Langsung ke konten utama

AVL Tree

Pengertian AVL Tree

AVL tree adalah sebuah tree yang mirip dengan Binary Search Tree yang mempunyai fungsi yang sama, namun mempunyai aturan sendiri. Di dalam Binary Tree, jika kita menginsert sebuah angka, pasti akan ditampung di kiri atau kanan dari tree tersebut, tergantung dengan nilainya kurang dari atau lebih dari (kalau kurang, di taruh kiri dan kalau lebih, ditaruh di kanan). AVL Tree ini mempunyai aturan bahwa perbedaan subtree kiri dan kanan tidak boleh melebihi 2. Untuk lebih jelasnya, mari kita lihat contoh berikut.

AVL Tree dari geeksforgeeks

Pada contoh di atas, tree tersebut merupakan sebuah AVL tree karena selisih dari subtree kiri dan kanan dari root kurang dari 2 (paling banyak 1). Kita dapat menghitung jumlah subtree kiri dengan melihat paling bawahnya dari kiri. Pada gambar tersebut paling bawahanya adalah 4. Nah, kita menghitung subtreenya dari 12. Di kiri dari 12 ada 8 lalu dikirinya lagi ada 5, lalu terakhir ada 4. Nah jumlah subtree kiri ada 3 sedangkan jumlah subtree kanan ada 2 yaitu 18 dan 17. Selisih dari subtree kiri dan kanan adalah 1, sehingga memenuhi syarat untuk membuat AVL tree. Coba kita lihat contoh yang tidak memenuhi syarat AVL tree.

Tree yang bukan AVL dari geeksforgeeks

Gambar diatas merupakan contoh dari AVL tree yang salah. Mari kita lihat salashnya di mana. Seperti yang saya bilang sebelumnya, sebuah AVL tree harus mempunyai perbedaan subtree kanan dan kiri kurang dari 2. Nah, jika kita hitung subtree kiri, maka kita bisa lihat bahwa ada 4 subtree di kiri. Pada subtree kanan terhadap 2 subtree. Selisih subtree kiri dan kanan adalah 2 sehingga tidak memenuhi syarat dari AVL tree.

Insertion

Sebenarnya untuk melakukan insertion, langkah-langkah yang dilakukan tidak terlalu berbeda dengan insertion pada Binary Search Tree. Yang membedakannya adalah ketika kita sudah selesai menginsert, kita mengecek apakah tree tersebut seimbang (selisih subtree kanan dan kiri paling banyak 1) atau tidak seimbang. Jika seimbang, maka kita akan membiarkannya saja sedangkan jika tree kita tidak seimbang, maka kita harus membuatnya seimbang. Cara untuk membuatnya seimbang adalah dengan single rotation atau double rotation.

Sebuah tree mempunyai 4 kemungkinan atau kasus untuk tidak seimbang yaitu:
  • Left Left case
  • Right Right case
  • Left Right case
  • Right Left case
Left left dan right right case dapat diselesaikan dengan single rotation, sedangkan left right dan right left case bisa diselesaikan dengan double rotation.

Left Left Case

Left left case adalah kasus dimana treenya tidak seimbang karena lebih berat di kiri.

         6                                      4 
        / \                                   /   \
       4   10      Right Rotate (6)          2      6
      / \          - - - - - - - - ->      /  \    /  \ 
     2   5                                1    3  5   10
    / \
   1   3

Pada kasus di atas, angka 6 menyebabkan ketidakseimbangan dari tree tersebut yang menyebabkan treenya berat ke kiri sehingga harus dilakukan single rotation. Karena treenya berat di kiri, maka ada beberapa bagian yang harus dibuat ke kiri sehingga bisa seimbang. Untuk lebih gampang untuk membayangkannya, anggap saja angka 6 adalah sebuah katrol. Karena titik tumpunya adalah di 6, dan untuk dapat seimbang harus ditarik ke kanan, maka titik tumpu akan menjadi 4 sehingga semua yang ada di kiri bergerak ke kanan. 

Right Right Case

  11                              14
 /  \                            /   \ 
2    14     Left Rotate(11)      11    18
    /  \   - - - - - - - ->    / \    / \
   12  18                     2  12  16 20
       / \
      16 20
Kasus di atas sangat mirip dengan kasus left left case, yang membedakannya adalah treenya lebih berat ke kanan sehingga perlu juga dilakukan single rotation agar tree tersebut bisa seimbang.

Left Right Case

    15                              15                           12
    / \                            /   \                        /  \ 
  10   20  Left Rotate (10)       12   20  Right Rotate(15)   10    15
  / \      - - - - - - - - ->    /  \      - - - - - - - ->  / \    / \
5   12                         10   13                      5  11  13 20
    / \                        / \
  11   13                    5   11
Nah kita harus lihat terlebih dahulu kenapa case ini dinamakan left right case. Lihatlah pada subtree kiri dari 15. Kita bisa lihat bahwa subtree terdalamnya ada di 11 dan 13. Karena itulah, treenya berat di 2 tempat di kiri, sehingga kita harus membuat bagian disitu seimbang terlebih dahulu. Nah untuk itu kita harus merotasi 10 dan setelah kita rotasi, ternyata masih belum seimbang. Oleh karena itu, kita harus merotasi 15 sehingga dapat seimbang. Oleh karena itu kasus ini memerlukan dua kali rotasi yang disebut dengan double rotation. 

