Hash Table and Binary Trees

Ø  Hash table

            Jadi, apa itu hash table? hash table merupakan sebuah fungsi dalam struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel. Keunggulan dari struktur hash table ini yaitu memiliki waktu pengaksesan data yang cepat. Namun kekurangannya ialah sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (collision).Maka dari itu perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam table agar angka – angka hash tidak saling bertabrakan (collision). Berikut hal – hal yang dapat dilakukan untuk menghindari collision :
           

·         Closed hashing (Open Addressing)

Close hashing menyelesaikan collision dengan menggunakan memori yang masih ada tanpa menggunakan memori diluar array yang digunakan. Closed hashing mencari alamat lain apabila alamat yang akan dituju sudah terisi oleh data. 3 cara untuk mencari alamat lain tersebut :

1.      Linear Probing

Apabila telah terisi, linear probing mencari alamat lain dengan bergeser 1 indeks dari alamat sebelumnya hingga ditemukan alamat yang belum terisi data, dengan rumus (h+1) mod m.

2.      Quadratic Probing

Quadratic Probing mencari alamat baru untuk ditempati dengan proses perhitungan kuadratik yang lebih kompleks. Tidak ada formula baku pada quadratic probing ini,anda dapat menentukan sendiri formula yang akan digunakan.

3.      Double hashing

Sesuai dengan namanya, alamat baru untuk menyimpan data yang belum dapat masuk ke dalam table diperoleh dengan menggunakan hash function lagi. Hash function kedua yang digunakan setelah alamat yang dihasilkan oleh hash function awal telah terisi tentu saja berbeda dengan hash function awal itu sendiri.

Kelemahan dari closed hashing adalah ukuran array yang disediakan harus lebih besar dari jumlah data. Selain itu dibutuhkan memori yang lebih besar untuk meminimalkan collision.

·         Open hashing (Separate Chaining)

Pada dasarnya separate chaining membuat tabel yang digunakan untuk proses hashing menjadi sebuah array of pointer yang masing-masing pointernya diikuti oleh sebuah linked list, dengan chain (mata rantai) 1 terletak pada array of pointer, sedangkan chain 2 dan seterusnya berhubungan dengan chain 1 secara memanjang.

Kelemahan dari open hashing adalah bila data menumpuk pada satu/sedikit indeks sehingga terjadi linked list yang panjang.

Ø  Binary tree

Lalu, apa itu binary tree? Binary tree merupakan sebuah fungsi pada data structure (sama seperti hash table) namun memiliki konsep yang berbeda. Seperti Namanya, 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). Berikut merupakan macam – macam pengoperasian 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 Insert Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert : sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong

4.      Find 
     Mencari root, parent, left child, atau right child dari suatu node. (tree tidak boleh kosong).

5.      Update 
     Mengubah isi dari node yang ditunjuk oleh pointer curret
(Tree tidak boleh kosong)

6.      Retrieve 
     Mengetahui isi dari node yang ditunjuk oleh pointer current
(Tree tidak boleh kosong)

7.      DeleteSub 
     Menghapus sebuah subtree (node beserta seluruh descendantnya)
yang ditunjuk current. Tree tidak boleh kosong. Setelah itu, pointer current dakan berpindah ke parent dari node yang dihapus.

8.      Characteristic 
     Mengetahui karakteristik dari suatu tree, yakni: size, height, serta average length. Tree tidak boleh kosong.

9.      Traverse 
     Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linear yang
tersimpan dalam tree. Ada tiga cara traverse,yaitu PreOrder, InOrder, dan PostOrder.
Berikut langkah – langkah dalam membaut traverse :

1)      PreOrder : 
cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child

2)       InOrder : 
kunjungi Left Child, cetak isi node yang dikunjungi, kunjungi Right C

3)      PostOrder : 
kunjungi Left Child, kunjungi Right Child cetak isi node yang dikunjungi.