AVL Tree

AVL TREE

AVL Tree adalah bentuk dari Binary Search Tree(BST) yang telah dikembangkan untuk dapat menyeiambangkan dirinya sendiri secara otomatis saat memasukkan data didalamnya dan juga masih memiliki semua sifat dan ciri dari BST.

AVL Tree juga memiliki ciri seperti, setiap root pastinya berada di paling atas; setiap root bisa memiliki nol, satu maupun dua child nodes; setiap child node bisa memiliki nol, satu atau lebih dari satu child node lainnya; dan biasanya setiap node yang berada di posisi kanan memiliki nilai yang relatif kecil daripada node yang berada di kanan yang nilainya relatif lebih besar.

Namun AVL Tree memiliki ciri khasnya yaitu, perbedaan kedalaman antara node kiri dan node kanan tidak boleh melebihi satu, dimana dalam pemrograman AVL Tree harus memiliki kode yang dapat mengatur/mengubah/menyeimbangkan tree pada saat nilai yang baru dimasukkan kedalam node yang baru.

                             
Metode yang ada pada AVL Tree mencakup Insertion dan Deletion

INSERTION

  1. Single LEFT Rotation (LL Rotation)
Jika terjadi ketidak seimbangan pada child node kanan pada subtree kanan maka perlu dilakukan  sebuah Left Rotation.
Hal ini dapat dilakukan dengan cara mengubah satu posisi tiap node dari posisi awalnya ke bagian kirinya.
Seperti contoh:
                                       
Pada contoh tersebut, diambil node yang berisi nilai 85 dan dijadikan sebagai poros agar semua nodenya dapat melakukan Left Rotation sekali.

  2. Single RIGHT Rotation (RR Rotation)
Jika terjadi ketidak seimbangan pada child node kiri pada subtree kiri maka perlu dilakukan  sebuah Right Rotation.
Hal ini dapat dilakukan dengan cara mengubah satu posisi tiap node dari posisi awalnya ke bagian kanannya.
Seperti contoh:
                                             

Pada contoh tersebut, diambil node yang berisi nilai 44 dan dijadikan sebagai poros agar semua nodenya dapat melakukan Right Rotation sekali.

  3. LEFT-RIGHT Rotation (LR Rotation)
Jika terjadi ketidak seimbangan pada child node kiri pada subtree kanan maka perlu dilakukan  sebuah Left-Right Rotation.
Hal ini dapat dilakukan dengan cara menggunakan kombinasi dari Left Rotation kemudian Right Rotation. Dengan setiap node bergeser 1 posisi ke sebelah kiri dari posisi awalnya dan kemudian bergeser sekali lagi ke posisi kanannya. 
Seperti contoh:
                                             
Pada contoh tersebut, diambil node yang berisi nilai 39 menjadi poros kemudian dilakukan Left Rotation dan dilanjutkan dengan mengambil nilai 39 lagi menjadi porosnya dan dilakukan Right Rotation.
  4. RIGHT-LEFT Rotation (RL Rotation)
Jika terjadi ketidak seimbangan pada child node kanan pada subtree kiri maka perlu dilakukan  sebuah Right-Left Rotation.
Hal ini dapat dilakukan dengan cara menggunakan kombinasi dari Right Rotation kemudian Left Rotation. Dengan setiap node bergeser 1 posisi ke sebelah kanan dari posisi awalnya dan kemudian bergeser sekali lagi ke posisi kirinya. 
Seperti contoh:
                                             
Pada contoh tersebut, diambil node yang berisi nilai 40 menjadi poros kemudian dilakukan Right Rotation dan dilanjutkan dengan mengambil nilai 40 lagi menjadi porosnya dan dilakukan Left Rotation.

DELETION
Biasanya dalam operasi Deletion dalam AVL Tree memiliki 2 kasus yaitu,
1. Ketika yang akan dihapus adalah node yang tidak memiliki anak, maka dari itu penghapusan dapat segera dilakukan tanpa mengubah Tree-nya.
2. Ketika yang akan dihapus adalah node yang memiliki anak, maka dari itu proses harus dilakukan  penyeimbangkan Tree-nya setelah melakukan penghapusan.