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