AVL Tree

An AVL Tree is self-balancing height-balanced Binary Search Tree. AVL stands for the inventors of this tree: Adelson-Velskii and Landis. Search, insertion and deletion are in O(log n) time in both average and worst cases. AVL Tree is better than Red-Black Tree for search operation because it is more strictly balanced.

AVL Tree approximately balances itself. Each node contains the attribute balance factor that indicates if the the sub-tree (whose node is considered as the root) is:

• left-heavy: if the height of the left sub-tree is greater than the height of the right sub-tree.
• balanced: if the height of the left and right sub-trees are the same.
• right-heavy: if the height of the right sub-tree is greater than the height of the left sub-tree.

If an insertion unbalance the tree, a rotation should be done to correct the balance.

Property: Every given pair of sub-trees heights differ by at most 1.

Resources

https://www.cs.auckland.ac.nz/software/AlgAnim/AVL.html
https://en.wikipedia.org/wiki/AVL_tree