CHAPTER - 31 – AVL TREES

31.1 INTRODUCTION

An AVL (Adelson-Velskii and Landis) tree is a binary search tree with a balance
condition. The balance condition must be easy to maintain, and it ensures that the depth of
the tree is O(log N).

An AVL tree is identical to a binary search tree, except that for every node in the tree,
the height of the left and right subtrees can differ by at most 1. (The height of an empty tree is
defined to be -1.) In Figure 31.1 the tree on the left is an AVL tree but the tree on the right is
not. Height information is kept for each node (in the node structure).

Figure 31.1 Two binary search trees. Only the left tree is AVL.

A balance factor is the height of the left subtree minus height of the right subtree. For an
AVL tree all balance factor should be +1, 0, or -1. If the balance factor of any node in an AVL tree
becomes less than -1 or greater than 1, the tree has to be balanced by making either single or
double rotations.

Thus, all the tree operations can be performed in O(log N) time, except possibly insertion
and deletion. When we do an insertion, we need to update all the balancing information for the
nodes on the path back to the root, but the reason that insertion is potentially difficult is that
inserting a node could violate the AVL tree property. (For instance, inserting 6 into the AVL tree
in Figure 4.31 would destroy the balance condition at the node with key 8.) If this is the case,
then the property has to be restored before the insertion step is considered over. It turns out
that this can always be done with a simple modification to the tree, known as a rotation.

After an insertion, only nodes that are on the path from the insertion point to the root
might have their balance altered because only those nodes have their subtrees altered. As we
follow the path up to the root and update the balancing information, we may find a node whose
new balance violates the AVL condition. We will show how to rebalance the tree at the first (i.e.,
deepest) such node, and we will prove that this rebalancing guarantees that the entire tree
satisfies the AVL property.

Let us call the node that must be rebalanced α. Since any node has at most two children,
and a height imbalance requires that α’s two subtrees’ heights differ by two, it is easy to see
that a violation might occur in four cases:
1. An insertion into the left subtree of the left child of α
2. An insertion into the right subtree of the left child of α
3. An insertion into the left subtree of the right child of α

52 B.BHUVANESWARAN | AP (SG) | CSE | Rajalakshmi Engineering College

 4. An insertion into the right subtree of the right child of α

Cases 1 and 4 are mirror image symmetries with respect to α, as are cases 2 and 3.
Consequently, as a matter of theory, there are two basic cases. From a programming
perspective, of course, there are still four cases.

The first case, in which the insertion occurs on the “outside” (i.e., left–left or right– right),
is fixed by a single rotation of the tree. The second case, in which the insertion occurs on the
“inside” (i.e., left–right or right–left) is handled by the slightly more complex double rotation.

4.4.1 Single Rotation

Figure 31.2 shows the single rotation that fixes case 1. The before picture is on the left
and the after is on the right. Let us analyze carefully what is going on. Node k 2 violates the AVL
balance property because its left subtree is two levels deeper than its right subtree (the dashed
lines in the middle of the diagram mark the levels). The situation depicted is the only possible
case 1 scenario that allows k2 to satisfy the AVL property before an insertion but violate it
afterwards. Subtree X has grown to an extra level, causing it to be exactly two levels deeper
than Z. Y cannot be at the same level as the new X because then k2 would have been out of
balance before the insertion, and Y cannot be at the same level as Z because then k 1 would be
the first node on the path toward the root that was in violation of the AVL balancing condition.

Figure 31.2 Single rotation to fix case 1

To ideally rebalance the tree, we would like to move X up a level and Z down a level. Note
that this is actually more than the AVL property would require. To do this, we rearrange nodes
into an equivalent tree as shown in the second part of Figure 32.2. Here is an abstract scenario:
Visualize the tree as being flexible, grab the child node k1, close your eyes, and shake it, letting
gravity take hold. The result is that k1 will be the new root. The binary search tree property tells
us that in the original tree k2 > k1, so k2 becomes the right child of k1 in the new tree. X and Z
remain as the left child of k1 and right child of k2, respectively. Subtree Y, which holds items that
are between k1 and k2 in the original tree, can be placed as k2’s left child in the new tree and
satisfy all the ordering requirements.

