Hash Table & Binary Tree

HASH TABLE

Apa itu Hash Table ?

Sebuah struktur data yang terdiri dari sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.

Apa itu Hashing ?

Hashing adalah transformasi sebuah input menjadi sebuah fixed value yang lebih pendek dan simple. Contohnya adalah sebuah fungsi yang meminta string dan memproduce integer dari 0-99. Fungsi hash ini bisa dipadukan dengan array untuk menghasilkan hash table. 

Kenapa Hash Table ?

Karena hash table ini memiliki kelebihan yaitu insertion dan searching value yang ada di array dengan sangat cepat.

Operasi Hash Table:

• insert : diberikan sebuah key dan nilai, insert nilai dalam table.
• find : diberikan sebuah key, temukan nilai yang berhubungan dengan key.
• remove : diberikan sebuah key, temukan nilai yang berhubungan dengan key lalu hapus.

Bagaimana cara kerja Hash Table ?

Hash table memiliki 2 komponen penting yaitu KEY dan VALUE. Key itu yang akan menjadi identifikasi dari value dan dimasukkan kedalam fungsi hash. Value adalah value/nilai yang akan dimasukkan kedalam array.

Contoh :

Jadi, key nya itu dimasukkan kedalam fungsi hash. Misalnya ConvertHash(John)->3; maka value dari john yaitu dori akan berada di index ke-3. Lalu jika ada ConvertHash(Ming)->3; padahal sudah sebelumnya terisi maka akan terjadi "Collision" yaitu bentrokan. Solusinya adalah menggunakan linked list untuk memasukkan value "Dan".

BINARY TREE

Binary Tree adalah sebuah pohon dalam struktur data yang bersifat hirarki. Tree adalah kumpulan dari berbagai leaves, setiap leaves paling banyak memiliki 2 anak. Anak tersebut diberi nama kiri dan kanan. 

Operasi-operasi pada Binary Tree :

1. Create : Membentuk binary tree baru yang masih kosong.
2. Clear : Mengosongkan binary tree yang sudah ada.
3. Empty : Function untuk memeriksa apakah binary tree masih kosong.
4. Insert : Memasukkan sebuah node ke dalam tree. 
5. Find : Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh kosong)
6. Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)
7. Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong)
8. DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendantnya) yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.
9. Characteristic : Mengetahui karakteristik dari suatu tree, yakni : size, height, serta average lengthnya. Tree tidak boleh kosong. 
10. Traverse : Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Ada tiga cara traverse : Pre Order, In Order, dan Post Order.

BINARY SEARCH TREE

Binary Search Tree adalah tree yang terurut. Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory. Data dibagi menjadi dua dengan 1 ditengah sebagai patokannya. Ada data kiri dan kanan. Semua data di kiri subtree dari node harus selalu lebih kecil dari data dalam node itu sedangkan semua data bagian kanan subtree dari node harus selalu lebih besar atau sama dengan data dalam node itu. Binary search tree memungkinkan pencarian dengan cepat, penambahan, juga menghapus data yang ada di dalamnya.