The AVL Tree came from its inventor's name Adelson Velskii Landis. It is self balancing binary tree also known as the Height Balanced Binary Tree.
In AVL tree, the height of two sub trees of the node may differ by at most one. It structure is same as the binary search tree, but with little difference. The advantages of AVL tree are that it takes O(log n) time to perform searches, insert, delete operations in average case as well as the worst case.
The balance factor is calculated by subtracting the height of its right sub-tree from the height of the left sub-tree. So the balance factor of -1, 0, 1 is considered to be a height balanced tree. A node with other than this value are considered to be unbalanced and need to be rebalancing.
A balanced tree has the following properties.
- If the left sub tree has a longest path than right subtree, then it is left heavy AVL tree.
- If the right sub tree has the longest path than left subtree, then it is right heavy AVL tree.
- If the left and right sub tree has equal path, then it is balanced AVL tree.