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
- 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).
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).
- 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
Comments
Post a Comment