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. 

AVL TREE

AVL TREE

AVL TREE

A. Pengertian

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 dan bentuk tree dapat dipersingkat dan disederhanakan. Selain itu terdapat 2 proses penyeimbangan pada AVL Tree yaitu dengan cara Single rotation dan Double rotation.

B. Single Rotation

Single rotation adalah rotasi yang di lakukan hanya sekali agar sebuah tree AVL cara ini dapat menyelesaikan kasus luar.
Double rotation adalah rotasi yang dilakukan lebih dari sekali dan sedangkan cara ini untuk menyelesaikan kasus dalam.

Cara menentukan Height dan Balance Factor :Note :

Height :

– Jika node (root) tidak memiliki subtree heightnya = 0

– Jika node adalah leaf, height =  1

– Jika internal node, maka height =  height tertinggi dari anak + 1

Balance Factor :

-selisih height antara anak kiri dan kanan, jika tidak memiliki anak, dianggap 0.

AVL Tree Operations : Insertion

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. Namun biasanya, path terdalam adalah path dari node yang baru saja di insert.

AVL Tree Operations : Deletion

Operasi penghapusan node sama seperti pada Binary Search Tree, 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. Cara menyeimbangkannya pun sama seperti insertion.

http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html
https://sikisik.wordpress.com/struktur-data/
https://strukturdata2015.wordpress.com/2015/12/01/week12/