Heaps and Tries

Heaps 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. Heap dibagi menjadi dua macam yaitu :

-Max Heap
yang dimana node rootnya memiliki nilai paling besar di antara semua childrennya.
contoh max heap :

-Min Heap
yaitu node rootnya memiliki nilai paling kecil di antara semua childrennya.
contoh min heap :

insertion and deletion in Heap

deletion di heap merupakan penghapusan pada simpul root. Jika itu max heap maka yang dihapus adalah node yang mempunyai nilai paling besar. Sedangkan deletion di min heap adalah penghapusan node yang memiliki nilai paling kecil.

untuk insertion dalam heap, yaitu dengan :
1. menambahkan elemen baru di akhir array
2. lalu membandingkan nilai node tersebut dengan nilai parent, jika mereka salah urutan tukar mereka.

Tries adalah dtruktur data yang digunakan untuk menyimpan array asosiatif. tries adalah struktur data yang simpulnya menyimpan huruf-huruf alfabet. 



Comments

Post a Comment

Popular posts from this blog

AVLdanBtree

Image
AVL dan Btree AVL TREE AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Ketinggian subtree kosong adalah 0. Tinggi daun adalah 1. Ketinggian simpul internal adalah ketinggian maksimum anak-anaknya ditambah 1. Faktor keseimbangan semua node di pohon AVL harus paling banyak 1.  Operasi pada AVL : - insertion  insert node baru pada bst, dimana node baru diposisikan sebagai leaf. Setelah itu, dilakukan penyeimbangan pada path dari node yang baru diinsert. - deletion node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Selain itu, terdapat single rotation dan double rotation. Single rotation merupakan rotasi sekali left ke left atau right ke right. Sedangkan double rotation merupakan dua kali rotasi dengan left-right ataupun sebaliknya. Btree Akar Btree paling sedikit me...
Read more