AVL Tree

AVL Tree

AVL tree merupakan suatu tipe binary search tree (BST) yang dapat menyeimbangkan dirinya sendiri. Maksudnya apa? setiap node dalam tree memiliki height, dimana height tersebut adalah jarak node tersebut menuju leaf paling bawah. dalam BST, jika inputan dari user memnyebabkan struktur tree menjadi skewed tree, maka metode insertion, deletion, dll akan bisa memakan waktu O(n) atau sebanyak node yang ada di tree tersebut.

Gambar diatas merupakan perbedaan antara implementasi BST normal dengan implementasi AVL Tree, dimana gambar kiri menunjukkan Skewed Binary Search Tree dan yang kanan merupakan Balanced Binary Search Tree. Jika BST bisa melakukan operasi dengan waktu O(n), AVL Tree dapat melakukan operasinya dengan waktu sebesar O(log n).

Height

Nah, setelah kita sudah tahu perbedaan BST normal dengan AVL Tree, sekarang kita pelajari bagaimana cara mengubah BST yang tidak seimbang menjadi seimbang menggunakan konsep AVL Tree.

Pertama, kita harus tahu apa itu height. Height adalah suatu pengukur jarak antara node dengan leaf.

Catatan: node ke 4 seharusnya returns 1

Bisa kita lihat pada gambar diatas. Pada node 5, height node tersebut adalah 2. itu artinya jarak antara node 5 ke leaf nya adalah 2 node, node 5 sendiri dan juga leaf nya node 6. Satu hal juga yang bisa kita tafsir, semua leaf node selalu memiliki height yang sama yaitu 1.

Bagaimana dengan node 1. Node 1 memiliki banyak anak, tetapi kita harus mencari leaf yang paling dalam untuk menentukan height. Dalam kasus ini, leaf paling terdalam dan merupakan keturunan node 1 adalah node 6, untuk itu, node 1 memiliki height sebesar 4. 

Balance Factor

Setelah mengenal tentang height, sekarang kita harus mengetahui apa itu balance factor. Apa sih tujuan utama AVL Tree? untuk menyeimbangkan tree yang tidak seimbang. Nah, cara kita tahu tree tersebut sudah seimbang atau belum bagaimana? Balance factor adalah jawabannya. 

Balance factor adalah suatu formula untuk menentukan apakah tree tersebut sudah seimbang atau belum. Dalam kasus AVL Tree, balance factor bisa ditentukan oleh pengurangan tangan kiri node dengan tangan kanan node.

Balance = ( tangan kiri node ) - ( tangan kanan node )

Nah AVL Tree memiliki aturan khusus juga dalam proses penyeimbangannya. Jika nilai absolut balance factor lebih dari 1, maka tree tersebut tidak seimbang, maka kita harus melakukan proses penyeimbangan.

Rotation

Dalam AVL Tree kita akan dikenalkan dengan konsep rotation, konsep ini sesuai namanya berfungsi untuk memutar node yang ada di tree kita. ada dua konsep rotation yang akan kita pakai, yaitu left rotation dan right rotation. Konsep inilah yang nantinya akan menyeimbangi Tree kita dengan menukar posisi node-node yang ada di tree kita.

1. Left Rotation

Left rotation berarti kita memutar node - node yang bersangkutan kekiri.

2. Right rotation

Right rotation berarti kita memutar node-node yang bersangkutan kekanan.

Nah, setelah kita tahu konsep right rotation dan left rotation. Sekarang kita langsung lihat bagaimana implementasinya pada tree yang tidak seimbang.

Ada 4 kondisi yang mengharuskan kita untuk menggunakan konsep rotation ini secara berbeda-beda. 2 kondisi tersebut kita namai Single Rotation 2 lainnya kita namakan Double Rotation, sesuai namanya, single rotation hanya melakukan operasi rotation sebanyak satu kali, sedangkan double rotation melakukan operasi rotation sebanyak dua kali.

Untuk melihat kondisi mana yang akan kita gunakan, kita cukup melihat dua tangan pertama node yang tidak seimbang.

Berikut kondisi 4 rotation tersebut:

1. Left Left Case 

Kasus ini berarti tangan node yang tidak seimbang dua-duanya merupakan tangan kiri. Kasus ini masuk kedalam ranah Single rotation, itu artinya kita bisa menyelesaikan masalah ini dengan hanya melakukan satu rotation, yaitu right rotation. Berikut contoh left left case. 

Di gambar kita bisa lihat node C adalah node yang bermasalah. Sekarang kita lihat tangannya. Node B merupakan tangan kiri Node C, untuk itu kita memasuki kondisi left. Setelah itu Node A adalah tangan kiri node B, sehingga kita akan memasuki kondisi left left case.

2. Right Right Case

Kasus ini merupakan kebalikan dari kasus left left case, dimana tangan node yang tidak seimbang kedua-duanya merupakan tangan kanan. Kasus ini bisa diselesaikan dengan single rotation, yang berupa left rotation.

3. Left Right Case

Kasus ini berbeda dari 2 kasus sebelumnya, karena kasus ini sudah masuk kedalam ranah double rotation. Kondisi ini berarti tangan pertama node yang bermasalah ada di kiri, setelah itu tangan kiri tersebut mempunyai tangan kanan, sehingga dinamai left right case. Untuk mengatasi ini kita harus mengubah case ini menjadi left left case, dengan melakukan left rotation. Setelah itu lakukan rotasi lagi sesuai left left case.

4. Right Left Case

Kasus, ini merupakan kebalikan dari kasus 3. Ini artinya node bermasalah mempunyai tangan kanan dan tangan kanan tersebut mempunyai tangan kiri. Kasus ini tetap mengharuskan kita untuk melakukan double rotation, tetapi kita harus melakukan right rotation terlebih dahulu. Setelah itu kita akan mendapatkan kasus right right case dan kita harus melakukan rotasi sesuai case tersebut.

Itu saja yang saya ketahui tentang AVL Tree yang mencakup pengertian AVL Tree dan proses Insertion AVL Tree, terima kasih.