AVL Tree

Pertemuan ke-(?),  AVL Tree 

Materi :

- Konsep AVL TREE

- Konsep-konsep Search, Insertion dan Deletion

AVL TREE

AVL Tree adalah sebuah "Binary Search Tree tahap berikut", dengan kata lain, AVL Tree adalah pematangan  dari konsep Binary Search Tree. AVL Tree dalam penempatan datanya akan terlihat persis sama seperti Binary Tree, namun pada saat penempatan data, AVL Tree melakukan langkah merapikan pohon, yang tidak dilakukan pada Binary Tree, sehingga data lebih efisien di AVL Tree. AVL Tree memiliki perbedaan tinggi maksimal 1 antara subtree kiri dan subtree kanan, bila perbedaan tinggi melewati 1, artinya sudah tidak seimbang dan akan dilakukan penyeimbangan. Hal ini dilakukan untuk mencegah sebuah situasi yang tidak baik yang bisa terjadi pada Binary Tree yaitu Skewed Tree.

 

AVL TREE : INSERTION

Insertion pada AVL Tree sama seperti Binary Tree (Apabila lebih besar ke kanan, lebih kecil ke kiri) kecuali AVL Tree memiliki Balance(Untuk mencegah Skewed Tree). Balance ini akan di sesudah insertion biasa seperti Binary Tree dilakukan. Bila tidak balance, akan diperbaiki agar balance.

Balance tersebut diperbaiki dengan teknik Rotation

- Single Rotation

- Double Rotation

AVL TREE : DELETION

Deletion di AVL Tree juga sama seperti Deletion pada Binary Search Tree, namun seperti teknik lainnya pada AVL Tree, konsep Balance adalah yang membedakan.

Sekian yang saya pelajari hari ini, maaf bila ada kesalahan kata dan terima kasih atas waktunya. 

REFERENSI

- VIDCON kelas besar data structures Binus

- PPT BINUS