Heap and Tries

Pengertian Heap

Heap adalah binary tree yang sudah lengkap yang telah memenuhi persyaratan heap. Berbeda dari AVL Tree, B-Tree, dan Red-Black Tree, Heap tidak memiliki balance factor ataupun warna dalam melakukan rebalancing.

Bentuk Heap

Heap sendiri memiliki dua bentuk umum:

1. Min Heap
2. Max Heap

Min Heap

Min Heap adalah heap dengan nilai parent lebih kecil dibandingkan nilai childnya. Di dalam tree Min Heap, nilai terkecil terdapat di root, sedangkan nilai terbesarnya terdapat di bagian leaves. Implementasi Min Heap dapat dilakukan di linked list, namun lebih mudah dilakukan dengan menggunakan array. Berikut adalah contoh Min Heap:

Dapat dilihat bahwa nilai parent lebih kecil dibandingkan nilai child nya. Nilai terkecil terdapat pada root, nilai terbesar terdapat di leaves, yaitu 83.

Cara Insert

Berikut adalah cara insert menggunakan Min Heap yang saya pelajari dari kelas kecil saya. Setiap node yang baru masuk dijadikan leaf. Setelah masuk, maka akan melakukan pengecekan dengan parentnya atau biasa disebut sebagai uphead atau heapify up. Bila nilai child lebih kecil daripada parent, maka akan melakukan balancing dengan cara menukar nilai child dengan nilai parent. Pengecekan ini dilakukan secara rekursif. Ini dilakukan sampai tree menjadi balance.

Cara Delete

Berikut adalah cara delete menggunakan Min Heap yang saya pelajari dari kelas kecil saya. Berbeda dengan Binary Search Tree ataupun AVL, dalam heap nilai yang dihapus SELALU ROOT. Setelah root dihapus maka, ARRAY TERAKHIR akan menggantikan posisi root. Kita tidak menggunakan predecessor ataupun successor. Setelah menjadi root, maka akan melakukan pengecekan dengan childrennya. Ini dapat disebut sebagai down heap atau heapify down. Bila nilai child lebih kecil dari parent, maka akan melakukan balancing dengan cara menukar parent dengan child. Pengecekan ini dilakukan secara rekursif.

Max Heap

Max Heap adalah heap dengan nilai parent lebih besar dibandingkan nilai childnya. berbeda dengan  tree Min Heap, dalam tree Max Heap, nilai terkecil terdapat di leaves, sedangkan nilai terbesarnya terdapat di bagian root. Implementasi Max Heap dapat dilakukan di linked list, namun lebih mudah dilakukan dengan menggunakan array. Berikut adalah contoh Min Heap:

Dapat dilihat bahwa nilai parent lebih besar dibandingkan nilai child nya. Nilai terbesar terdapat pada root, nilai terkecil terdapat di leaves, yaitu 23.

Cara Insert

Berikut adalah cara insert menggunakan Max Heap yang saya pelajari dari kelas kecil saya. Setiap node yang baru masuk dijadikan leaf. Setelah masuk, maka akan melakukan pengecekan dengan parentnya atau biasa disebut sebagai uphead atau heapify up. Bila nilai child lebih besar daripada parent, maka akan melakukan balancing dengan cara menukar nilai child dengan nilai parent. Pengecekan ini dilakukan secara rekursif. Ini dilakukan sampai tree menjadi balance.

Cara Delete

Berikut adalah cara delete menggunakan Max Heap yang saya pelajari dari kelas kecil saya. Berbeda dengan Binary Search Tree ataupun AVL, dalam heap nilai yang dihapus SELALU ROOT. Setelah root dihapus maka, ARRAY TERAKHIR akan menggantikan posisi root. Kita tidak menggunakan predecessor ataupun successor. Setelah menjadi root, maka akan melakukan pengecekan dengan childrennya. Ini dapat disebut sebagai down heap atau heapify down. Bila nilai child lebih besar dari parent, maka akan melakukan balancing dengan cara menukar parent dengan child. Pengecekan ini dilakukan secara rekursif.

Pengertian Tries

Tries atau prefix tree adalah tree yang terurut yang dapat menyimpan data array, biasanya berupa strings ataupun char. Kata TRIE berasal dari kata RETRIEVAL karena tries dapat mencari satu kata dalam kamus hanya dengan kata awalan saja. Berikut adalah gambaran tries:

Refrensi:

1. https://www.google.com/url?sa=i&url=http%3A%2F%2Fbtechsmartclass.com%2Fdata_structures%2Ftries.html&psig=AOvVaw39rWJuHg1x0nZIGQLHTz8O&ust=1589618170135000&source=images&cd=vfe&ved=0CAIQjRxqFwoTCMj53aa7tekCFQAAAAAdAAAAABAD
2. Binus Maya