Balanced tree ( AVL Tree )

Balanced tree adalah tree dengan berat / selisih level child kiri dan kanan tidak lebih dari 1.

Dalam binary search tree, pencarian dimulai dari root sampai ke leaf
apabila tree yang dibuat adalah skewed tree, pencarian akan sangat panjang dan tidak efisien sehingga perlu diseimbangkan supaya dapat mencapai jarak dari root hingga ke leaf paling jauh dapat diminimalkan ( height dari tree )

contoh:
Memasukkan data : 50, 25, 48, 28, 38, 32, 35

cr : skyconnectiva.com

tinggi tree : 7

untuk meminimalkan tinggi dari tree, dibutuhkan sebuah metode. Salah satunya metode AVL.

Jika kita memasukkan data yang sama ( 50, 25, 48, 28, 38, 32, 35 )
Untuk step 50 dan 25 masih sama, namun saat memasukkan angka 48, child kiri lebih banyak dari child kanan sehingga ada yang harus dipindahkan

Hasil akhir:

tinggi tree = 4
dalam metode AVL, ada 4 macam pemindahan node/verteks dari tree.
1 & 2 : Single rotation apabila orientasi child sama sama ke kiri / kanan.

[input = 42.16.3] tree berat ke kiri, rotation ke kanan

[input = 3,24,106] tree berat ke kanan, rotation ke kiri

3 & 4 : Double rotation apabila orientasi child berbeda dengan orientasi child ke-2 dari child pertama.

[input = 85,34,51] tree akan merotasi 51 dengan 34 terlebih dahulu

[input = 256,512,384] tree akan merotasi 384 dan 512 terlebih dahulu

perpindahan node/verteks tidak selalu pada angka yang baru dimasukkan, tergantung saat selisih level kedua child dari sebuah verteks adalah lebih dari 1. Cara menghitungnya adalah level 1 untuk leaf, level leaf untuk parent adalah +1 dan apabila verteks mempunyai 2 child dengan level 3 dan 4, verteks tersebut adalah level 4+1 ( = 5)

Contoh : memasukkan angka 1 hingga 12

analisis:
verteks input : 12
level verteks 11 = 2 | child : 0 dan 1 ( 12 ) , Δ = 1
level verteks 10 = 3 | child : 2 ( 11 ) dan 1 ( 9 ) , Δ = 1
level verteks 8 = 4 | child : 2 ( 6 ) dan 3 ( 10 ) , Δ = 1
level verteks 4 = 5 | child : 2 ( 2 ) dan 4 ( 8 ) , Δ = 2
*Δ = selisih

permasalahan terjadi pada verteks 4 jadi, penyelesaian adalah single rotation ke kiri dari verteks 4 ke kanan ( 4, 8, 10)

karena 8 tidak bisa mempunyai lebih dari 2 child ( binary tree ), maka child kiri dari 8 adalah 4, tree 6(5,7) menjadi child 4

Kesimpulan : AVL Tree dapat membuat tinggi tree menjadi lebih rendah dan kondisi tree lebih seimbang sehingga pencarian verteks/node lebih efisien.

P.S. : Baru bisa dikerjain karena laptop abis diservice
credits : images generated by apps from skyconnectiva.com

---

skyconnectiva.com
binus.ac.id