Heap dan Tries

Heap

Merupakan data structur yang berdasarkan tree (binary tree) yang memenuh ketentuan-ketentuan tertentu (ketentuan heap). Salah satu ketentuan heap yaitu selalu ada level terakhir yang diisi NULL.

Heap dibagi menjadi 3, yaitu min-Heap, max-Heap, dan MinMax-Heap.

Min-Heap

Min-heap adalah heap yang disusun dari kecil ke besar. Disusun kecil ke besar artinya setiap node meliki nilai yang lebih kecil dari pada childnya. Ini berarti nilai terkecil berada pada root dan nilai yang terbesar berada pada salah satu leaf di level yang terakhir.

Max-Heap

Min-heap adalah heap yang disusun dari besar ke kecil. Disusun besar ke kecil artinya setiap node meliki nilai yang lebih besar dari pada childnya. Ini berarti nilai terbesar berada pada root dan nilai yang terkecil berada pada salah satu leaf di level yang terakhir.

Tries

Tries adalah sebuah tree yang tiap leafnya menyimpan sebuah character. Biasanya root diberi char kosong ("") karena tidak digunakan nilainya. Implementasi tries antara lain untuk auto-complete dan search engine dan lainnya.

Contoh tries:

                                  ""
                                   |
                                   R
                                 /  |
                              U   E
                              /     |  \
                           N     A   S
                                    |      \
                                   L      T

kata: RUN, REAL, REST

AVL tree

AVL tree adalah pengembangan dari binary tree yang nantinya tree akan dapat self balancing.

Penamaan AVL tree diambil dari penemunya yang adalah Georgy Adelson-Velsky dan Landis.


Tree dinyatakan balance jika ketinggian anak kiri dan kanan sama atau setidaknya berselisih 1.


Self balancing dari AVL tree sendiri pada dasarnya dilakukan dengan rotasi. Rotasi yang digunakan tergantung dari posisi node mana yang tidak balance dan lurus atau tidaknya node yang tidak balance dilihat dari root..

Ada 2 jenis rotasi untuk menyeimbangkan tree yaitu, Single Rotate dan Double Rotate.

Single Rotate digunakan jika untuk ke node yang tidak balance dari root adalah lurus.

Double Rotate digunakan jika untuk ke node yang tidak balance dari root adalah tidak lurus

First rotation

Second rotation

Source : PPT