AVL TREE
The first type of self-balancing binary search tree to be invented is the AVL tree. The name AVL tree is coined after its inventor's names − Adelson-Velsky and Landis.
In AVL trees, the difference between the heights of left and right subtrees, known as the Balance Factor, must be at most one. Once the difference exceeds one, the tree automatically executes the balancing algorithm until the difference becomes one again.
In an AVL tree, the heights of the two sub-trees of a node may differ by at most one. Due to this property, the AVL tree is also known as a height-balanced tree.
AVL trees are self-balancing,
which means that the tree height is kept to a minimum so that a very fast
runtime is guaranteed for searching, inserting and deleting nodes, with time
complexity O(log n).
In its structure, it stores an additional variable called the BalanceFactor. Thus, every node has a balance factor associated with it.
The balance factor of a node is calculated by
subtracting the height of its right sub-tree from the height of its left
sub-tree. A binary search tree in which every node has a balance factor of –1,
0, or 1 is said to be height balanced. A node with any other balance factor is
considered to be unbalanced and requires rebalancing of the tree.
Balance factor = Height (left
sub-tree) – Height (right sub-tree)
- · If the balance factor of a node is 1, then it means that the left sub-tree of the tree is one level higher than that of the right sub-tree. Such a tree is therefore called as a left-heavy tree.
- · If the balance factor of a node is 0, then it means that the height of the left sub-tree (longest path in the left sub-tree) is equal to the height of the right sub-tree.(balanced AVL tree.)
- · If the balance factor of a node is –1, then it means that the left sub-tree of the tree is one level lower than that of the right sub-tree. Such a tree is therefore called as a right-heavy tree.
Look at Fig a Left-heavy AVL tree. Note that the nodes 18, 39, 54, and 72 have no children, so their balance factor = 0. Node 27 has one left child and zero right child. So, the height of left sub-tree = 1, whereas the height of right sub-tree = 0. Thus, its balance factor = 1. Look at node 36, it has a left sub-tree with height = 2, whereas the height of right sub-tree = 1. Thus, its balance factor = 2 – 1 = 1. Similarly, the balance factor of node 45 = 3 – 2 =1; and node 63 has a balance factor of 0 (1 – 1).
Look at Fig b right-heavy AVL tree. Note that the nodes 70,54,39, and 27 have no children, so their balance factor = 0. Node 72 has one left child and zero right child. So, the height of left sub-tree = 1, whereas the height of right sub-tree = 0. Thus, its balance factor = 1.
Look at node 63 it has a left sub-tree with height = 1, whereas the height of right sub-tree = 2. Thus, its balance factor = 1 – 2 = -1. Similarly, the balance factor of node 45 = 2 – 3 = -1; and node 36 has a balance factor of 0 (1 – 1).
The Four
"out-of-balance" Cases
When the balance factor of just one node is less than -1, or
more than 1, the tree is regarded as out of balance, and a rotation is needed
to restore balance.
There are four different ways an AVL Tree can be out of balance, and each of these cases require a different rotation operation.
Case | Description | Rotation to Restore Balance |
Left-Left (LL) | The unbalanced node and its left child node are both left-heavy. | A single right rotation. |
Right-Right (RR) | The unbalanced node and its right child node are both right-heavy. | A single left rotation. |
Left-Right (LR) | The unbalanced node is left heavy, and its left child node is right heavy. | First do a left rotation on the left child node, then do a right rotation on the unbalanced node. |
Right-Left (RL) | The unbalanced node is right heavy, and its right child node is left heavy. | First do a right rotation on the right child node, then do a left rotation on the unbalanced node. |
Step through the building of an AVL Tree in the animation below to see how the balance factors are updated, and how rotation operations are done when required to restore the balance.
