AVL TREE

BST dalam worst case bisa sampai O(n) yaitu kita melakukan pencarian sebanyak n data dalam kasus tertentu, yaitu skewed BST tree

Kalau kita ingin mencari angka 13 kiri kita harus melakukan rekursif / looping sebanyak 4 kali, padahal jumlah data ada 5. hal ini membuat boros waktu O(n)





- Jadi diperlukan cara untuk membuat BST menjadi Balanced Binary Search Tree dengan meminimalkan height / tinggi treenya , salah satunya adalah AVL Tree
- Tujuannya adalah untuk mempercepat pencarian dengan mempertahankan tree sekitar O(log n)

Ketentuan AVL Tree :
a. Balance factor
- selisih tinggi child kiri dan kanan harus paling banyak 1

Contoh AVL Tree

angka hitam adalah tinggi dari node

angka merah adalah balance factor dari setiap node

Node angka 17 memiliki left child yang memiliki tinggi 2, sedangkan tidak ada right child.
sehingga balance factornya adalah 2 - 0, 0
karena balance factornya lebih dari 1, BST ini tidak dapat disebut dengan AVL tree






Insertion pada AVL Tree

- insert key baru layaknya BST
( namun dapat membuat kerusakan pada AVL tree, seperti yang terjadi pada Node angka 3, setelah di insert 4 )
- restore / mengembalikan kondisi balance ( balance position )

Rebalancing AVL Tree
- agar AVL Tree tetap balance / seimbang, perlu dilakukan rebalancing setiap melakukan insert node

ada 4 case dalam melakukan rebalancing
anggap node yang ingin di rebalance adalah node T
1. node terdalam terletak di left sub tree dari left child T
2. node terdalam terletak di right sub tree dari right child T
3. node terdalam terletak di right sub tree dari left child T
4. node terdalam terletak di left sub tree dari right child T
karena dalam insertion, node yang di insert adalah node paling bawah

Rebalancing AVL Tree menggunakan rotation
1. Single rotation berlaku untuk kerusakan / ketidakseimbangan case 1 dan 2
2. double rotation berlaku untuk kerusakan case 3 dan 4

Insertion
- setiap kita melakukan insertion kita harus mengecek dari bawah apakah ada terjadi ketidakseimbangan, jika ada harus di rebalancing

jenis jenis rotation :
1. LL rotation, untuk menyelesaikan case 1

kita lakukan rotasi S dan T, sehingga T menjadi right childnya S. sedangkan right child S dipindahkan menjadi left childnya T.
namun apabila menghapus b dan menginsertkan lagi akan berada di left dari T, jadi sama saja

2. RR rotation, untuk menyelesaikan case 2

Kita lakukan seperti kebalikan dari case 1, node T jadi left child S. left childnya S ditempel ke rightnya T

--Contoh single rotation

Dalam kasus ini, node 30 memiliki balance factor 2, sehingga terjadi violation

Karena node terdalam ada di left sub dari child 30, makanya terjadi kasus 1

jadi kita tinggal melakukan LL (left left) rotation pada node 22 dan 30

Untuk LR dann RL harus dengan double rotation
3. LR (left right) rotation

4. RL ( RIght left ) rotation
Merupakan kebalikan dari LR rotation

Contoh dari double rotation

Deletion pada AVL Tree
seperti deletion pada BST, namun kita perlu melakukan checking dan rebalancing pada tree, dari bawah hingga root



Setelah mendelete node 60, node 55 akan unbalance

RR rotation pada node angka 55

lalu lakukan double rotation untuk melakukan balancing pada root

AVL Tree setelah mendelete node 60