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.
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:
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.
