AVL Tree

Balanced Binary Tree

Balanced Binary Tree adalah Tree yang memiliki minimal ketinggian root ke leaf-nya pada BST agar mencegah terjadinya kegagalan tree yaitu, skewed BST (yang datanya kekanan semua atau kekiri semua)

AVL Tree

Dinamakan berdasarkan 2 penemunya yaitu Adelson-Veleskii dan E.M. Landis

1. Menentukan Height:
- Height dari tree yang kosong adalah 0.
- Height dari sebuah node tanpa anak adalah 1.
- Height ditentukan dari height anaknya tertinggi (antara anak kiri dan anak kanan) lalu +1.

2. Menentukan Balanced factor:
- Dengan mencari perbandingan height anak kiri dan kanan (height anak kiri - height anak kanan atau sebaliknya).
- Dan disebut balance apabila nilainya tidak lebih dari 1 dan tidak kurang dari -1.

3. Insertion
- Insertnya seperti BST pada umumnya yaitu insert jika ada head dia akan mengecek apakah lebih kecil atau lebih besar dari head ? bila lebih kecil ke kiri dan apa bila lebih besar ke kanan.
- Namun ada yang membedakan yaitu harus disertakan rebalance

berikut beberapa case rebalance :
Misal A adalah node yang harus di rebalance.
Case 1 : node yang akan dimasukkan terletak di subtree kiri dari anak kiri si A.
Case 2 : node yang akan dimasukkan terletak di subtree kanan dari anak kanan si A.
Case 3 : node yang akan dimasukkan terletak di subtree kanan dari anak kiri si A.
Case 4 : node yang akan dimasukkan terletak di subtree kiri dari anak kanan si A.

Rotasi yang dilakukan saat rebalance :
- Single Rotation:
LL rotation: bentuk ke kiri dari root dan salahnya pada anak kirinya.
RR rotation: bentuk ke kanan dari root dan salahnya pada anak kanannya.
-Double Rotation:
LR rotation: bentuk ke kanan dari root dan salahnya pada anak kirinya.
RL rotation: bentuk ke kiri dari root dan salahnya pada anak kanannya.

4. Deletion
- Deletion di AVL tree seperti deletion BST yang mengambil antara successornya atau predecessornya
- Namun ada tambahan lagi bagi AVL karena setelah melakukan deletion ada kemungkinan bahwa treenya menjadi tidak balance lagi, maka dari itu kita haru melakukan rebalance kembali setelah melakukan deletion.

Sekian dari saya tentang materi AVL tree, jika ada yang mau ditanyakan silahkan comment.