AVL Tree

AVL tree adalah nama berasal dari dua penciptannya yaitu, G.M. Adelson-Veleskii and E.M. Landis. AVL tree adalah self-balancing binary search tree pertama yang pernah diciptakan. AVL tree digunakan untuk menyeimbangkan Binary Search Tree, untuk mempersingkat pencarian dan menyederhanakan bentuk tree.

Contoh:

Insertion di AVL Tree

Insertion pada AVL tree adalah insertion biasa seperti yang digunakan pada binary search tree. Tetapi ini dapat menyebabkan pelanggaran pada properti AVL Tree. Setelah melakukan insertion biasa maka kita harus benarkan menjadi kondisi yang seimbang.

Selanjutnya, kembalikan kondisi keseimbangan. Pertama, lacak jalur dari kunci baru menuju root. Untuk setiap node yang A lewati, periksa apakah ketinggian kiri A dan kanan A berbeda pada paling banyak 1. Jika ya, lanjutkan ke parent A. Jika Tidak, perbaiki sub pohon A baik dengan single rotation atau double rotation.

Single Rotation

Single rotation dilakukan jika searah (left-left atau right-right)

Double Rotation

Double rotation dilakukan jika tidak searah (left-right atau right left)

Rotasi pertama

Rotasi kedua

Delete di AVL tree

Hapus node seperti pada Binary Search Tree biasa. Node yang dihapus akan berupa leaf atau node dengan satu child. Lacak jalur dari parent dari leaf yang dihapus ke arah root. Untuk setiap node yang A lewati, periksa apakah ketinggian kiri A dan kanan A berbeda paling banyak 1. Jika ya, lanjutkan ke parent A. Jika tidak, perbaiki sub pohon A dengan single rotation atau double rotation. Setelah kita melakukan rotasi pada A, kita mungkin harus melakukan rotasi pada beberapa ancestor A. Jadi, kita harus terus melacak jalan sampai kita mencapai root.