HASHING TABLE & BINARY TREE

Hashing Table

Hashing Table adalah sebuah 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:

• Waktu akses data lebih cepat
• Kecepatan dalam insertions, deletions, maupun searching relatif sama

 Operasi pada Hashing Tabel:

• insert: diberikan sebuah key dan nilai, insert nilai dalam tabel
• find: diberikan sebuah key, temukan nilai yang berhubungan dengan key
• remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut
• getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu

Binary Tree

Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki max. 2 subtree & kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak 2 child.

Jenis-jenis Binary Tree:

Full Binary Tree

Jenis binary tree ini tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtreeharus mempunyai panjang path yang sama.

Complete Binary Tree

Jenis ini mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda dan setiap node kecuali leaf hanya boleh memiliki 2 child.

Skewed Binary Tree

Skewed Binary Tree adalah Binary Tree yang semua nodenya (kecuali leaf) hanyamemiliki satu child.

Implementasi Binary Tree

Binary tree dapat diimplementasikan dalam C++ dengan menggunakan doublelinkedlist.

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. Ada tiga pilihan insert: sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong.
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. (Average Length = [jumlahNodeLvl1*1+jmlNodeLvl2*2+…+jmlNodeLvln*n]/Size)
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.

Langkah-Langkahnya Traverse :

• PreOrder : Cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child.
• InOrder : Kunjungi Left Child, Cetak isi node yang dikunjungi, kunjungi Right Child.
• PostOrder : Kunjungi Left Child, Kunjungi Right Child, cetak isi node yang dikunjungi

Referensi :

• http://muqoddasrengmadureh.blogspot.com/2013/01/algoritma-dan-struktur-data-hashing.html
• https://saragusti22.wordpress.com/2015/05/04/pengantar-struktur-data-tree-dan-binary-tree/
• https://zoneblog123.blogspot.com/2018/04/pengertian-tree-binary-tree-beserta.html