Binary Tree dan hashing table

Pengertian dari hashing table adalah struktur data yang mengimplementasikan tipe data abstrak array asosiatif struktur yang dapat memetakan kunci ke nilai.Hashing table menggunakan fungsi hash untuk menghitung indeks,juga disebut kode hash,ke dalam array dari ember atau slot,dari mana nilai yang diinginkan dapat ditemukan.

Algoritma dalam hashing table :

index = f (key, array_size)

Hashing table dua langkah :

hash = hashfunc (kunci)
index = hash% array_size

Dalam metode ini, hash tidak tergantung pada ukuran array, dan kemudian dikurangi menjadi indeks (angka antara 0 dan array_size − 1 ) menggunakan operator modulo ( % ).

Jika semua kunci diketahui sebelumnya, fungsi hash sempurna dapat digunakan untuk membuat tabel hash sempurna yang tidak memiliki tabrakan. Jika hashing minimal sempurna digunakan, setiap lokasi di tabel hash dapat digunakan juga.

Gambaran Hashing Tree :



Binary tree adalah pohon dengan syarat bahwa tiap node hanya memiliki boleh maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua anak/child.

Jumlah maksimum node pada setiap tingkat adalah 2n, Node pada binary tree maksimumnya berjumlah 2n-1.

Ada 3 jenis binary tree yaitu:
1.Strict Binary Tree

Harus memiliki 2 anak,atau tidak punya sama sekali.

2.Complete Binary Tree

Harus punya anak dahulu dari yang paling kiri ke kanan.

3.Perfect Binary Tree

Semua harus punya anak dengan jumlah yang sama dan segitiga sempurna.

Selanjutnya ada yang dinamakan dengan binary search tree.Dimana pada tree ini data akan dimasukin ke sebelah kiri apabila lebih kecil dari nilai parent dan akan pergi ke sebelah kanan apabila nilai lebih besar dari parent.Hal ini akan terus berlanjut sampai menemukan nilai yang kosong/NULL.

Berikut merupakan cara untuk traversal dalam binary tree:
1.Inorder traversal

Berurutan berdasarkan nilai terkecil sampai terbesar.Dimulai dari paling kiri lalu dilanjutkan ke kanan dan mulai lagi ke paling kiri.

2.Preorder traversal

Mulai dari parent paling atas setelah itu ke kiri sampai leaf baru ke kanan.

3.Postorder traversal

Mulai dari child paling bawah kiri.Mulai dari leaf paling kiri lalu dilanjutkan ke kanan terus ke kiri dan kanan seterusnya.

gambaran Binary Tree :