Hashing & Binary Tree

⤼ HASH TABLE.

Hash Table adalah struktur data yang menyimpan data dalam format array, yang mana setiap nilai data memiliki nilai indeks uniknya sendiri. Jika kita mengetahui indeks dari data yang diinginkan, pengaksesan data dapat dilakukan dengan lebih cepat. Hashing adalah teknik untuk mengubah range nilai-nilai kunci menjadi range indeks array. Operator modulo digunakan untuk mendapatkan range nilai kunci tersebut.

[ Hash function ] :: h = k (mod s)

-- keterangan :

h → hash index / hash value / index yang ingin dituju

k → key value / nilai dari data

s → size array

Ketika diterapkan, kerap kali terjadi collision (tabrakan). Collision adalah suatu kondisi dimana > 1 nilai dari data mempunyai hash index yang sama, yang sebenarnya satu hash index hanya dapat menyimpan satu nilai data saja. Oleh karena itu, terdapat beberapa metode hash table agar tidak terjadi collision :

1. Linear probing

Mencari alamat yang belum terisi data dengan cara berurutan, dari 1 indeks (jika terisi) bergeser satu ke indeks selanjutnya. [ rumus : (h+1) mod m ]

2. Quadratic probing / squared probing

Mencari alamat baru untuk ditempati dengan proses perhitungan kuadratik yang lebih kompleks. Tidak ada rumus spesifik untuk probing ini.

3. Double hashing

Menggunakan hash function lagi untuk memperoleh alamat baru untuk menyimpan data yang belum dapat masuk ke dalam table. Kelemahan function ini adalah ukuran array yang disediakan harus lebih besar dari jumlah data. Selain itu dibutuhkan memori yang lebih besar untuk meminimalisir collision.

4. Open Hashing

Menggunakan hash function untuk menentukan linked list mana yang memiliki element yang dicari, lalu melakukan pembacaan pada linked list tersebut. Untuk penghapusan element, dapat dilakukan dengan menghapus linked list setelah dilakukan pencarian.

* * *

Contoh Binary Tree

⤼ BINARY TREE.

‣ TREE adalah salah satu bentuk struktur data yang menggambarkan hubungan hierarki antar elemen-elemennya. Di dalam tree, terdapat akar dan node/vertex. Di setiap nodenya, biasanya terdapat beberapa node lagi yang merupakan percabangan atas node itu sendiri.

‣ BINARY TREE adalah sebuah tree yang hanya memiliki maksimal dua percabangan pada setiap nodenya.

Terminologi pada Tree :

1. Simpul

Elemen tree yang berisi informasi / data dan penunjuk pencabangan. ( contoh : simpul f )

2. Anak (Child) dan Orangtua (Parent)

» simpul e dan f adalah anak dari simpul b.

    maka simpul b adalah orangtua dari f.

» simpul g adalah anak dari simpul d.

    maka simpul d adalah orangtua dari g.

3. Path (lintasan)

Runtutan dari sebuah simpul ke simpul lainnya. Panjang lintasan adalah jumlah sisi yang dilalui dalam suatu lintasan, yaitu k – 1. 

» lintasan dari a ke h adalah a, b, e, h.

» panjang lintasan dari a ke h adalah 3.

4. Descendant (keturunan) & Ancestor (leluhur)

» simpul b adalah leluhur dari simpul h.

   simpul h adalah keturunan dari simpul simpul b.

» simpul k adalah leluhur dari simpul d.

   simpul k adalah keturunan dari simpul d.

5. Sibling (Saudara Kandung)

Simpul-simpul yang berasal dari satu simpul yang sama (orang tua yang sama).

» simpul e saudara kandung dari simpul f.

» simpul g bukan saudara kandung dari simpul e.

6. Subtree (Sub pohon)

Subtree dengan x merupakan akarnya adalah subgraf T’ = (V’,E’) sedemikian hingga V’ mengandung x dan semua keturunannya dan E’ mengandung sisi-sisi dalam semua lintasan yang berasal dari x.
(pada gambar G2) :

» V’ = {b, e, f, h, i, j}

» E’ = {(b, e), (b, f), (e, h), (e, i), (e, j)}

» b adalah simpul akar.

7. Degree (Derajat)

Jumlah anak/node keluar dari sebuah simpul.

(pada gambar G1) :

» simpul e = 3

» simpul k = 2

» simpul c = 0

» simpul d = 1

» derajat tertinggi/maksimum = 3

8. Leaf (Daun)

Simpul yang berderajat nol/tidak mempunyai anak. 

(pada gambar G1)  :

» daun = simpul c, f, h, i, j, l dan m.

9. Internal Nodes (Simpul Dalam)

Simpul yang berderajat > 0 / mempunyai anak.

(pada gambar G1) :

» simpul dalam : simpul b, d, e, g dan k.

10. Level (Tingkat)

» Akar (pada gambar : simpul a) mempunyai level 0.

» Level simpul lainnya = 1 + panjang lintasan (lihat gambar G3).

11. Height (tinggi) / Kedalaman (depth)

Level maksimum suatu pohon.

(pada gambar) :

» height = 4.

Jenis-Jenis Binary Tree :

1. Full Binary Tree

Binary tree yang tiap node-nya (kecuali leaf) memiliki dua anak dan tiap subtree harus mempunyai panjang path yang sama.

2. Complete binary Tree

Binary tree yang mirip dengan full binary tree, namun tiap subtree boleh memiliki panjang path yang berbeda.
[ untuk node (kecuali leaf) yang memiliki 0 atau 2 anak. ]

3. Skewed Binary Tree

Binary tree yang semua node nya (kecuali leaf) hanya memiliki satu anak.

4. Balanced Binary Tree

Binary tree yang height antara node sub kiri dengan satunya sama atau berselisih satu.

* * *

< Thank you for reading this blog! :) >