Heaps & tries

Heap

Minggu lalu kita sudah membahas AVL Tree dan sekarang kita akan membahas Heap & Tries. Heap adalah sebuah struktur data dengan konsep binary tree. Heap mempunyai dua jenis yaitu:

• Min - heap
• Max - heap
• Min - Max heap

Heap dapat diimplementasikan dengan linked list, namun akan lebih gampang jika menggunakan array. Agar lebih jelas, lebih baik kita lihat gambar berikut ini.

Heap dari geeksforgeeks

Min - Heap

Pada min - heap terdapat aturan agar heap itu dapat dibuat. Aturan tersebut adalah angka atau huruf yang ada di root harus paling kecil daripada anak - anaknya. Hal ini juga berlaku pada subtree lainnya secara rekursif. Jadi, yang diatas harus lebih kecil daripada bawahnya.

Insertion

Berbeda dengan BST yang mempunyai aturan kiri harus yang kecil dan kanan yang besar, min - heap hanya menghiraukan atasnya. Pada kasus min - heap berarti atasnya harus lebih kecil daripada bawahnya. Agar kita mengerti cara menginsertnya, lihat gambar berikut:

Kita akan menginsert angka 3, 1, 6, 5, 2, 4

Karena angka pertamanya adalah 3, maka kita langsung insert angka tersebut menjadi root.

Insert 1

Nah pada kasus diatas, angka 3 lebih besar daripada 1. Karena aturannya tidak memperbolehkan hal itu untuk terjadi, maka angka 1 dan 3 harus ditukar menjadi seperti berikut:

Selanjutnya, kita akan menginsert angka 6.

Karena angka 1 sudah lebih kecil daripada 6, maka tidak perlu ditukar seperti angka 3. Sehabis itu, kita akan menginsert angka 5 di array selanjutnya.

Karena angka 3 sudah lebih kecil daripada 5, kita tidak perlu menukarnya lagi. Lanjut, kita insert angka 2.

Nah, ini kita harus menukar angka 3 dan 2 sehingga menjadi berikut:

Selanjutnya, kita insert angka terakhir kita yaitu 4.

Angka 6 tidak lebih kecil daripada 4 sehingga harus ditukar.

Setelah ditukar, jadilah sebuah min - heap, horeee hhhhh.

Deletion

Pada min - heap, terdapat aturan agar deletion dapat terjadi dengan benar. Step - stepnya adalah sebagai berikut:

1. Siapkan heapnya terlebih dahulu (ya iyalah kalo ngga gimana mau di delete bang)
2. Delete nilai yang ingin kamu delete (kalo mau delete 2, ya hapus 2 jangan 5).
3. Tempat dari nilai yang kamu delete tadi diganti dengan nilai paling bawah kanan. 
4. Cek nilai yang lainnya. Sehabis kamu ganti apakah ada yang tidak sesuai dengan aturannya? Kalo iya, tukar nilainya terus - terusan sampai heapnya benar.

Mari kita lihat contoh agar lebih mengerti.

Pada heap tree tersebut, kita ingin mendelete angka 2 sehingga menjadi seperti berikut.

Karena 9 merupakan nilai yang ada di paling bawah kanan, maka 9 akan mengambil tempat 2.

Selanjutnya, kita akan mengecek apakah ada node yang tidak memenuhi aturan. Nah karena 9 ternyata lebih besar daripada 5 dan 7, maka kita mengambil 5 untuk menjadi root. Kita tidak mengambil 7 karena 5 adalah nilai yang paling kecil diantara mereka ber 2.

Deletion sukses dilakukan jadi Horeee lagiii HHHHHH.

Max - Heap

Max - heap intinya sama saja dengan min - heap. Hanya, yang membedakan adalah aturannya. Angka atau huruf yang ada di root harus paling besar daripada anak - anaknya. Ini juga berlaku pada subtree lainnya secara rekursif. Jadi, yang diatas harus lebih besar daripada bawahnya.

Insertion

Insertion dari max - heap sangat mirip dengan min - heap. Kita hanya perlu menukar jika ada angka yang lebih besar.

Contoh:

Ceritanya kita akan memasukkan angka 6, 4, 8, 2, 7, 1

Insert 6:
      6

Insert 4:
      6
    /    
   4      

Insert 8:
      6             Swap 8 sama 6          8    
    /    \          ------------>        /   \
   4      8                             4     6

Insert 2:
       8
     /   \         
    4     6        
  /
 2

