AVL Tree

Balanced Binary Search Tree

Seperti yang sudah kita pelajari, tree merupakan suatu bagian dari struktur data yang memungkinkan melakukan operasi insert, delete , dan searching. Sayangnya, waktu yang dibutuhkan insertion, deletion, dan searching bergantung pada tingginya tree tersebut dimana makin besar height nya maka akan semakin lama. Hal ini yang menyebabkan mengapa menggunakan Binary Search Tree akan kurang efektif bila sedang mengerjakan sebuah data yang berjumlah besar atau banyak. Oleh karena itu, dengan menyeimbangkan height dari tree tersebut akan membantu mempercepat operasi insert, delete, dan searching pada sebuah tree. Tree dengan tujuan untuk meminimalkan height disebut dengan Balanced Binary Search. Contoh dari Balanced Binary tree adalah AVL tree dan Red Black Tree karena kedua tree tersebut sebisa mungkin akan meminimalkan height dari sebuah tree.

AVL Tree

AVL tree merupakan salah satu bagian dari self-balancing binary search tree. Bahkan AVL tree merupakan self-balancing tree pertama yang ditemukan. Faktor balance pada AVL sendiri adalah selisih dari height subtree kiri dan subtree kanan dari tree tersebut. Maximal dari height tersebut adalah 1 sehingga jika balance dari AVL tree tersebut melebihi 1 akan dilakukan penyeimbangan height.

Keuntungan dari AVL Tree

Karena AVL tree menyeimbangkan setiap balance yang melebihi 1 dengan begitu, height pada tree tersebut akan menjadi minimal karena height dari subtree kiri dan subtree kanan akansedemikin rupa diseimbangkan. Dengan height yang minimal ini, proses operasi insert, delete, dan searching akan jauh lebih cepat dan efektif dalam mengolah data yang jumlahnya yang relatif banyak.

Insertion Pada AVL Tree

Setiap kali kita melakukan Insertion pada AVL tree, akan terjadi pengecekan balance dimana selisih dari height subtree kiri dan subtree kanan. Bila ditemukan balance melebihi 1 maka akan diseimbangkan dengan beberapa metode. Ada 4 kasus dalam penyeimbangan AVL Tree:

- Case 1 : node terdalam terletak di sub tree kiri anak kiri pohon. (Left Left).
- Case 2 : node terdalam terletak di sub tree kanan anak kanan pohon. (Right Right).
- Case 3 : node terdalam terletak di sub tree kanan anak kiri pohon. (Left Right).
- Case 4 : node terdalam terletak di sub tree kiri dari anak kanan pohon. (Right Left)

4 kasus diatas bisa diselesaikan dengan rotation. Pada kasus 1 dan 2 harus diselesaikan dengan menerapkan single rotation. Sedangkan pada kasus 3 dan 4 harus diselesaikan dengan menerapkan double rotation

Single Rotation (Left & Right Rotation)

Gambar diatas merupakan contoh operasi left rotation yang merupakan single rotation. Node yang berapada di tengan (node B) akan menyundul node yang diatasnya (node A) sehingga node B akan menjadi parent dan node A serta node C akan menjadi subtree kiri dan subtree kanan dari node B. Setelah single rotation ini, balance akan bernilai 0 atau dengan kata lain subtree kiri dan subtree kanan akan seimbang. Single left rotation ini akan digunakan pada kasus 1 (LL).

Sama halnya dengan left rotation, cara kerja dari right rotation hampir sama. Node yang berada di tengah akan menyundul node yang berada di atasnya (node A) sehingga node B akan naik menjadi parent dan node yang tadinya berada di atas akan menjadi subtree kiri dari node B. Sedangkan node C akan menjadi subtree kanan dari node B. Right rotation akan digunakan ketika terdapat kasus 2 (RR)

Double Rotation (Left Right & Right Left)

Gambar di atas merupakan operasi dari double rotation (Left Right ). Node yang berada di paling dalam (2) akan menyundul ke atas kiri yaiut node 1. Setelah itu, node akan berbentuk seperi case nomor 2 sehingga yang perlu kita lakukan adalah melakukan Right rotation. karena node 2 sekarang berada di tengah, maka node 2 akan menyundul node diatasnya sehingga node 2 akan naik dan node 3 akan menjadi subtree kanan dari node 2. Sedangkan node 1 akan menjadi subtree kiri dari node 2. Left Right rotation ini digunakan pada kasus nomer 3 (Left Right).

Gambar di atas merupakan gambar operasi double rotation (Right Left). node 60 akan menyundul node 70 yang berada di atasnya sehingga node 60 akan berada di tengah. setelah itu akan terbentuk seperti kasus nomer 1. Sehingga yang perlu dilakukan adalah melakukan Left Rotation. node 60 akan menyundul node 50 sehingga node 50 akan turun menjadi subtree dari node 60. Node 70 akan tetap menjadi subtree kanan dari node 60. Pengaplikasian Right Left rotation ini bisa dilakukan pada case nomor 4.

Deletion AVL Tree

Deletion pada AVL tree bisa dilakukan seperti berikut:

Step 1: Delete node seperi Binary Search Tree biasa.
Step 2: Ketika yang di delete merupakan leaf atau node dengan 1 anak. maka cek dari parent node yang ingin di hapus hingga root tree. Untuk setiap node yang dicek, bila heigh kiri dan kanan berbeda maka harus dilakukan rotasi (bisa single atau double). jika height seimbang maka cek terus lanjut hingga ditemukan ketidak seimbangan lagi atau hingga root dari tree tersebut.

contoh: