Apa itu AVL Tree ??
AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.
Gambar BST
digambar tersebut sudah menjadi AVL Tree, Tree sudah sesuai dengan syarat menjadi AVL Tree, Tree nya sudah balance antara satu dan lain.
Untuk memeriksa Tree tersebut sudah balance atau tidak, dengan cara [balance faktor] > 1, ditiap node di cek kedalamnya, digambar node 7 sisi kiri 2 dan sisi kanan 3, maka antara sisi kiri dan kanan dikurangkan kedalam nya (3-2= 1) , nah selanjutnya cek masing-masing node tree ya, apakah tidak >1 jika iya semua 1 atau 0 maka sudah di sebut AVL Tree
di AVL Tree ada 2 cara rotation dalam mencari balance Tree:
1. Single Rotation
a. Left Left Rotation
b. Right Right Rotation
contoh Single Rotation
a. Right Left Rotation
b. Left Right Rotation
Left-Right
Right-Left
Delete node di AVL Tree
Delete node di AVL Tree sama percis dengan Binary Search Tree, yaitu node yang dihapus digantikan oleh node tersebar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus leaf maka langsung di hapus. Namun jika node yang ingin di hapus memiliki anak maka anaknya yang menggantikannya. Pada saat delete pun harus di cek kembali, apakah tree tersebut sudah balance atau tidak. Jika belum maka lakukan proses Rotation.
referensi :
PPT : Binus (Data Structure)