Insert 7:

       8                                         8
     /   \          Swap 7 dengan 4            /   \
    4     6         ---------------->         7     6
  /   \                                     /   \
 2     7                                   2     4

Insert 1:
        8
      /   \
     7     6
    / \   /
   2   4 1

Deletion

Insertion dari max - heap mirip dengan min - heap, itu juga berlaku pada deletionnya. Agar lebih jelas, lihatlah contoh berikut:

Misalnya heapnya dengan aturan Max - heap:
      10
    /    \
   5      3
  / \
 2   4

Elemen yang mau dihapusnya yaitu 10

Process:
Elemen paling kanan bawahnya adalah 4

Step 1: Hapus angka 10 yaitu angka yang ada di root
      
    /    \
   5      3
  / \
 2   4
Step 2: Angka 4 itu paling kanan bawah, jadinya gantiin tempat 10
      4
    /    \
   5      3
  / 
 2   
Step 2: Tukar angka yang tidak sesuai dengan aturannya (dalam kasus ini angka 4 dan 5)
Final Heap:
      5
    /    \
   4      3
  / 
 2   

Min - Max Heap

Nah ini adalah bentuk terakhir dari heap. Kalo gamer bilang sih Final Boss nya dari heap. Jadi kalo belum bisa ngalahin/ngertiin yang sebelumnya. mending jangan liat ini dulu, oke?

Nah aturan yang ada di heap ini adalah rootnya mempunyai aturan min - heap, lalu dibawahnya menganut aturan max - heap, lalu dibawahnya lagi menganut aturan min - heap. Jadi aturannya selang - seling begitu.

Insertion

Nah setelah kita mengetahui aturannya, mari kita coba menginsert beberapa angka hingga menjadi min - max heap.

Contohnya kita akan menginsert 6, 4, 8, 2, 7, 1

Insert 6:

Min:    6

Insert 4:
Min:      6       6 harus diswap dengan 4            4
        /         ----------------------->         /   
Max:   4                                          6

Insert 8:
Min:      4               
        /    \          
Max:   6      8          

Insert 2:
Min:       4
         /   \         
Max:    6     8        
       /
Min:  2

Insert 7:

Min:       4                                            4
         /   \                                        /   \
Max:    6     8            ---------------->         7     8
       / \                                         /   \
Min:  2   7                                       2     6

Insert 1:
Min:       4
         /   \         
Max:    7     8        
       / \   /
Min:  2   6 1

Deletion

Berikut adalah langkah - langkah untuk menghapus sebuah node pada min - max heap:

1. Sekali lagi untuk yang terakhir kalinya, heapnya harus ada lah
2. Tentukan mana yang mau dihapus
3. Setelah tau yang mana mau dihapus, liatin dulu ini heap apa bukan? Kalo bukan ngapain di delete coba?
4. Nah habis dipastiin, hapusin yang kamu mau
5. Ganti posisi yang dihapus tersebut dengan node yang paling bawah kanan
6. a. Downheapmin: Cari angka terkecil dari anak dan cucu dari node yang sudah dihapus. Setelah itu, ganti saja tempatnya
   b. Downheapmax: Ini kebalikannya downheapmin

Nah, kalau kurang jelas, mari kita langsung ke contohnya.

Misalnya kita mau delete 9. Hal yang akan terjadi adalah begini

Nah, lalu kita akan mereplacenya dengan kanan paling bawah, yaitu 90.

Kita lalu menerapkan down-heap min. Karena 20 lebih kecil daripada 90, kita harus menukarnya jadi seperti ini:

Tries

Pengertian tries dari Medium.com

Seperti yang telah diberikan diatas, tries itu adalah sebuah kata yang berasal dari kata "retrieve". Jadi trie itu adalah sebuah data structure yang mempunyai sifat tree yang digunakan untuk menyimpan alfabet atau string dari sebuah kata. Menyimpannya adalah dengan membuat cabang terus-terusan ke bawah.

Cara menginsert di dalam sebuah trie

Nah, dalam membuat sebuah trie, kita hanya perlu mengurut alfabetnya sehingga menjadi urut. Dari gambar diatas, pastinya tidak sulit untuk mengerti trie, bukan? (iyain aja sumpah orang gampang kok)

Demikian rangkuman untuk Heaps & Tries. Ingat saja bahwa heap ada min, max, dan min - max heap yang mempunyai aturan yang berbeda - beda. Ada juga tries yaitu salah satu tipe dari tree yang mengatur alfabet.