AVL TREE

AVL Tree merupakan salah satu dari tipe binary search tree (BST) yang dapat menyeimbangkan dirinya sendiri. Maksud dari penyeimbangan diri sendiri adalah saat terjadi perbedaan height node kiri dan kanan yang melebihi satu (>1), maka node itu akan melakukan penyeimbangan. Lama proses AVL tree yaitu selama O(log n) time

Rotation

penyeimbangan dari tree yang menyalahi aturan AVL Tree dilakukan dengan rotation. tree yang menyalahi aturan bisanya terjadi saat melakukan insertion (tidak selalu).

Dapat dilihat di gambar bahwasanya tree yang memenuhi aturan AVL tree melakukan insertion yang yang berada pada node children sebelah kanan daripada node (40). Hal ini menyebabkan terjadi ketidakseimbangan height kiri dan kanan dari root, yaitu node (30). karena itu dilakukan rotation dengan 30 sebagai pivotnya. Hal ini disebut sebagai single rotation.

Bagaimana dengan contoh yang ini? 

Node (26) di insert ke dalam tree dan menyebabkan ketidakseimbangan.  maka dilakukan rotation dengan node (22) sebagai pivotnya.

Dapat dilihat masih terjadi violation terhadap aturan AVL tree. Karena itu, dilakukanlah rotation sekali lagi dengan node(30) sebagai pivot. Hal ini disebut sebagai double rotation

Sekarang tree sudah memenuhi kriteria AVL tree. dapat dilihat ada perbedaan-perbedaan tergantung dari case tree yang ada.

Case

Case terdiri dari 4, yaitu:

1. Left left
2. Right right
3. Left Right
4. Left Right

(1) left left dan (3) left right

(2) Right left dan (4) right left

pada kasus left left/right right dilakukan single rotation, sedangkan pada Left right/Right left dilakukan double rotation. Cek path dari parent node yang didelete ke root dari tree yang ada. kalau tidak ada unbalance, lanjut ke parent yang selanjutnya. Kalau tidak, perbaiki sub tree, baik dengan single rotation atau dengan double rotation.

Deletion

Deletion akan menyebabkan parent dari node yang di delete menjadi leaf atau node dengan satu child.

example:

Node (60) didelete, menyebabkan terjadinya unbalance. node (55) menjadi node dengan single child  

lakukan single rotation pada node (55) karena ada unbalance. cek apakah node (65) ada unbalance. kalau tidak, pergi ke parentnya yaitu node (50)

Terdapat unbalance pada node (50). karena casenya merupakan left right, maka lakukan double rotation pada node (50). rotate pertama dengan node (25) sebagai pivotnya. setelah itu, rotate node (50). Hasil akhirnya akan seperti ini:

Demikian rangkuman saya dari materi yang diberikan pak Ferdinand minggu lalu. materi yang disampaikan dan yang saya tulis adalah konsep AVL, insertion, rotation, jenis case, dan yang terakhir adalah deletion. Terima kasih :)

Source:

-PPT AVL tree Universitas Bina Nusantara

-catatan saat VC AVL tree