AVL Tree

Pendahuluan

Binary Search Tree (BST) yang telah dipelajari selama ini masih memiliki kekurangan. Jika tree yang terbentuk berupa Skewed Tree, maka diperlukan pencarian sebanyak jumlah data yang ada (n). Untuk itu, kita akan menggunakan AVL Tree. AVL Tree merupakan subtipe dari Binary Search Tree. Fyi, AVL Tree diambil dari nama penemunya yaitu Adelson, Velskii dan Landis (sumber:https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor/). Dengan adanya AVL Tree, maka pencarian yang dilakukan dapat dikurangi hingga berjumlah ²log(n).

Ciri-ciri

Konsep tree : https://linked-list-dikky.blogspot.com/2020/03/hashmap-and-binary-tree.html

BST : https://binustreereview.blogspot.com/2020/03/binary-search-tree.html

AVL Tree memiliki semua ciri yang dimiliki oleh Tree dan BST dengan satu tambahan ciri, yaitu:
- Perbedaan tingkat (depth) dari subtree kiri dan kanan dari setiap node tidak boleh lebih dari satu.

Dengan adanya tambahan syarat tersebut, diperlukan metode balancing (penyeimbangan) depth untuk setiap subtree yang ada, atau dikenal dengan Rotating Method.

Rotating Method

Jika dikelompokkan, ada dua metode rotasi, yaitu:

- Single Rotation (Left(L)/Right(R) Rotation)

- Double Rotation (LR/RL Rotation)

Untuk penggunaannya, dapat disesuaikan sesuai dengan kondisi di bawah ini:

Jika node dengan subtree/leaf yang berlebih selalu dalam arah yang sama (segaris) (kanan-kanan atau kiri-kiri) digunakan Single Rotation.

1.1. Single Rotation Case (sumber: binusmaya.ac.id)
Jika node dengan subtree/leaf yang berlebih mengalami belok/bengkok di antara link yang ada, dapat digunakan Double Rotation.

2.1. Double Rotation Case Example (sumber: binusmaya.ac.id)

Step awal menggunakan node S sebagai poros untuk menarik R ke kiri (left rotation).

2.2. Double Rotation Case, step 1. (sumber: binusmaya.ac.id)

Lalu, node T akan digunakan sebagai poros selanjutnya untuk menarik R ke kanan. (right rotation).

2.3. Double Rotation Case, step 2. (sumber: binusmaya.ac.id)