AVL TREE

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


AVL Tree : 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 Rotation
Single rotasi (rotasi 1x) dilakukan apabila searah, left-left atau right-right

Gambaran 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 searah, left-right atau right-left.
Gambaran Double Rotation :



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



Step 2 (Rotasi kedua) kasus diatas, left-left.

AVL Tree : Delete

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.