Heaps & Tries

Heaps adalah salah satu bentuk tree yang memenuhi syarat heap, yaitu anak dari sebuah node, maka node tersebut nilainya harus lebih besar atau sama dengan anak node tersebut disebut max-heap. jika anak node lebih besar atau sama dengan node tersebut maka disebut min-heap. gabungan dari kegunaan max-heap dan min-heap disebut dengan min-max heap dimana dalam baris node atas lebih kecil dari node bawahnya lalu node bawahnya lagi lebih besar dan seterusnya.

Tries adalah pohon struktur data yang terurut yang menyimpan data array. Penggunaan tries biasanya digunakan pada web browser dalam bentuk autocomplete dan juga melakukan autocorrect. pada tree ini, node yang berada di paling atas menjadi huruf awal dan node anaknya menjadi huruf-huruf berikutnya

Rangkuman AVL Tree

AVL Tree adalah salah satu bentuk dari Binary Search Tree. Yang menyebabkan AVL Tree berbeda adalah AVL Tree memiliki perbedaan tinggi antara subtree kiri dengan kanan maksimal satu atau perbedaan tingginya bisa memiliki tinggi yang sama. Hal ini untuk mempersingkat waktu pencarian serta mempersingkat dan menyerdehanakan bentuk tree.

Insertion 

Seperti Binary Search Tree pada umumnya, AVL Tree juga memiliki operasi insertion, bedanya terletak pada jenisnya. Terdapat 2 jenis Insertion yaitu : 

1. Single Rotation

operasi insertion ini bisa dilakukan pada node terdalam pada subtree kiri dan anak kiri dan juga pada subtree kanan dan anak kanan ( operasi ini dilakukan jika memasukan node pada tree yang berurutan seperti gambar diatas)

2. Double Rotation 

operasi insertion ini dilakukan pada node terdalam pada subtree kiri dan anak kanan serta subtree kanan dan anak kiri. 

Deletion 

untuk menghapus node pada AVL Tree memiliki kasus yang serupa dengan Binary Seach Tree yang normal, yaitu : 

a. jika node yang akan dihapus terletak pada leaf (node tanpa anak) maka akan langsung terhapus

b. jika node yang akan dihapus terletak pada node dengan anak maka harus diseimbangkan dengan menyesuaikan tinggi dengan perbedaan 1 tinggi dengan menggunakan single atau double rotation