AVL Tree

Pada Binary Search Tree (BST) bisa terjadi kasus dimana treenya berbentuk skewed karena berdasarkan inputan user. Contohnya bisa dilihat pada gambar di bawah ini.

Input : 9 1 6 3 4

BST memiliki aturan dimana setiap inputan yang lebih besar dari root selalu ke kanan dan yang lebih kecil selalu ke kiri. Berdasarkan inputan user di atas, tree tersebut menjadi tidak seimbang. Oleh sebab itu, kita perlu menggunakan AVL Tree. 

AVL Tree adalah balanced binary search tree dimana memiliki perbedaan tinggi antara subtree kiri dan kanan 0 atau 1. Tujuan dari AVL Tree ini adalah untuk menjadikan BST seimbang sehingga proses pencarian menjadi lebih mudah. AVL Tree ditemukan oleh Adelson-Veleskii dan E.M. Landis.

Height:

1. Jika subtree kosong maka height bernilai 0

2. Jika node adalah leaf maka height bernilai 1

3. Jika merupakan internal node, maka heightnya bernilai height maksimum anaknya ditambah 1

Balance Factor: perbedaan tinggi/height antara subtree kiri dan subtree kanan.

Contoh:

BST di atas tidak seimbang karena node 17 memiliki balance factor bernilai 2. Jadi, BST di atas bukan merupakan AVL Tree karena balance factornya lebih dari 1.

Operation pada AVL Tree ada 2, yaitu:

1. Insertion

2. Deletion

Insertion

Insert pada AVL Tree sama seperti insert pada BST, namun hal ini bisa menyebabkan BST menjadi tidak seimbang. Oleh sebab itu, setelah melakukan insertion maka harus menyeimbangkannya lagi / rebalance.

Ada 4 kasus yang biasa terjadi saat operasi insertion dilakukan, yaitu:

Misal: T adalah node yang harus diseimbangkan kembali

- Kasus 1: node terdalam terletak pada subtree kiri dari anak kiri T (left-left)

- Kasus 2: node terdalam terletak pada subtree kanan dari anak kanan T (right-right)

- Kasus 3: node terdalam terletak pada subtree kanan dari anak kiri T (right-left)

- Kasus 4: node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

Untuk menyeimbangkan BST pada keempat kasus tersebut maka dilakukan rotation. Rotation ada 2 jenis, yaitu:

1. Single Rotation : jenis rotation ini dilakukan jika terjadi kasus 1 dan 2

2. Double Rotation : jenis rotation ini dilakukan jika terjadi kasus 3 dan 4

Contoh Single Rotation pada operasi Insertion:

Node yang diinsert adalah 12. Setelah melakukan insertion, didapatkan tree seperti pada gambar kiri. BST tersebut tidak seimbang karena balance factor pada node 30 lebih dari 1. Kasus tersebut sama seperti kasus 1, yaitu node terdalam terletak pada subtree kiri dari anak kiri T (left-left). Oleh sebab itu diseimbangkan menggunakan single rotation sehingga menghasilkan AVL Tree seperti pada gambar kanan dimana node 22 menjadi rootnya.

Contoh Double Rotation pada operasi Insertion:

Node yang diinsert adalah 26. Setelah melakukan insertion, didapatkan tree seperti gambar di sebelah kiri. BST tersebut tidak seimbang karena balance factor pada node 30 lebih dari 1. Kasus tersebut sama seperti kasus 4, yaitu node terdalam terletak pada subtree kiri dari anak kanan T (left-right). Oleh sebab itu diseimbangkan menggunakan double rotation. Jika menggunakan single rotation, tree tetap menjadi tidak seimbang. Pada rotation pertama menghasilkan BST seperti gambar di tengah, dimana node 22 menjadi anak dari node 27. BST masih belum seimbang. Pada rotation kedua menghasilkan BST yang seimbang sehingga didapatkan AVL Tree seperti pada gambar kanan dimana node 27 menjadi rootnya.

Deletion

Ada dua kasus pada opersi deletion dilakukan, yaitu:

- Jika node yang akan dihapus berada pada posisi leaf atau tanpa node anak, maka dapat langsung dihapus.

- Jika node yang akan dihapus memiliki anak, maka proses deletionnya perlu di cek kembali / rebalance untuk menyeimbangkan BST dengan balance factor maksimal 1.

4 kasus yang ditemukan akan rebalance:

Misal: T adalah node yang harus diseimbangkan kembali

- Kasus 1: node terdalam terletak pada subtree kiri dari anak kiri T (left-left)

- Kasus 2: node terdalam terletak pada subtree kanan dari anak kanan T (right-right)

- Kasus 3: node terdalam terletak pada subtree kanan dari anak kiri T (right-left)

- Kasus 4: node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

Untuk menyeimbangkan BST pada keempat kasus tersebut maka dilakukan rotation. Rotation ada 2 jenis, yaitu:

1. Single Rotation : jenis rotation ini dilakukan jika terjadi kasus 1 dan 2

2. Double Rotation : jenis rotation ini dilakukan jika terjadi kasus 3 dan 4

Contoh Deletion:

Node yang akan dihapus adalah 60. Kemudian node 55 menggantikan posisi 60. 

Hal tersebut membuat BST menjadi tidak seimbang. Balance factor pada node 55 lebih dari 1 sehingga perlu dilakukan rotation. Jenis rotation yang digunakan adalah single rotation karena kasus tersebut sama seperti kasus 2, yaitu node terdalam terletak pada subtree kanan dari anak kanan T (right-right). 

Setelah melakukan single rotation pada node 55, maka dilakukan perbedaan tinggi kembali/ rebalance dimana balance factor bernilai maksimal 1. Didapatkan bahwa BST tersebut masih belum seimbang karena pada node 50 balance factornya lebih dari 1. Kasus tersebut sama seperti kasus 4, yaitu node terdalam terletak pada subtree kiri dari anak kanan T (left-right). Oleh sebab itu dilakukan double rotation.

Setelah dilakukan double rotation, didapatkan tree seperti gambar diatas. Tree tersebut sudah seimbang dan merupakan AVL Tree / Balanced BST. 

==>>Hal penting pada AVL Tree adalah setiap melakukan insertion atau deletion, maka perlu terus memperhatikan balance factornya. Jika BST tersebut belum seimbang, maka harus diseimbangkan kembali/ rebalance. Proses rebalance bisa dilakukan menggunakan single rotation atau double rotation. Jenis rotation yang digunakan harus sesuai dengan kasus yang didapatkan agar tree menjadi seimbang. <<==

Sumber:

1. PPT Binusmaya

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

3. https://socs.binus.ac.id/2017/05/15/deletion-avl-tree/

Dibuat oleh:

Nama : Sheila Gracia Angelina

NIM : 2301857456