Heap and Tries

HASH TABLE                                                                                                                        
       Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain. keunggulan dari Hash Table adalah waktu mengakses lebih cepat.

• Operasi pada Hash Table

                insert: diberikan sebuah key,insert nilai dalam tabel

                find   : diberikan sebuah key,menemukan nilai yang berhubungan dengan key

                remove: diberikan sebuah key,menemukan nilai yang berhubungan dengan key                                            kemudian di hapus nilai tersebut.

                getiterator: mengembakikan iterator, yang memeriksa nilai satu demi satu. 

 Fungsi Hash yang biasa digunakan : 

1. Division

Secara umum, rumusnya h(k)= k mod m. Dalam hal ini m adalah jumlah lokasi memori yang tersedia pada array.  eFungsi hash tersebut menempatkan record dengan kunci K pada suatu lokasi memori yang beralamat h(k). Metode ini sering menghasilkan nilai hash yang sama dari dua atau lebih nilai aslinya atau disebut dengan bentrokan.

2. Mid-Square
adalah teknik hashing di mana kunci unik dihasilkan. Dalam teknik ini, nilai benih diambil dan dikuadratkan. Kemudian, beberapa digit dari tengah diekstraksi. Angka-angka yang diekstrak ini membentuk angka yang diambil sebagai benih baru. Teknik ini dapat menghasilkan kunci dengan keacakan tinggi jika nilai benih yang cukup besar diambil. Namun, itu memiliki batasan. Saat bijinya dikuadratkan, jika angka 6-digit diambil, maka persegi akan memiliki 12-digit. Ini melebihi kisaran tipe data int. Jadi, overflow harus diurus.

3. Folding
Untuk mendapatkan alamat relatif, nilai key dibagi menjadi beberapa bagian, setiap bagian (kecuali bagian terakhir) mempunyai jumlah digit yang sama dengan alamat relatif. Bagian-bagian ini kemudian dilipat (seperti kertas) dan dijumlah. Hasilnya, digit yang tertinggi dibuang (bila diperlukan).

BINARY TREE

Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut  terpisah.  maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.

Binary Tree merupakan kumpulan dari satu node atau lebih. 

Di dalam Tree terdapat : 

1. Prodecessor : node yang berada diatas node tertentu.
2. Successor : node yang berada di bawah node tertentu.
3. Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
4. Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
5. Parent : predecssor satu level di atas suatu node.
6. Child : successor satu level di bawah suatu node.
7. Sibling : node-node yang memiliki parent yang sama dengan suatu node.
8. Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
9. Size : banyaknya node dalam suatu tree.
10. Height : banyaknya tingkatan/level dalam suatu tree.
11. Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
12. Leaf : node-node dalam tree yang tak memiliki seccessor.
13. Degree : banyaknya child yang dimiliki suatu node

Binary Tree merupakan struktur data potoh yang di rootnya memiliki paling banyak dua child.

Impelementasi Binary Tree

Create          : Membentuk binary tree baru yang masih kosong.

Clear            : Mengosongkan binary tree yang sudah ada.

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.

Find              : Mencari root, parent, left child, atau right child dari suatu node.tree tak boleh kosong

Update          : Mengubah isi dari node yang ditunjuk oleh pointer current. tree tak boleh kosong

Retrieve         : Mengetahui isi dari node yang ditunjuk pointer current. tree tak boleh kosong

DeleteSub      : Menghapus sebuah subtree  yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.

Characteristic : Mengetahui karakteristik dari suatu tree, yaitu: size, height, serta average lengthnya. Tree tidak boleh kosong. 

Traverse         : Mengunjungi seluruh node-node pada tree, masing-masing sekali.  Adatiga cara traverse : Pre Order, In Order, dan Post Order.