AVL Tree

AVL Tree

AVL berasal dari nama penemunya Georgy Adelson-Velsky and Evgenii Landis .

AVL tree adalah salah statu jenis tree yang berasal dari BST, tetapi memiliki karakteristik khusus yaitu tree yang dihasilkan harus balance (seimbang).

Konsep AVL Tree

• Height untuk sub tree kosong yaitu 0.

• Height dari leaf adalah 1.

• Height dari node internal adalah max height dari anaknya ditambah 1.

Balance Factor merupakan selisih height dari anak kanan dengan anak kiri dari suatu node.
Agar seimbang, balance faktor tidak boleh lebih dari 1.

AVL Deletion

Deletion dalam AVL Tree sama seperti teknik deletion dalam binary search tree yang tidak seimbang.

• Jika yang di delete adalah leaf, langsung dihapus.
• Jika yang dihapus memiliki 1 anak, maka yang menggantikan adalah anaknya itu sendiri.
• Jika yang dihapus memiliki 2 anak, maka akan diambil anak terkanan dari subtree kiri.