AVL Tree

AVL Tree adalah Subtype dari Binary Search Tree (BST) dimana tree ini dapat melakukan Self-Balancing.

AVL Tree memiliki ciri-ciri yang sama dengan BST dengan tambahan yaitu beda kedalaman antara subtree kiri dan subtree kanan tidak boleh lebih dari 1 tingkat.

Pada Tree yang pertama dan ketiga (kiri dan kanan) termasuk AVL tree karena sesuai dengan aturan yaitu beda kedalaman antara subtree kiri dan subtree kanan tidak lebih dari 1 tingkat. sedangkan pada tree yang kedua (tengah) bukan merupakan AVL karena node 2 memiliki beda kedalaman 2, subtree kiri memiliki kedalaman 3 sedangkan subtree kanan hanya memiliki kedalaman 1 sehingga beda kedalamannya adalah 2 tingkat, hal ini tidak sesuai dengan aturan AVL tree.

Insertion dan Deletion pada AVL Tree

Untuk melakukan Insertion dan Deletion pada AVL Tree dapat dilakukan sama seperti melakukan Insertion dan Deletion pada BST, hanya saja setiap melakukan insertion atau kita wajib melakukan pengecekan beda kedalaman. Jika ada yang tidak sesuai dengan aturan AVL tree maka harus dilakukan perubahan pada AVL tree.
Contoh : Insertion

Pada Tree ini kita melakukan insert 2,1,9,3,10 dan yang terakhir 17, semua insert pasti tidak akan terjadi masalah kecuali pada insert 17 karena setelah dilakukan pengecekan ternyata beda kedalaman di kiri dan kanan dari node 2 adalah 2 tingkat, hal ini melanggar aturan AVL tree.

Untuk memperbaiki ini kita akan melakukan rotasi ke kiri dengan poros di node 2 sehingga 9 menjadi root, 2 menjadi subtree kiri 9, 10 menjadi subtree kanan 9 dan 3 akan menjadi subtree kanan 2 seperti gambar berikut.