AVL Tree

Nama: Dea Claresta
Nim: 2301863736

AVL Tree merupalan self balancing binary search tree. BST digunakan dengan tujuan dari lebih cepatnya suatu node ditemukan, namun BST memiliki worst case, dimana proses penginputan data yg berurut akan membuat penempatan Node yang sebaris dan tidak bercabang,sehingga proses pencarian datanya sama saja dengan linked list  yaitu dengan membandingkan setiap node dari awal sampai ketemu. Oleh sebab itu, digunakan lah metode AVL, yaitu balancingnya BST, sehingga setiap node hanya akan memiliki balence faktor maksimal 1 yang didapat dari pengurangan height kedua anaknya. Dimana setiap leaf(node yang tidak memiliki anak ) akan memiliki height sebesar satu, dan node-node keatasnya akan memiliki height yang semakin besar.


Jika setelah penginputan terbentuk balence factor yang lebih besar dari 1, maka akan dilakukan rotasi. Untuk rotasi ini sendiri, ada 4 macam( LL, RR, LR, RL). dimana rotasi ini dilihat dari 2 langkah terjadi imbalace menuju sumber terciptanya imbalance.

Rotasi LL(left-left)
Pada Node 6, balance faktornya 0-2=-2, sehingga <-1. Oleh sebab itu dilakukan rotasi, jika dilihat dari node 6 menuju ke node yang membuat tidak balance(9), maka jalannya adalah kanan,kanan, oleh sebab itu dilakukan arah kebalikannya, yaitu left-left(LL), dengan membuat 8 sebagai parent  ,6&9 menjadi anaknya, karena 8 sudah dinaikkan, maka anak kirinya akan tetap di kirinya node 8, namun sebagai anak kanannya node 6(yang turun)

Rotasi RR(right-right)
pada node c terjadi imbalance, oleh sebab itu dilakukan rotasi, karena balace faktornya 2-0=2 ->lebih besar dr 1, karena 2 langkah menuju ke sumber imbalance adalah left-left, maka dilakukan rotasi RR, dan membuat node B menjadi parent, A&C menjadi anakn. jika node b memiliki anak kanan, maka anaknya akan tetap dikanannya, namun beradi di bawah node c(yang memberikan posisinya)

Rotasi RL(right - left)
imbalance terjadi di node 3, untuk menuju ke sumber imbalance, perlu ke kanan, lalu kiri, oleh sebab itu dilakukan rotasi RL,Rotasi RL adalah melakukan rotasi RR di node ke 5, dan rotasi LL di node 3

Rotasi LR(left-right)
setelah dimasukkan node 7, pada node 13 terjadi imbalance, karena balance faktornya 4-2=2-> lebih besar dari 1, namun, dibawahnya terdapat node yang juga imbalance, sehinggat yang dilakukan adalah node dibawahnya terlabih dahulu. node 10 juga imbalace . 2 langkah dari node 10 menuju node 7(penyebab imbalance) adalah kiri,kanansehingga dilakukan rotasi LR, sehingga pada node ke 5 dilakukan rotasi LL, lalu rotasi RR pada node 10, dan anak kanan 6 pindah ke anak kiri 10(yang turun)

Delete node pada AVL

jika, node tidak memiliki anak, maka node tersebut akan dihapus, dan dilakukan pengecekan terjadi imbalance atau tidak, jika terjadi, maka dilakukan rotasi sesuai dengan cara diatas.
Jika node yang dihapus memiliki anak, maka digantikan oleh anak kiri paling kanan atau anak kanan paling kiri dari node tersebut. lalu dilakukan pengecekan ,terjadi imbalance atau tidak, jika terjadi maka melakukan rotasi sesuai dengan cara diatas.
link untuk delete code https://www.programiz.com/dsa/avl-tree