AVL TREE

AVL adalah balanced binary search tree dimana ia memiliki perbedaan jumlah node pada subtree kiri dan subtree kanannya maksimal 1 (atau dapat dikatakan antara tingginya sama atau selisih satu).















Cara menentukan Height dan Balance Factor :

Height :
- Jika node (root) tidak memiliki subtree heightnya = 0
- Jika node adalah leaf, height =  1
- Jika internal node, maka height =  height tertinggi dari anak + 1

Balance Factor :
-selisih height antara anak kiri dan kanan, jika tidak memiliki anak, dianggap 0.

AVL Operation 

   - Insertion
         

Insert suatu node pada AVL sama halnya pada insert node pada binary search tree, dimana node baru diposisikan sebagai leaf. Setelah memasukkan node baru, maka harus dilakukan penyeimbangan kembali pada path dari node yang baru di insert atau path terdalam. Namun biasanya, path terdalam adalah path dari node yang baru saja di insert.

Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :

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)

Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi
- Kasus 1 dan 2 dengan single rotation
- Kasus 3 dan 4 dengan double rotation

     1.  Single Rotation

Single rotasi (rotasi 1x) dilakukan apabila searah, left-left atau right-right
 

     2. Double Rotation

Double rotasi (rotasi 2x) dilakukan apabila searah, left-right atau right-left. 
 
First Rotation 
 
Second Rotation

     - Deletion

Operasi penghapusan node sama seperti pada Binary Search Tree, yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus adalah leaf, maka langsung hapus saja. Namun jika node yang dihapus memiliki child maka childnya yang menggantikannya. Namun setelah operasi penghapusan dilakukan, cek kembali apakah tree sudah seimbang atau belum, jika belum maka harus diseimbangkan kembali. Cara menyeimbangkannya pun sama seperti insertion.

 
Delete Node 60

 
Node 55 is Unbalance, cause on the left child is 0 and on the right child is 2
 
Get Balanced with double rotation
 
Balance AVL.


Source:
http://suciantinovi.blogspot.com/2014/05/balanced-binary-tree-and-2-3-tree.html