As a result of this work, which requires only a few pointer changes, we have another
binary search tree that is an AVL tree. This happens because X moves up one level, Y stays at
the same level, and Z moves down one level. k2 and k1 not only satisfy the AVL requirements,
but they also have subtrees that are exactly the same height. Furthermore, the new height of
the entire subtree is exactly the same as the height of the original subtree prior to the insertion
that caused X to grow. Thus no further updating of heights on the path to the root is needed,
and consequently no further rotations are needed. Figure 31.3 shows that after the insertion of
6 into the original AVL tree on the left, node 8 becomes unbalanced. Thus, we do a single
rotation between 7 and 8, obtaining the tree on the right.

B.BHUVANESWARAN | AP (SG) | CSE | Rajalakshmi Engineering College 53

 Figure 31.3 AVL property destroyed by insertion of 6, then fixed by a single rotation

Routine to perform single rotation with left

SingleRotateWithLeft(Position K2)
{
Position K1;
K1 = K2  Left;
K2  Left = K1  Right;
K1  Right = K2;
K2  Height = Max(Height(K2  Left), Height(K2  Right)) + 1;
K1  Height = Max(Height(K1  Left), Height(K1  Right)) + 1;
return K1;
}

As we mentioned earlier, case 4 represents a symmetric case. Figure 31.4 shows how a
single rotation is applied.

Figure 31.4 Single rotation fixes case 4

Routine to perform single rotation with right

SingleRotateWithRight(Position K1)
{
Position K2;
K2 = K1  Right;
K1  Right = K2  Left;
K2  Left = K1;
K2  Height = Max(Height(K2  Left), Height(K2  Right)) + 1;
K1  Height = Max(Height(K1  Left), Height(K1  Right)) + 1;
return K2;
}

54 B.BHUVANESWARAN | AP (SG) | CSE | Rajalakshmi Engineering College

B.BHUVANESWARAN | AP (SG) | CSE | Rajalakshmi Engineering College 55
Example 1 - Single Rotation

Let us work through a rather long example. Suppose we start with an initially empty AVL
tree and insert the items 3, 2, 1, and then 4 through 7 in sequential order. The first problem
occurs when it is time to insert item 1 because the AVL property is violated at the root. We
perform a single rotation between the root and its left child to fix the problem. Here are the
before and after trees:

A dashed line joins the two nodes that are the subject of the rotation. Next we insert 4,
which causes no problems, but the insertion of 5 creates a violation at node 3 that is fixed by a
single rotation. Besides the local change caused by the rotation, the programmer must
remember that the rest of the tree has to be informed of this change. Here this means that 2’s
right child must be reset to link to 4 instead of 3. Forgetting to do so is easy and would destroy
the tree (4 would be inaccessible).

Next we insert 6. This causes a balance problem at the root, since its left subtree is of
height 0 and its right subtree would be height 2. Therefore, we perform a single rotation at the
root between 2 and 4.

The rotation is performed by making 2 a child of 4 and 4’s original left subtree the new
right subtree of 2. Every item in this subtree must lie between 2 and 4, so this transformation
makes sense. The next item we insert is 7, which causes another rotation:

56 B.BHUVANESWARAN | AP (SG) | CSE | Rajalakshmi Engineering College

Example 2 - Single Rotation (Case 1)

Inserting the value 1 in the following AVL Tree makes AVL Tree imbalance.

Before After
Example 3 - Single Rotation (Case 4)

Inserting the value 10 in the following AVL Tree makes AVL Tree imbalance.

Before After

B.BHUVANESWARAN | AP (SG) | CSE | Rajalakshmi Engineering College 57

4.4.2 Double Rotation

The algorithm described above has one problem: As Figure 31.5 shows, it does not work
for cases 2 or 3. The problem is that subtree Y is too deep, and a single rotation does not make
it any less deep. The double rotation that solves the problem is shown in Figure 31.6.

Figure 31.5 Single rotation fails to fix case 2

Figure 31.6 Left–right double rotation to fix case 2

The fact that subtree Y in Figure 31.5 has had an item inserted into it guarantees that it
is nonempty. Thus, we may assume that it has a root and two subtrees. Consequently, the tree
may be viewed as four subtrees connected by three nodes. As the diagram suggests, exactly one
of tree B or C is two levels deeper than D (unless all are empty), but we cannot be sure which
one. It turns out not to matter; in Figure 31.6, both B and C are drawn at 1 ½ levels below D.

