Hashing and binary tree

Hashing

Hashing adalah merubah sebuat string ke dalam bentuk aritmatik yang merepresentasikan string tersebut. Hashing memasukkan bentuk aritmatik tersebut sebagai key dan memasukkannya ke dalam hash table

ada beberapa cara mendapatkan key yaitu:
1. mid-square
2. division
3. folding
4. digit extraction
5. rotating hash

jika ada beberapa string yang masuk ke dalam 1 array yang sama disebut dengan collision. Collision dapat di selesaikan dengan beberapa cara yaitu:
1. Linear Probing -> memasukkan string yang akan di masukkan ke dalam array yang sudah ada isinya tersebut ke array kosong terdekat.
2. Chaining -> tetap memasukkan string tersebut ke dalam srray yang sama dan menghubungkannya dengan linked list

Hashing digunakan dalam cryptographic untuk memperkecil output yang di keluarkan dan membuat transaksi menjadi aman dan tidak dapat di artikan oleh orang lain selain program itu sendiri.

Binary Tree

node yang paling atas disebut dengan Root

node yang dibuat dengan struct akan seperti ini

struct node {

  int data;

  struct node *left;

  struct node *right;

  struct node *parent;

};

struct node *root = NULL;

jika suatu node tidak memiliki child pointernya diisikan NULL

pertemuan 2

Linked list

ada 2 hal yang dapat dilakukan pada linked list yaitu
1. Push / insert -> push atau insert digunakan untuk menambahkan node dari sebuah linked list
2. Pop -> pop digunakan untuk menghilangkan sebuah node

A. Push
push dibedakan jadi 3 yaitu:
1. Push depan -> push depan berarti menambahkan node di depan linked list dan node baru itu menjadi node head. Harus diperhatikan bahwa node baru harus menunjuk ke node head yang lama baru node head bisa dipindahkan ke node yang baru ditambahkan.
2. Push belakang -> push belakang berarti menambahkan node menjadi tail sebuah linked list harus diperhatikan bahwa node yang baru harus memuliki nilai next yaitu NULL (kecuali  circular linked list). push belakang juga harus memperhatikan tail yang lama untuk menunjuk ke pada node yang baru.
3. Push tengah -> push tengah yaitu menambahkan node ke dalam linked list yang sudah ada. Perlu diperhatikan bahwa node sebelum harus menunjuk node yang baru tersebut dan node yang baru menunjuk node setelahnya agar linked list tetap berhubungan.

B. Pop
Pop dibedakan menjadi 3 yaitu:
1. Pop depan-> menghilangkan node head. Perlu dperhatikan bahwa node head harus dipindahkan dulu ke node sebelahnya baru melakukan free() pada node pertama.
2. Pop tengah-. menghilangkan node di antara head dan tail. Perlu diperhatikan bahwa node yang ada sebelum node yang akan di Free di hubungkan dulu ke node yang ada sesudah node yang akan di free baru bisa melakukan Free() kepada node yang ingin di hapus.
3. Pop belakang-> melakukan free pada node tail. perlu diperhatikan bahwa node tail harus dipindahkan dulu ke node sebelum yang kita inginkan untuk di hapus lalu melakukan Free() pada node paling akhir. Perlu juga diingat untuk memberikan nilai next pada tail yaitu NULL.