AVL Tree


AVL Tree - 28 April 2020

AVL atau Balanced Binary Search Tree adalah BST yang mempunyai minimal tinggi (height) sebesar log n agar bisa mempersingkat waktu dalam memasukan, mencari, dan menghapus data.

biasanya bila kita menggunakan bst dan memasukan data berurut 1 sampai 10, akan menjadi seperti gambar dibawah
dan jika kita mau memasukkan data 11, tree ini akan mencari dari root sampe data ke 10 terlebih dahulu dan baru memasukkan data 11.

di AVL Tree, kita membuat tree dalam bentuk seimbang, bagaimana cara mengetahui apakah pohon itu seimbang atau tidak?
maksimum height kanan dikurang kiri adalah 1.
lihat gambar dibawah
kita lihat dari node 10 yang merupakan root dari tree
height yang ada dikanan adalah 3
height di kiri adalah 2
height kanan kurang kiri adalah 1
jadi tidak menyalahi aturan.

lalu lihat node 6
height di kiri 6 adalah 1
di kanan adalah 1
1-1=0
tidak menyalahi aturan.

lihat node 17
di kanannya 0
di kiri ada 2
|0-2|=2
ini menyalahi aturan.

bagaimana cara membuat pohon ini seimbang?

ada 2 tipe case dalam penyeimbangan tree
case 1 :
node yang bermasalah adalah 4 karena kanannya 0 kirinya 2
|0-2|=2
dan yang membuat kelebihan adalah node 2 di kiri,
bila dilihat dari atas untuk mencapai node 4, menggunakan path kiri kiri
bila path yang digunakan untuk mencapai node yang bermasalah adalah kiri-kiri, atau kanan-kanan.
cukup menggunakan single rotation

pada kasus ini kita akan menggunakan single rotation dan membuat 3 sebagai poros
kita akan rotate 4 agar bisa seimbang
bayangkan 3 menjadi poros dan tarik 4 kesebelah kanan

balance tree nya akan menjadi seperti ini


Case 2 :
node yang bermasalah adalah 30 dan yang membuat berat sebelah kiri adalah 26
untuk mencapai 26, kita mengambil path kiri-kanan
untuk kasus path kiri-kanan atau kanan-kiri
kita menggunakan double rotation
single rotate pada poros 22
dan lakukan single rotate lagi pada poros 27


Pada AVL, kita juga bisa menghapus node
namun setelah kita menghapus sebuah node,
kita harus cek lagi apakah pohon itu sudah seimbang atau belum
bila tidak seimbang, maka kita harus menyeimbangkan lagi dengan single rotation atau double rotation.

contoh kasus :

kita akan menghapus node 60
tetapi setelah node 60 dihapus, pohonnya menjadi tidak seimbang
maka kita harus menyeimbangkan lagi pohonnya.

kita lihat yang tidak seimbang disini adalah node 55 dan yang menyebabkannya adalah node 70
untuk sampai ke node 70 ambil path kanan-kanan
maka kita pakai single rotation.

setelah diseimbangkan, ternyata masih ada yang tidak seimbang
node 50 memiliki height 2 dikanan dan 4 dikiri
|2-4|=2
maka harus diseimbangkan kembali
node yang menyebabkan berat dikiri adalah 42
untuk sampai ke 42, kita ambil path kiri-kanan
untuk kasus ini kita akan pakai double rotation


 hasil setelah double rotation :


maaf bila ada salah, karena saya juga masih belajar :)

Comments

Popular posts from this blog

Source code untuk Tugas GSLC

Heaps and tries

Linked list - 002