Data Structure (Conclusion)
Balanced Binary Search Tree (BBST) –> Merupakan salah satu jenis Binary Tree yang lebih teratur dibandingkan Binary Search Tree (BST) sendiri. Dibuat dengan beberapa macam cara tetapi memiliki fungsi yang sama yaitu mempermudah proses pencarian, mempersingkat waktu pencarian dan menghemat tempat.
AVL Tree (Adelson – Veleskii and E. M. Landis) – 1962
Merupakan Self – BBST pertama yang pernah ada
Berdasarkan gambar di atas, angka di dalam tanda kurung () merupakan Balancing Factor dimana balancing factor ini merupakan hasil selisih height dari anak kiri dengan anak kanan parent-nya.
Balancing Factor pada AVL Tree sendiri memiliki batas maksimum sebesar 1.
Jika balancing factor lebih dari 1, maka disebut violating (Melanggar).
Berikut adalah beberapa jenis violation dalam AVL Tree :
- LL Violation (Left – Left) –> Binary Tree tidak seimbang, dan lebih panjang ke arah kiri.
- RR Violation (Right – Right) –> Binary Tree tidak seimbang, dan lebih panjang ke arah kanan.
- LR Violation (Left – Right) –> Binary Tree tidak seimbang, dan lebih panjang ke arah kiri – tengah.
- RL Violation (Right – Left) –> Binary Tree tidak seimbang, dan lebih panjang ke arah kanan – tengah.
Dari ke-4 violation diatas, dapat kita selesaikan dengan 2 solusi berikut :
- Single Rotation : Dengan memutar Binary Tree 1 kali
(Digunakan untuk menyelesaikan LL dan RR Violation)
- Double Rotation : Dengan memutar Binary Tree 2 kali
(Digunakan untuk menyelesaikan LR dan RL Violation)
Posted by: dennisht
Categories:
Uncategorized