Right Left Case

  15                           15                            17
  / \                          / \                          /  \ 
 1   20   Right Rotate (20)   1  17      Left Rotate(15)   15   20
    / \  - - - - - - - - ->     /  \   - - - - - - - ->  / \    / \
  17  21                      16    20                  1  16  19 21
  / \                              /  \
16  19                            19   21
Kasus ini mirip dengan kasus left right case hanya perbedaannya adalah berat di subtree kanan dari 15 lalu berat di subtree kiri darai 20. Diperlukan metode double rotation sehingga bisa seimbang lagi.

Deletion

Untuk melakukan deletion, cara melakukannya sama dengan ketika kita melakukan deletion pada Binary Search Tree. Yang membedakannya adalah ketika kita melakukan deletion dan membuat tree itu tidak seimbang, maka kita harus melakukan rotaion agar tree tersebut seimbang.

Kita ingin mendelete 55
Karena yang di delete adalah 60, maka tree di kiri menjadi tidak seimbang. Untuk membuatnya seimbang, diperlukan rotation agar treenya menjadi seimbang.

Rotation terhadap 55
Kita melakukan rotasi terhadap 55 sehingga 65 akan menempati 55 dan 55 akan ada di subtree kiri dari 65.

Rotasi terhadap 50

Setelah melakukan rotasi terhadap 55, ternyata tree masih tidak seimbang sehingga 50 harus dirotasikan. Karena 50 dirotasi ke kiri, maka 40 mengambil posisi dari 25. Setelah itu dilakukan lagi rotasi terhadap 50 ke kanan sehingga 40 menempati tempat 50 dan treenya menjadi seimbang.

Hasil AVL Tree yang sudah dilakukan deletion

Bisa disimpulkan bahwa AVL tree merupakan tree yang mirip dengan Binary Search Tree namun mempunyai sedikit perbedaan. AVL tree mempunyai syarat agar subtree kiri dan kanan mempunyai selisih 1 sehingga subtree tersebut bisa seimbang.

Komentar

Posting Komentar

Postingan populer dari blog ini

How do you get to the top of Mt Coronet in Pokemon Diamond?

Note: If you are going to try to catch Dialga or Palkia (diamond or pearl) make sure you have a bunch of Ultra and Dusk balls!! First, Fly to Hearthome city and head west, Route 208. Enter the cave and once inside, you should go north.When you first enter the cave, you need to head west to the opposite side. Once you reach the west entrance, head north and surf across the pond. Use rock climb to reach the stairs up. In the next room: Go- North, West, South, Upstairs, North, West over bridge, down stairs, up north, stairs,up stairs, cross bridge, down stairs, down stairs, upstairs and in cave door. In the Next room: Up stairs, up stairs Again Next room: up stairs, north, west, south, Out. Now you are outside. Follow the path and use rock climb when you get there. Now don't use rock climb again, instead, head west and through the grass until you reach another cave. Inside, use rock climb, follow the path, down the stairs then east, you're out of the cave. ...
Posting Komentar
Baca selengkapnya

Binary Search Tree

Pengertian Binary Search Tree Binary search tree adalah sebuah metode dari data structure yang mempunyai ciri sebagai berikut: Bagian kiri dari subtree adalah nodus yang mempunyai nilai yang lebih kecil Bagian kanan dari subtree adalah nodus yang mempunyai nilai yang lebih besar Bagian kiri dan kanan dari subtree harus berupa binary search tree juga Mencari Sebuah Angka (searching) Ilustrasi Binary Search Tree dari geeksforgeeks Bisa kita lihat dari contoh diatas, bagian kiri dari binary search tree merupakan nilai yang kecil sedangkan bagian kanannya adalah nilai-nilai yang besar. Kita bisa mengambil contoh angka 7. Ketika angka 7 ingin dicari pada binary search tree diatas, maka dia akan mengecek. Apakah 8 lebih kecil atau besar dari 7? Karena lebih kecil, maka 7 akan dicari di bagian kiri. Kemudian, akan dicek lagi. Apakah 7 lebih kecil daripada 3? Jawabannya adalah tidak, sehingga 7 dicari dibagian kanan. Lalu ketika sampai di 6, karena 7 lebih besar...
Posting Komentar
Baca selengkapnya

Heaps & tries

Heap Minggu lalu kita sudah membahas AVL Tree dan sekarang kita akan membahas Heap & Tries. Heap adalah sebuah struktur data dengan konsep binary tree. Heap mempunyai dua jenis yaitu: Min - heap Max - heap Min - Max heap Heap dapat diimplementasikan dengan linked list, namun akan lebih gampang jika menggunakan array. Agar lebih jelas, lebih baik kita lihat gambar berikut ini. Heap dari geeksforgeeks Min - Heap Pada min - heap terdapat aturan agar heap itu dapat dibuat. Aturan tersebut adalah angka atau huruf yang ada di root harus paling kecil daripada anak - anaknya. Hal ini juga berlaku pada subtree lainnya secara rekursif. Jadi, yang diatas harus lebih kecil daripada bawahnya. Insertion Berbeda dengan BST yang mempunyai aturan kiri harus yang kecil dan kanan yang besar, min - heap hanya menghiraukan atasnya. Pada kasus min - heap berarti atasnya harus lebih kecil daripada bawahnya. Agar kita mengerti cara menginsertnya, lihat gambar berikut: Kita ak...
Posting Komentar
Baca selengkapnya