AVL Tree

AVL Tree dinamai menurut 2 penemunya yaitu G.M. Adelson Veleskii and E.M. Landis. AVLtree adalah binary search tree (BST) yang secara otomatis menyeimbangka tangan kiri dan tangan kanan. Perbedaan tinggi antara tangan kanan dan tangan kiri dari AVL tree tidak boleh lebih dari satu untuk semua node.
Operas yang terdapat dalam AVL Tree  :

I. 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.

Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :
anggap T adalah node yang harus diseimbangkan kembali

- Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
- Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
- Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
- Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi
- Kasus 1 dan 2 dengan single rotation
- Kasus 3 dan 4 dengan double rotation

->Single rotasi (rotasi 1x) dilakukan apabila searah, left-left atau right-right

pada contoh diatas, left-left karena dari 30 ke 22 ke kiri, dan dari 22 ke 15 ke kiri juga

->Double rotasi (rotasi 2x) dilakukan apabila searah, left-right atau right-left.

Step 1 (Rotasi pertama)

kasus diatas adalah left-right

Step 2 (Rotasi kedua)

kasus diatas, left-left

II. 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.

delete node 60

node 55 tidak seimbang, karena anak kiri 0 dan anak kanan 2, selisih 2.

diseimbangkan dengan single rotation (left-left) karena 55 ke 65 kiri dan 65 ke 70 kiri

akan tetapi, node 50 menjadi tidak seimbang, di subtree kiri 4 dan subtree kanan 2

diseimbangkan dengan double rotation (left-right) karena dari 50 ke 25 kiri dan 25 ke 40 kanan

AVL yang sudah balance