Hashing & Tree

HASHING

Hashing merupakan teknik menyimpan dan mengambil kunci dengan cepat.
Hashing berarti mengambil string input dengan panjang berapa pun dan memberikan output dengan panjang tetap.

Metode hash string menjadi key :
1. Mid-square
2. Division
3. Folding
4. Digit extraction
5. Rotating Hash

1. Mid-square
Langkah :
1. Ambil nilai awal
2. Kuadratkan nilai awal
3. Beberapa digit angka ditengah setelah dikuadratkan, diambil dan diekstrak menjadi nilai baru
Contoh :
3121 dikuadratkan menjadi 9740641. Nilai tengahnya adalah 406.
Binarinya adalah 1001 0100 1010 0001 0110 0001‬.

2. Divison
Divison menggunakan modulus.
Contoh :
Nilai asli = 5
Ukuran tabel = 4
(5 % 4)+1 = 1+1 = 2. Simpan 5 di lokasi 2.

3. Folding
Langkah :
1. Nilai dibagi menjadi beberapa bagian, tiap bagian memiliki jumlah digit yang sama
2. Lipat seperti kertas, lalu dijumlah
Contoh :
- 1234 = 12 + 34 = 46. Hash valuenya adalah 46.
- 123654 = 123 + 654 = 777. Hash valuenya adalah 777.
- 321456 = 321 + 456 = 777. Hash valuenya adalah 777.

Terjadi collision antara 123654 dan 321456.
Collision adalah peristiwa dimana ada dua atau lebih nilai asli yang memiliki hash value yang sama. Penyelesaiannya adalah dengan cara probing dan chaining.

4. Digit extraction
Digit yang ditentukan sebelumnya dari nomor yang diberikan dianggap sebagai alamat hash.
Contoh : 14568
Digit ke 1 adalah 1
Digit ke 3 adalah 5
Digit ke 5 adalah 8
Maka disimpan di 158.

5. Rotating
Hanya membalikkan nilai asli
Contoh : 12345 menjadi 54321. Hash codenya adalah 54321.



TREE

Tree adalah node tanpa pengulangan/looping.

Konsep tree

DEGREE of TREE = 3

DEGREE of C = 2

HEIGHT = 3

PARENT of C = A

CHILDREN of  A = B, C, D

SIBILING of F = G

ANCESTOR of F = A, C

DESCENDANT of C = F, G

Konsep binary tree

ROOT = 18
LEAVE = 9, 12, 10, 23















Macam-macam pohon binari:
1. Pohon binari penuh

2. Pohon binari lengkap

3. Pohon binari similer

4. Pohon binari ekuivalen

5. Pohon binari miring

PREFIX, INFIX & POSTFIX

1. Prefix

Kunjungan secara preorder (Depth First Order), mempunyai urutan :

1. Cetak isi simpul yang dikunjungi (simpul akar)

2. Kunjungi cabang kiri

3. Kunjungi cabang kanan

2. Infix

Kunjungan secara inorder (symetric order), mempunyai urutan :
1. Kunjungi cabang kiri
2. Cetak isi simpul yang dikunjungi (simpul akar)
3. Kunjungi cabang kanan

 3. Postfix

Kunjungan secara postorder, mempunyai urutan :
1. Kunjungi cabang kanan
2. Kunjungi cabang kiri
3. Cetak isi simpul yang dikunjungi (simpul akar)