AVL Tree Summary

AVL Tree

Adalah binary tree yang dapat menyeimbangkan diri sendiri. Hal ini agar tidak akan terbentuknya skewed binary search tree yang akan membuat proses searching binary tree tersebut lama

.

Agar tetap balance dalam AVL Tree terdapat peraturan yaitu kedalaman atau height subtree kiri dan kanan sebuah node dalam avl tree hanya boleh beda 1. Jika bedanya lebih dari 1 maka peraturan AVL Tree tersebut terlanggar. 

Berikut contoh gambar AVL Tree yang tidak seimbang

Dalam gambar diatas dapat dilihat bahwa node yang berisi 17 melanggar peraturan AVL Tree karena subtree kirinya memiliki height 2 sedangkan subtree kanannya heightnya 0. Sehingga perbedaan heightnya lebih dari 1.

Untuk membalance atau membenarkan AVL Tree yang sudah tidak seimbang maka terdapat 2 cara yaitu:

      1.  Single Rotation:

          

Ketika node yang melanggar peraturan AVL Tree ke arah node yang membuat tidak seimbangnya itu dua arah pertamanya lurus atau kiri dan kiri atau kanan dan kanan.

Berikut contoh gambar AVL Tree yang harus di single rotate

Cara kerja single rotation:

Tarik node yang melanggar peraturan AVL ke arah lawannya terdapat node yang membuat tidak seimbangnya tree tersebut. Sehingga child dari node yang ditarik tersebut menjadi rootnya dan disesuaikan child dari node-node tersebut. (Untuk membantu menyesuaikan child coba saja insert ulang child-child tersebut).

Berikut gambar proses Single Rotation:

2. Double Rotation:

 

Ketika node yang melanggar peraturan AVL Tree ke arah node yang membuat tidak seimbangnya itu dua arah pertamanya tidak lurus atau kiri dan kanan atau kiri dan kanan.

Berikut contoh gambar AVL Tree yang butuh Double Rotate:

Cara kerja Rotation  Pertama Double Rotation:

Tarik node ke dua dari node yang melanggar peraturan AVL tree kemudian sesuaikan dulu child nya. 
Berikut contoh gambar Proses Rotasi pertama pada Double Rotation:

 Cara kerja Rotation Kedua Double Rotation:
Setelah itu lakukan first rotation dan juga pastikan childnya sesuai agar AVL Tree nya seimbang.
 Berikut contoh gambar Proses Rotasi kedua pada Double Rotation: 

Deletion & Insertion:

Untuk proses Delete dan Insert pada AVL Tree masih sama seperti Binary Search Tree tetapi harus diperiksa subtree kiri dan kanan setiap node dari node yang di insert atau didelete hingga root untuk memastikan AVL Tree tetap seimbang.

Nama: Jordy Ferdian

Nim: 2301888524

Kelas: LP01

Demikian rangkuman saya untuk AVL Tree dari VC dan juga ppt Binusmaya. Mohon maaf jika ada kesalahan. Terima kasih.