Hashing, Tabel Hash, and Binary Tree

Hashing, Tabel Hash, and Binary Tree

Hashing adalah proses memetakan sejumlah besar item data ke tabel yang lebih kecil dengan bantuan fungsi hashing. Inti dari hashing adalah untuk memfasilitasi metode pencarian tingkat selanjutnya jika dibandingkan dengan pencarian linear atau biner. Keuntungan dari metode pencarian ini adalah efisiensinya untuk menyerahkan sejumlah besar item data dalam koleksi tertentu (misal ukuran koleksi). Karena proses hashing ini, hasilnya adalah struktur data hash yang dapat menyimpan atau mengambil item data dalam waktu rata-rata mengabaikan ukuran koleksi.

Tabel hash adalah hasil dari penyimpanan struktur data hash dalam tabel yang lebih kecil yang menggabungkan fungsi hash di dalam dirinya sendiri. Fungsi Hash terutama bertanggung jawab untuk peta antara item data asli dan tabel yang lebih kecil itu sendiri. Di sini pemetaan berlangsung dengan bantuan output integer dalam rentang konsisten yang dihasilkan ketika item data tertentu (semua tipe data) disediakan untuk penyimpanan dan rentang integer output ini menentukan lokasi dalam tabel yang lebih kecil untuk item data. Dalam hal implementasi, tabel hash dibangun dengan bantuan array dan indeks array ini dikaitkan dengan kisaran integer output.

Binary Tree 

Merupakan salat Satu bentuk Struktur Data tidak linier yang menggambarkan hubungan Yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul / node dengan satu elemen khusus yang disebut root dan node lainnya terbagi menjadi Himpunan-Himpunan Yang tak saling berhubungan Satu sama lainnya (disebut subtree). dibawah ini diuraikan istilah-istilah umum dalam tree.

• Parent : predecssor satu level di atas suatu node.
• Child : successor satu level di bawah suatu node.
• Sibling : node-node yang memiliki parent yang sama dengan suatu node.
• Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
• Size : banyaknya node dalam suatu tree.
• Height : banyaknya tingkatan/level dalam suatu tree.
• Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
• Leaf : node-node dalam tree yang tak memiliki seccessor.
• Degree : banyaknya child yang dimiliki suatu node.

Pengertian Binary Tree dalam Struktur Data

Pohon biner 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.

Node pada Binary Tree 

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

Pemakaian tree structure dalam proses pencarian (search)

-Sifat Binary Tree:

Pada sebuah node x,

1.    elemen yang berada di LEFT sub-tree selalu lebih KECILdaripada x

2.    elemen yang berada di RIGHT sub-tree selalu lebih BESAR Atau SAMA DENGAN daripada x

-Binary Search Tree: proses pencarian (SEARCHING) berbasis binary tree

Tree traversal adalah cara kunjungan node-node pada pohon biner.

Ada tiga cara kunjungan dalam tree:

1.  Pre order

2. In order

3. Post order

1. Pre order

a. Cetak data pada root

b. Secara rekursif mencetak seluruh data pada subpohon kiri

c. Secara rekursif mencetak seluruh data pada subpohon kanan

2. In order

a. Secara rekursif mencetak seluruh data pada subpohon kiri

b. Cetak data pada root

c. Secara rekursif mencetak seluruh data pada subpohon kanan

3. Post order

a. Secara rekursif mencetak seluruh data pada subpohon kiri

b. Secara rekursif mencetak seluruh data pada subpohon kanan

c. Cetak data pada root

Insert Binary Search Tree

Penyisipan sebuah  node baru, didahului dengan operasi pencarian posisi yang sesuai. Dalam hal ini node baru tersebut akan menjadi daun.

Delete Binary Search Tree

Operasi delete memiliki 3 kemungkinan :

- Delete terhadap node tanpa anak/child (daun) : node dapat langsung dihapus

- Delete terhadap node dengan satu anak: maka node anak akan menggantikan posisinya.

- Delete terhadap node dengan dua anak: maka node akan digantikan oleh node paling kiri dari Sub Tree Kanan atau dapat juga digantikan oleh anak paling kanan dari Sub Tree Kiri.