AVL Tree

AVL Tree

• AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian danbentuk tree dapat dipersingkat dan disederhanakan. Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru→root. Node pertama yang memiliki balance factor > 1 diseimbangkan. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan. 

• Proses penyeimbangan dilakukan dengan: 
1. Single rotation adalah rotasi yang dilakukan apabila data yang diinsert searah, left-left atau right-right.
   
2. Double rotation adalah rotasi yang dilakukan apabila data yang diinsert tidak searah, left-right atau right-left.
   
• Operasi pada AVL:

1. Insertion atau 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.
   
2. Deletion 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. 
   
   
   

Sumber: 

http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html?m=1

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

https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor/