Heap & Tries

Heap & Tries

Heap

heap adalah struktur data yang bisa dibilang sama atau mirip dengan Binary Search Tree (BST), namun bedanya adalah heap merupakan Complete Binary Tree yang memiliki persyaratannya sendiri. Heap dibagi menjadi 3 yaitu :

• Min Heap 
• Max Heap
• Min-Max Heap

1. Min Heap

Setiap node dalam Min Heap lebih kecil dari masing-masing child nya dan root merupakan node paling kecil.

Insertion : 

• Insert Node baru
• Check parent
• Jika nilai node baru tersebut lebih kecil dibandingkan parent, tukar posisinya dengan parent.

Deletion : 

• Yang dihapus merupakan rootnya (elemen terkecil).
• Root yang dihapus tersebut kemudian digantikan oleh data terakhir di nodenya, kemudian data tersebut di downheapmin(jika anak < data tsb, maka tukar,dst sampai mentok dibawah atau node tsb<anaknya).

2. Max Heap

Setiap node dalam Max Heap lebih besar dari masing-masing child nya dan root merupakan node paling besar

Insertion : 

• Insert Node baru
• Check parent
• Jika node baru bernilai lebih besar dibandingkan parent, tukar posisinya dengan parent.

Deletion : 

• Yang dihapus merupakan rootnya (elemen terbesar).
• Root yang dihapus tersebut kemudian digantikan oleh data terakhir di nodenya, kemudian data tersebut di downheapmax(jika anak > data tsb, maka tukar,dst), sampai mentok dibawah atau node tsb>anaknya).

3. Min-Max Heap

Pada Min-Max Heap, root akan bernilai minimum, selanjutnya child dari root akan bernilai maksimum, dan seterusnya. Nilai terkecil berada di root dan nilai terbesar berada di salah satu node pada level setelah root. Level min hanya dapat dibandingkan dengan level min, dan sebaliknya.

Insertion dan Deletion sama seperti Min Heap atau Max Heap namun, pengecekan kondisi hanya dapat dilakukan di level sesama min atau max

Tries

Tries merupakan tree yang berfungsi untuk menyimpan array

• root mempresentasikan karakter kosong/null
• node lainnya mempresentasikan satu huruf