AVL Tree

 

AVL Tree berasal dari nama penemunya yaitu Adelson, Velski & Landis, yang merupakan tree yag digunakan untuk membalance binary search tree. AVL tree mengecek ketinggian dari sub-tree / leaf kiri dan kanan dan memastikan bahwa perbedaan tinggi tidak lebih dari 1. Perbedaan ini disebut Balance Factor.

Pada tree kedua dikatakan tidak balance dikarenakan sub-tree kiri dari C itu 2 dan sub-tree kanannya adalah 0, jadi perbedaan tingginya adalah 2, maka melanggar syarat balance factor. Jika masalah seperti ini terjadi, maka AVL tree mempunyai beberapa teknik untuk menyelesaikan masalah tersebut yang dinamakan AVL Rotation. 

Contoh perbaikan dari no-AVL tree ke AVL tree :

Terdapat 2 kasus dalam insertion AVL balancing yang menyebabkan diperlukannya menggunakan salah satu teknik rotasi :

Insertion

1. Single Rotation

Jika node yang menyebabkan tidak balance itu berupa kiri - kiri

Jika dilihat dari gambar diatas, T1 menyebabkan pelanggaran balance factor terhadap node z dikarenakan selisih sub-tree kiri kanan dari z adalah 2, maka untuk memperbaikinya harus dilakukan penarikan z ke kanan dan T3 menjadi sub-tree z.

2. Double Rotation

Jika node yang menyebabkan tidak balance itu berupa kiri - kanan

Jika dilihat dari gambar diatas, T3 menyebabkan pelanggaran balance factor terhadap node z dikarenakan selisih sub-tree kiri dan kanan z adalah 2, maka untuk memperbaikinya harus dilakukan penarikan y ke kiri dan T2 menjadi sub-tree y. Dikarenakan masih belum balance pada node z dilakukan rotasi sekali lagi.

Deletion

Terdapat 2 jenis kasus dalam penghapusan suatu node dalam AVL tree:

1. Jika node yang ingin dihapus merupakan node yang tidak memiliki sub-tree lalu dilakukan pengecekan kembali balance factor.

2. Jika node yang ingin dihapus memiliki sub-tree sehingga harus mencari successor atau predecessor untuk menggantikan node tersebut, lalu dilakukan pengecekan kembali balance factor.

Gambar diatas merupakan salah satu kasus yang dalam proses deletion pada suatu node yaitu kasus pertama. Maka node (30) langsung dihapus karena tidak terdapat sub-tree dan dilakukan pengecekan balance factor. Ternyata selisih sub-tree kiri dan kanan node (20) lebih dari satu. Maka node (20) ditarik ke kiri sehingga node (10) menjadi node paling awal dan node (15) berpindah menjadi sub-tree kiri node (15).

Reference ; https://algorithms.tutorialhorizon.com/avl-tree-insertion/