AVL Trees

AVL trees mirip dengan binary search tree. Hanya saja AVL memiliki perbedaan yaitu akan menyeimbangkan ketinggian dari subtrees kiri dan kanan. Perbedaan ketinggian dari subtrees kiri dan subtrees kanan kurang dari atau sama dengan 1.

Contoh diatas merupakan AVL tree karena perbedaan ketinggian dari subtrees kiri dan kanan kurang atau sama dengan satu.

Sedangkan untuk gambar ke dua bukan merupakan avl karena perbedaan ketinggian dari subtrees kiri dan kanan lebih dari satu.

Keuntungan dalam menggunakan AVL Tree adalah jika kita menggunakan BST / Binary Search Tree untuk mempercepat pencarian data, maka dengan menggunakan AVL akan menjadi semakin cepat lagi karena seimbang serta tidak memakan tempat di ketinggian yang lain. Sehingga waktu pencarian data tidak lebih dari log2n langkah.

Ada 4 kasus dalam operasi insert, yaitu:

T adalah node yang harus diseimbangkan.

1.       Node terdalam terletak pada subtree kiri dari anak kiri T (left-left).

2.       Node terdalam terletak pada subtree kanan dari anak kanan (right-right).

3.       Node terdalam terletak pada subtree kanan dari anak kiri T ( right-left).

4.       Node terdalam terletak pada subtree kiri dari anak kanan T (left-right).

Untuk kasus 1 dan 2 dapat diselesaikan dengan single rotation. Sedangkan untuk kasus 3 dan 4 dapat diselesaikan 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

 

Perbedaan dengan Red Black Tree adalah AVL tree lebih seimbang hanya saja bisa melakukan rotasi yang lebih banyak selama insertions dan deletion dibandingkan denga Red Black Tree. Sehingga jika aplikasi kita mengunakan insertion dan deletion yang banyak, maka tentu sangat dianjurkan menggunakan Red Black Tree. Sedangkan jika sebaliknya maka AVL sangat dianjurkan.

Sumber:

- https://www.geeksforgeeks.org/avl-tree-set-1-insertion/

- https://socs.binus.ac.id/2016/12/20/insertion-avl-tree/