AVL Tree

Pendahuluan

AVL tree adalah pohon pencarian biner di mana perbedaan ketinggian subtree kiri dan kanan dari setiap node kurang dari atau sama dengan satu. AVL tree muncul untuk menyeimbangkan Binary Search Tree. Teknik menyeimbangkan ketinggian pohon biner dikembangkan oleh Adelson, Velskii, dan Landi dan karenanya diberi bentuk pendek sebagai AVL tree atau Balanced Binary Tree.

Contoh Gambar AVL tree:


Contoh gambar yang bukan AVL tree :

Gambar di atas bukan AVL tree karena perbedaan antara ketinggian subtree kiri dan kanan untuk 8 dan 18 lebih besar dari 1.

Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan.

|Balance Factor| = |height (left subtree) - height (right subtree)| 

Proses penyeimbangan dilakukan dengan: Single rotation dan Double rotation.

Single Rotation

Single rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar 2. T1, T2, dan T3 adalah subtree yang urutannya harus seperti demikian serta heightnya harus sama (≥ 0).

Double Rotation

Double rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar 3. T1, T2, T3, dan T4 adalah subtree yang urutannya harus seperti demikian. Tinggi subtree T1 harus sama dengan T4 (≥ 0), tinggi subtree T2 harus sama dengan T3 (≥ 0). Node yang ditambahkan akan menjadi child dari subtree T2 atau T3.

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.

Contoh :

1. Delete node 60 : 

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

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

4. AVL Tree sudah balance / seimbang.