Heap & Tries

Heap & Tries

Heap

• Adalah struktur data yang berbentuk pohon yang memenuhi sifat-sifatnya, yaitu jika B adalah anak dari A, maka nilai yang tersimpan di node A lebih besar atau sama dengan nilai yang tersimpan di node B.
• Heap terbagi menjadi 2 yaitu:
1. Min Heap, setiap elemen node adalah lebih kecil daripada childrennya. Ini menunjukan bahwa elemen terkecil terletak pada root dari tree. Unsur terbesar adalah terletak di suatu tempat di salah satu node leaves.
2. Max Heap, setiap elemen node adalah lebih besar daripada childrennya. Karena urutan sibling dalam heap tidak ditentukan oleh sifat heap, dua node tunggal anak-anak bisa secara bebas dipertukarkan.
   
• Sifat dari Heap: 
• Setiap node lebih besar dari atau sama dengan masing-masing anak sesuai dengan perbandingan predikat yang ditetapkan untuk struktur data.

Tries

• Adalah Binary Tree dimana didalamnya terdapat kumpulan dari kata-kata. Tree ini dibuat untuk mempermudah pencarian suatu kata-kata (biasanya digunakan pada saat pembuatan fitur search pada kamus).
  

Sumber:

https://furqonubd.wordpress.com/2013/05/24/heap/

https://www.share28s.com/2019/08/pengertian-dan-contoh-soal-pada-heap.html

http://alkarmany.blogspot.com/2013/05/heap-pengertian-heap-adalah-struktur.html

http://apalah-ini-itu.blogspot.com/2011/06/heap.html

https://www.it-swarm.dev/id/algorithm/apa-perbedaan-antara-struktur-data-trie-dan-radix-trie/1071455430/

AVL Tree

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. Dengan AVL Tree, waktu pencarian danbentuk tree dapat dipersingkat dan disederhanakan. Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru→root. Node pertama yang memiliki balance factor > 1 diseimbangkan. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan. 

• Proses penyeimbangan dilakukan dengan: 
1. Single rotation adalah rotasi yang dilakukan apabila data yang diinsert searah, left-left atau right-right.
   
2. Double rotation adalah rotasi yang dilakukan apabila data yang diinsert tidak searah, left-right atau right-left.
   
• Operasi pada AVL:

1. Insertion atau insert suatu node pada AVL sama halnya pada insert node pada binary search tree, dimana node baru diposisikan sebagai leaf. Setelah memasukkan node baru, maka harus dilakukan penyeimbangan kembali pada path dari node yang baru di insert atau path terdalam.
   
2. Deletion yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus adalah leaf, maka langsung hapus saja. Namun jika node yang dihapus memiliki child maka childnya yang menggantikannya. Namun setelah operasi penghapusan dilakukan, cek kembali apakah tree sudah seimbang atau belum, jika belum maka harus diseimbangkan kembali. 
   
   
   

Sumber: 

http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html?m=1

http://suciantinovi.blogspot.com/2014/05/balanced-binary-tree-and-2-3-tree.html

https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor/