AVL Tree (Insertion and Deletion)

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree digunakan untuk melakukan searching yang lebih singkat dan sederhana.

Ada 4 case dalam melakukan operasi insert :

• Single Rotation
  Ada 2 case yang dapat diselesaikan dengan single rotation, yaitu ketika node terdalam terletak pada subtree kiri dan anak kiri T, (left rotation) dan ketika node terdalam terletak pada subtree kanan dan anak kanan T (right rotation).
  

• Double RotationDi double rotation juga terdapat 2 case yang dapat terselesaikan dengan double rotation, yaitu jika node terdalam terletak pada subtree kanan dan anak kiri T (right-left), dan node terdalam terletak pada subtree kiri dan anak kanan T (left-right).

Ada 2 case yang terjadi saat operasi delete :

1. Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.
2. Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1.Anggap T adalah node yang harus diseimbangkan kembali
   – Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
   – Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
   – Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
   – Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)
   
             Jika kita ingin menghapus node 60
   
   
   
   

   Terdapat node yang tidak seimbang yaitu node 55, maka kita dapat seimbangkan dengan single rotation (left rotation), tetapi node 50 menjadi tidak seimbang.

   
   

   Lalu diseimbangkan dengan double rotation (left-right) karena dari 50 ke 25 kiri dan 25 ke 40 kanan.