Binus Preview

Data Structure (Conclusion)

Heap Tree
Head tree merupakan sebuah complete binary tree, biasanya menggunakan array dan dibagi menjadi 3 :

1. Min Heap Tree
   Merupakan Tree yang sudah di sorting dari yang terkecil sebagai root hingga yang terbesar di leaf.
2. Max Heap Tree
   Merupakan Tree yang sudah di sorting dari yang terbesar sebagai root hingga yang terkecil di leaf.
3. Min-Max Heap Tree
   Merupakan Tree yang sudah di sorting dari yang terkecil sebagai root, lalu memiliki child dengan sorting angka/prioritas terbesar, dilanjutkan dengan child Min, lalu child Max, dan seterusnya.

Trie
Trie berasal dari kata re(TRIE)val. Biasanya, Trie digunakan untuk menampung data yang biasanya ada pada tampilan keyword search engine.

Hashing

Hashing adalah sebuah transformasi dari karakter string menjadi suatu value/keyword yang lebih pendek yang mewakili string originalnya. Hashing menggunakan array/index karena dapat melakukan pencarian dengan lebih cepat.

Function pada Hash

1. Mid-Square
   Dengan meng-kuadratkan string/indetifier, lalu menggunakan number of bits dari nilai tengah kuadratnya kaan menghasilkan hash key.
2. Division (Paling Umum)
   Membagi string/identifier dengan menggunakan modulus operator. Hasilnya akan menjadi hash key.
3. Folding
   Membagi-bagi string/identifier menjadi beberapa bagian, lalu menjumlahkan bagian tersebut dan menghasilkan hash key.

Jika terjadi collision, dimana suatu hash key sudah ditempati oleh value lain, maka dapat diselesaikan dengan 2 cara

1. Probing
   Value dari hash key baru akan masuk ke baris yang selanjutnya, dengan penanda value [step = step + 1].
2. Chainning
   Value dari hash key baru akan disambungkan dengan value hash key lama.