Summary about linked list

Heap and Tries

Heap merupakan struktur data berbasis pohon biner lengkap yang memenuhi properti heap. Heap dapat diimplementasikan dengan menggunakan linked-list, tetapi lebih mudah untuk menggunakan array.

Min Heap
 node yang berada dibawahnya atau parent nilainya akan lebih kecil dibandingkan dengan node anaknya. Maka dapat disimpulkan node root merupakan node dengan nilai paling kecil , dan salah satu node dari leaf node merupakan node yang nilainya paling besar .
Max Heap
yang dimana node rootnya memiliki nilai paling besar di antara semua childrennya.
 contoh :

















Insertion dalam Min Heap:
Jika kita akan menginsert sebuah angka, maka kita harus meletakkan node tersebut di tempat setelah terakhir. Lalu, kita cek kondisi dengan parent nya, jika node tersebut lebih besar dari parent nya maka di swap, lakukan cara tersebut sampai root
contoh :

Insertion Max Heap :
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.

Deletion dalam Max Heap:
Jika kita akan menghapus suatu node, maka node yang akan menggantikan adalah node yang paling terakhir. Setelah itu cek kondisi dengan child nya, jika node tersebut lebih besar dari child nya maka di swap, lakukan cara tersebut sampai leaf 
Contoh :


Sedangkan untuk Min 
Tukar akar dengan anak/orang tua terakhir dari heap lalu hapus akar yang sudah berada di anak/orang tua terakhir tersebut. Downheapmin dari akar.

Tries

Tries sama saja dengan tree, anaknya bisa banian tetapi hanya digunakan untuk bentuk character atau string. Tries atau prefix tree adalah suatu pohon struktur data yang terurut yang menyimpan data array, biasanya string. Kata tries diambil dari kata RETRIEVAL, karena tries dapat menemukan kata tunggal dalam kamus dengan hanya awalan katanya saja.

Tries sudah diterapkan ke banyak hal dalam kehidupan sehari-hari, contohnya pada web browser. suatu web browser dapat mengira atau mensugestikan kata-kata yang mungkin kita maksud saat kita mengetik huruf pertamanya saja. (autocomplete).