Heap and Tries

Heap adalah sebuah Complete Binary Tree yang memenuhi persyaratan heap. 

Dalam Heap ada beberapa rumus yang harus diketahui yaitu :

1. Mencari Index Parent : Index / 2 

2. Mencari Index Left Child : Index * 2

3. Mencari Index Right Child : (Index * 2) + 1

Heap dibagi menjadi 2 yaitu :

1. Min Heap

Pada Min Heap syarat utamanya adalah isi dari node parent harus lebih kecil dari node child-nya. (ascending-order)

   

2. Max Heap

Pada Max Heap syarat utamanya adalah isi dari node parent harus lebih kecil dari node child-nya.(descending-order)

3. Min Max Heap

Min Max heap adalah gabungan dari Min Heap dan Max Heap dimana level ganjil bersifat Min Heap dan level genap bersifat Max Heap.

Insertion

Ketika melakukan Insertion pada heap, data yang masuk akan selalu diletakan di index terakhir. Setelah itu data dibandingkan nilainya dengan nilai parentnya.

Pada Min Heap jika data baru lebih kecil dari parent maka posisi data baru dan data parent ditukar, lalu cek lagi dengan node parent selanjutnya hingga memenuhi syarat Min Heap.

Pada Man Heap jika data baru lebih besar dari parent maka posisi data baru dan data parent ditukar, lalu cek lagi dengan node parent  selanjutnya hingga memenuhi syarat Max Heap.

Deletion

Ketika melakukan Deletion pada heap pada root, maka data dengan index terakhir akan menggantikan root kemudian dibandingkan dengan node childnya sesuai dengan jenis Heap.

Pada Min Heap data dibandingkan dengan node child terkecil, jika data lebih besar dari node child terkecil maka data ditukar, lanjutkan hingga Heap memenuhi aturan Min Heap.

Pada Max Heap data dibandingkan dengan node child terbesar, jika data lebih kecil dari node child terbesar maka data ditukar, lanjutkan hingga Heap memenuhi aturan Max Heap.

Tries

Trie adalah suatu data struktur yang berbentuk pohon yang menyimpan huruf. Trie biasa digunakan pada AutoComplete, dan Search Engine seperti google, yahoo,dll.

Pada Trie setiap kata harus diberi EOW (End Of Word) sebagai penanda bahwa dari root hingga node terakhir adalah sebuah kata yang terdaftar.