AVL Tree

AVL Tree

AVL adalah balanced binary search tree dimana ia memiliki perbedaan jumlah tinggi/level pada subtree kiri dan subtree kanannya maksimal 1 (atau dapat dikatakan antara tingginya sama atau selisih satu).

Berikut gambarannya :

AVL Tree, karena factor tertingginya 1

Not AVL Tree, karena  balance factor tertingginya 2, sedangkan syarat AVL adalah selisihnya maksimal 1

Note :

Cara menentukan Height dengan Balance Factor :

Height :
- Jika node (root) tidak memiliki subtree heightnya, maka = 0
- Jika node adalah leaf, height =  1
- Jika internal node, maka height =  height tertinggi dari anak + 1

Balance Factor :
-selisih height antara anak kiri dengan kanan, jika tidak memiliki anak, maka 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.

Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :

anggap O adalah node yang harus diseimbangkan kembali

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

Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi

- Kasus 1 dan 4 dengan single rotation
- Kasus 2 dan 3 dengan double rotation

Single Rotation

Single rotasi (rotasi 1x) dilakukan apabila satu arah (jika arah nya kiri ya kiri terus, begitu pula sebaliknya).

Gambaran Single Rotation :

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

Double Rotation

Double rotasi (rotasi 2x) dilakukan apabila satu arah tapi turunannya beda arah seperti contohnya, kiri kekanan atau kanan ke kiri.

Gambaran Double Rotation :

Step 1 (Rotasi pertama)
kasus diatas adalah left-right

Step 2 (Rotasi kedua)

kasus diatas, left-left

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 di 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 agar imbang. Cara seimbangnya pun sama seperti cara 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