The problem with a Binary Search Tree is that it may require O(n) time in the worst case to perform the basic search and insert operations, for example in the case of a skewed tree, like one shown below.
AVL tree is a self-balancing binary search tree in which the difference between the heights of left and right subtrees must not exceed one.
The Balance Factor in AVL Tree
The below expression describes the balance factor for an AVL tree,
balance_factor = height(left_subtree) - height(right_subtree)
The balance factor of any node in an AVL tree is either -1, 0 or +1. If after any modification in the tree, the balance factor becomes less than -1 or greater than +1, the subtree rooted at that node is said to be unbalanced, and a rotation is needed.
For example, in the AVL tree shown in the diagram below,
height(left_subtree) = 2,
height(right_subtree) = 1,
balance factor of node '9' = 2-1 = 1
Dealing with Unbalanced trees
If the balance factor of the tree exceeds |1|(absolute 1), rotations must be performed to make it balanced.
1) Right Rotation (RR)
Sometimes a single right rotation is enough to make the tree balanced as shown in the diagram below.
2) Left Rotation (LL)
Sometimes a single left rotation is enough to make the tree balanced as shown in the diagram below.
3) Left Right Rotation (LR)
Combination of a left rotation and a right rotation.
4) Right Left Rotation (RL)
Conclusion:
In this article we learned what is an AVL tree, how its balance factor works and how the tree can be balanced.
