Data Structure: AVL Tree

Pengertian AVL Tree

AVL Tree ditemukan oleh Adelson-Velskii dan Landis. AVL Tree merupakan salah satu jenis BST (binary Search Tree). Apabila BST yang terbentuk cukup seimbang (mendekati complete binary tree) maka waktu pencarian data tidak lebih dari log2n langkah.

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.

Contoh gambar AVL Tree:

Single Rotation:

Jika suatu Tree diinsert node baru dengan nilai 12, maka akan terjadi ketidak seimbangan dan hal ini terletak pada posisi root.
contoh:

Double Rotation:

Node (26) dimasukkan dalam pohon AVL dan menyebabkan node (30) untuk melanggar properti AVL.
Contoh:

Rotasi kedua, node (27) dan node (30).

Delete dalam AVL Tree

Delete Node sama seperti Binary Search Tree. Node yang dihapus akan menjadi leaf atau node yang memiliki 1 child.

Untuk melakukan delete lihat dari parent, untuk setiap node P yang ditemui, periksa apakah tinggi parent(P) kanan dan parent(P) Kiri berbeda paling banyak 1.

Jika iya, lanjutkan ke parent(P).
Jika tidak, perbaiki sub-tree (P) baik dengan Single Rotation ataupun Double Rotation.

Setelah melakukan rotasi di parent(P), mungkin juga harus melakukan rotasi pada parent sebelumnya. Dengan demikian kita terus melacak path sampai mencapai root.

Contoh:

Hapus Node (60), Node (55) tidak seimbang.