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.

Ketinggian subtree kosong adalah 0. Tinggi daun adalah 1. Ketinggian simpul internal adalah ketinggian maksimum anak-anaknya ditambah 1. Faktor keseimbangan semua node di pohon AVL harus paling banyak 1. 

Operasi pada AVL :
- insertion 

insert node baru pada bst, dimana node baru diposisikan sebagai leaf. Setelah itu, dilakukan penyeimbangan pada path dari node yang baru diinsert.

- deletion

node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan.

Selain itu, terdapat single rotation dan double rotation. Single rotation merupakan rotasi sekali left ke left atau right ke right. Sedangkan double rotation merupakan dua kali rotasi dengan left-right ataupun sebaliknya.