AVL Tree

Pengertian AVL Tree

AVL Tree adalah tree yang hanya boleh memiliki perbedaan tinggi/height maksimal satu antara subtree di kiri dan di kanan. Dengan adanya AVL tree, waktu pencarian akan dipersingkat dan lebih sederhana.

Gambar tersebut merupakan contoh dari AVL Tree karena perbedaan tinggi dari subtree kanan dan subtree kiri adalah 1.

Insertion

Insertion pada AVL tree sama seperti insertion pada BST, yang lebih kecil dari pada root akan berada di sebelah kiri dan yang lebih besar akan berada di sebelah kanan. Masalah yang biasa terjadi pada insertion di sini adalah bisa saja treenya tidak akan seimbang. Pada syarat AVL kita hanya diperbolehkan memiliki tinggi maksimal 1/-1 saja. Untuk membuat AVL tree tetap seimbang kita akan menggunakan dua teknik yaitu, single rotation dan double rotation. Jangan lupa untuk arah rotasi juga ada dua ya! right rotate dan left rotate.

1. Single Rotation

T1, T2, T3 and T4 are subtrees.
         z                        z                  
        / \                      / \                   
       y   T4                  T1   y
      / \           atau           / \
     x   T3                       T2  x             
    / \                              / \
  T1   T2                           T3  T4

Kita diperbolehkan menggunakan single rotation jika bentuk dari AVL tree seperti diatas. Jadi, dari root lurus kekiri bawah (leaf) ataupun dari root lurus ke kanan bawah (leaf). Cara untuk melakukan rotasinya adalah sebagai berikut.

T1, T2, T3 and T4 are subtrees.
         z                                      y 
        / \                                   /   \
       y   T4      Right Rotate (z)          x      z
      / \          - - - - - - - - ->      /  \    /  \ 
     x   T3                               T1  T2  T3  T4
    / \
  T1   T2

Dari tulisan tersebut kira dapat lihat cara untuk menggunakan single rotation. Pada tree yang pertama kita lihat bahwa disana terdapat perbedaan 2 level lebih banyak di subtree kiri. Oleh karena itu, kita harus rotasikan z yang awalannya adalah root dari tree (dan juga merupakan poros untuk dirotasikan), menjadi subtree di kanan. Sehingga y akan menjadi root baru dan semuanya akan kembali seimbang antara subtree kanan dan kiri. 

Permasalahan selanjutnya adalah bagaimana dengan T3 jika subtree kanan dan kiri y sudah terisi karena y telah menjadi root baru? Jawabannya adalah kita masukkan T3 kedalam subtree kiri z, mengapa? karena sebelumnya T3 merupakan anak kanan dari y yang nilainya lebih besar dari x tetapi lebih kecil dari z, sehingga saat single rotation telah dilakukan T3 akan pindah kedalam subtree kiri dari z.

2. Double Rotation

     z                  z           
    / \                / \         
   y   T4             T1  y
  / \        atau        / \
T1   x                  x   T2                  
    / \                / \    
  T2   T3             T3  T4    

Untuk double rotation kita hanya diperbolehkan memakainya jika bentuk tree seperti diatas, dari root sampai leaf bengkok dan tidak lurus kebawah. Cara untuk merotasikannya adalah sebagai berikut.

     z                               z                           x
    / \                            /   \                        /  \ 
   y   T4  Left Rotate (y)        x    T4  Right Rotate(z)    y      z
  / \      - - - - - - - - ->    /  \      - - - - - - - ->  / \    / \
T1   x                          y    T3                    T1  T2 T3  T4
    / \                        / \
  T2   T3                    T1   T2

Dari tulisan diatas kita dapat melihat bahwa bentuk tree dari root sampai leaf bengkok. Perbedaan level pada subtree di kiri dan subtree di kanan adalah dua. Untuk melakukan double rotation kita harus mengetahui porosnya terlebih dahulu. Karena namanya saja double rotation berarti kita juga memiliki 2 poros yang harus dirotasikan. Poros pertama yang harus di rotasikan pada tree diatas adalah y karena y merupakan awalan yang membuat tree menjadi bengkok. Kita rotasikan y ke kiri sehingga memiliki bentuk tree baru seperti gambar kedua. Jika dilihat lebih baik lagi, kita dapat melihat bahwa gambar kedua mirip sekali dengan tree yang sudah kita bahas di single rotation. Oleh karena itu, poros kedua adalah rootnya yaitu z, z di rotasikan ke kanan sehingga x menjadi root yang baru dan z menjadi subtree bagian kanan dari x. Jangan lupa untuk memindahkan T3 ke subtree kiri dari z!

Deletion

Jika kita ingin menghapus suatu node dalam AVL tree kita dan kita ingin memastikan agar tree tersebut masih memenuhi syarat AVL, kita harus menambahkan operasi penghapusan BST standar untuk melakukan beberapa penyeimbangan ulang.

Dari dua gambar diatas kita dapat mengetahui jika node 32 sedang dihapus dan setelah dihapus kita akan kembali melihat bentuk tree itu lagi dan perbaiki tree tersebut jika ada yang tidak seimbang. Dari tree tersebut yang menjadi tidak seimbang adalah 44 yang akan ditandai dengan z, 62 akan ditandai dengan y dan 78 akan ditandai dengan x. Setelah itu kita dapat melihat jika dari root sampai leaf memiliki jalur lurus, sehingga kita akan melakukan single rotation dan porosnya berada pada z / node 44 yang akan kita rotate ke kiri sehingga, kita mendapatkan tree yang sama seperti gambar kedua. Sama seperti sebelumnya, 50 akan menjadi anak kanan dari z/node 44 karena node 50 sebelumnya merupakan anak kiri dari node 66 sehingga saat node 66 menjadi root yang baru, node 50 akan pindah menjadi anak kanan dari node 44 karena nilainya lebih besar dan node 62 subtree kanan dan kirinya sudah full.

Sekian penjelasan tentang AVL tree dari saya, semoga dapat membantu kalian semua. Terima kasih

Nama : Reinhart Perbowo Pujo Leksono

NIM ; 2301857254

Source :

1. https://www.geeksforgeeks.org/avl-tree-set-1-insertion/
2. https://www.geeksforgeeks.org/avl-tree-set-2-deletion/