AVL adalah versi lanjutan dari BST yang mana menutup kekurangan dari BST. AVL bertujuan untuk menyeimbangkan sub tree dalam BST yang tidak seimbang kanan dan kiri nya. AVL memiliki 2 cara untuk menutup worstcase dari BST, cara ini disebut juga dengan rebalancing.
cara pertama ialah single rotation, cara ini merotate arah sebalik nya dari worst case BST seperti node tersusun secara linear sebanyak 3 level sehingga terlihat seperti linklist. Algoritma ini menyusun BST yang linear menjadi full binary tree. Cara nya dengan mengankat node di level 1 ke level 0 menjadi parent lalu node parent menjadi anak kiri dari node level 1 tadi dan anak kanan node level 1 tadi tetaplah anak kanan nya sendiri
cara kedua ialah double rotation, cara ini merotate 2 kali sub tree. worstcase BST seperti zigzag. Algoritma double rotation adalah lanjutan daru single rotation. Langkah pertama subtree dibuat sedemikian hingga lurus seperti linked list lalu node paling bawah akan menjadi parent dan parent sebelum nya akan menjadi anak kiri dan node kanan nya ialah parent dari node paling bawah tersebut.
Berikut adalah simulasi dari kasus yang biasa terjadi
Single Rotation :
Left Left
Right Right
Left Right
Double Rotation :
Right Left
Tidak ada komentar:
Posting Komentar