AVL TREE

AVL TREE

     Dalam ilmu pengetahuan komputer, AVL Tree adalah sebuah pohon biner berurutan yang bisa menyeimbangkan dirinya sendiri secara otomatis. Pada sebuah tree AVL, tinggi dua anak sub tree dari simpul apapun mempunyai perbedaan paling besar '1'. Lookup, Insertion, dan Deletion semuanya memerlukan O(logn) kali dalam kasus biasa dan kasus paling buruk. adition dan deletion membutuhkan pohon tersebut untuk menyeimbangkan kembali dirinya melalui rotasi pohon satu kali atau lebih.cara perurutannya yaitu sebelah kiri nilai yang paling rendah sedangkan sebelah kanan nilai paling besar dari nilai utamanya (root), atau disebut juga left < root<right. AVL Tree bisa juga disebut sebagai keseimbangan dalam kehidupan sehari-hari kita.


AVL Tree dinamakan dari kedua penemunyaa yaitu G.M. Adelson-Veleskii dan E.M. Landis. AVL Tree merupakan penemuan binary search tree yang dapat menyeimbangkan dirinya sendiri.

Tinggi/height dari sebuah node :

- Tinggi dari sebuah daun/leaf yaitu 1
- Tinggi dari sebuah subtree yang kosong itu 0.
- Tinggi dari sebuah internal node adalah tinggi maksimum dari anakannya ditambah 1.

Faktor penyeimbang :
- Ketinggian dikiri subtree dan dikanan subtree

(Faktor penyeimbang dari semua node pada AVL Tree seharusnya ada 1)

Contoh:

kasus ini dapat diselesaikan dengan melakukan rotasi
– Kasus 1 dan 2 dengan single rotation
– Kasus 3 dan 4 dengan double rotation

Contoh – Single Rotation: Jika suatu Tree diinsert node baru dengan nilai 12, maka akan terjadi ketidak seimbangan dan hal ini terletak pada posisi root

Contoh – Double Rotation : Jika terdapat sebuah tree yang kemudian dilakukan insert node 26. Maka akan terjadi ketidak seimbangan, sehingga terlihat dari bentuknya dapat diselesaikan dengan kasus 4. sehingga hasilnya menjadi sebagai berikut.