To rebalance, we see that we cannot leave k3 as the root, and a rotation between k 3 and
k1 was shown in Figure 31.5 to not work, so the only alternative is to place k2 as the new root.
This forces k1 to be k2’s left child and k3 to be its right child, and it also completely determines
the resulting locations of the four subtrees. It is easy to see that the resulting tree satisfies the
AVL tree property, and as was the case with the single rotation, it restores the height to what it
was before the insertion, thus guaranteeing that all rebalancing and height updating is
complete. Figure 31.7 shows that the symmetric case 3 can also be fixed by a double rotation.
In both cases the effect is the same as rotating between α’s child and grandchild, and then
between α and its new child.

Figure 31.7 Right–left double rotation to fix case 3

58 B.BHUVANESWARAN | AP (SG) | CSE | Rajalakshmi Engineering College

Routine to perform double rotation with left

DoubleRotateWithLeft(Position K3)
{
/* Rotation between K1 and K2 */
Position K1;
K1  Left = SingleRotateWithRight(K3  Left);
/* Rotation between K3 and K2 */
return SingleRotateWithLeft(K3);
}

Routine to perform double rotation with right

DoubleRotateWithRight(Position K1)
{
/* Rotation between K2 and K3 */
K1  Right = SingleRotateWithLeft(K1  Right);
/* Rotation between K1 and K2 */
return SingleRotateWithRight(K1);
}

Example 1 - Double Rotation

We will continue our previous example by inserting 10 through 16 in reverse order,

followed by 8 and then 9. Inserting 16 is easy, since it does not destroy the balance property,
but inserting 15 causes a height imbalance at node 7. This is case 3, which is solved by a right–
left double rotation. In our example, the right–left double rotation will involve 7, 16, and 15. In
this case, k1 is the node with item 7, k3 is the node with item 16, and k2 is the node with item
15. Subtrees A, B, C, and D are empty.

Next we insert 14, which also requires a double rotation. Here the double rotation that
will restore the tree is again a right–left double rotation that will involve 6, 15, and 7. In this
case, k1 is the node with item 6, k2 is the node with item 7, and k3 is the node with item 15.
Subtree A is the tree rooted at the node with item 5; subtree B is the empty subtree that was
originally the left child of the node with item 7, subtree C is the tree rooted at the node with
item 14, and finally, subtree D is the tree rooted at the node with item 16.

B.BHUVANESWARAN | AP (SG) | CSE | Rajalakshmi Engineering College 59

 If 13 is now inserted, there is an imbalance at the root. Since 13 is not between 4 and 7,
we know that the single rotation will work.

Insertion of 12 will also require a single rotation:

To insert 11, a single rotation needs to be performed, and the same is true for the
subsequent insertion of 10. We insert 8 without a rotation, creating an almost perfectly
balanced tree:

60 B.BHUVANESWARAN | AP (SG) | CSE | Rajalakshmi Engineering College

 Finally, we will insert 9 to show the symmetric case of the double rotation. Notice that 9
causes the node containing 10 to become unbalanced. Since 9 is between 10 and 8 (which is
10’s child on the path to 9), a double rotation needs to be performed, yielding the following
tree:

B.BHUVANESWARAN | AP (SG) | CSE | Rajalakshmi Engineering College 61

Example:

Let us consider how to balance a tree while inserting the numbers from I to 10.

Insert the value 1.

Balanced Tree

Insert the value 2.

Balanced Tree

Insert the value 3.

Imbalanced Tree Balanced Tree

Here the tree imbalances at the node 1, so the single rotation with left is performed.

Insert the value 4.

Balanced AVL Tree

62 B.BHUVANESWARAN | AP (SG) | CSE | Rajalakshmi Engineering College

Insert the value 5.

Imbalanced Tree Balanced Tree

Tree is imbalanced at node 3, perform the single rotation with left to balance it.

Insert the value 6.

Imbalanced Tree Balanced Tree

Insert the value 7.

Imbalanced Tree Balanced Tree

B.BHUVANESWARAN | AP (SG) | CSE | Rajalakshmi Engineering College 63

 Insert the value 8.

Balanced Tree

Insert the value 9.

Imbalanced Tree Balanced Tree

Insert the value 10.

Imbalanced Tree Balanced Tree

64 B.BHUVANESWARAN | AP (SG) | CSE | Rajalakshmi Engineering College