Insertion and deletion of nodes in an AVL tree

Binary search tree#

A binary search tree (BST) is a recursive data structure in which each node has at most two children, and the value of the left child is less than that of the right child according to the chosen property. Recursive means that each node in a binary search tree and its descendants form a binary search tree. A logical outcome of the above definition is that the value of the left child must be less than that of the right child of each node, according to the chosen property.

New York City has a population of 8.8 million and an area of 783 km², Los Angeles has a population of 3.9 million and an area of 1299 km², and Chicago has a population of 2.7 million and an area of 600 km². If a binary search tree is constructed using city names, the tree may look like the following.

If we build the binary search tree using the city area property, it may look like the following.

It is important to note that the structure of a simple binary search tree solely depends upon the sequence in which nodes are inserted in it. If the name property is used and the insertion sequence is Chicago, Los Angeles, and New York, the resulting binary search tree will look like as shown below.

If a binary search tree is built by inserting Honolulu, Huntsville, Lakewood, Boston, Baltimore, Chicago, Newark, and Orlando in sequence, we get the following tree. The numbers next to the city names show the insertion sequence.

If we now insert Pittsburg and Quincy in the above binary search tree it looks like the following.

The above tree is indeed a binary search tree, but the right side looks more like a linked list. The search operation in such trees requires more than $\ln_2N$operations, $N$ in the worst case, where N is the total number of nodes.

AVL tree#

AVL trees solve the problem associated with the binary search trees like the one shown above. AVL trees maintain the balance by performing certain operations on the tree, after nodes are inserted. Let's explore how AVL tree insertion and deletion works.

Basic terminology#

We define some terms which will be used in the discussion of AVL trees.

1. The node in a tree which does not have a parent node is called the root of that tree.

2. A node which does not have any child is called a leaf node.

3. Two nodes that share the same parent are called siblings.

4. All nodes from a given node to the root node of a tree are called its ancestors.

5. All nodes from a given node to leaf nodes, including the leaf nodes, are called its descendants.

6. The maximum number of edges from any node to a leaf node is called the height of the tree or subtree rooted at that node. The height of the tree shown above is 6. The height of the tree or subtree with Boston as root is 1. The height of the tree or subtree with Newark as root is 3.

7. The difference between the heights of the right and the left subtrees of a node is called a balance factor of the node.

In an AVL tree the balance factor of each node must be $-1$, $0$, or $+1$. If, on inserting a new node or deleting an existing node, the balance factor of any node becomes $−2$ or $+2$, appropriate operations are performed on the tree to bring the balance factor of that node within the permissible range.

Inserting a node in an AVL tree#

We start by inserting Honolulu, Huntsville, Lakewood, Boston, Baltimore, Chicago, Newark, and Orlando in sequence, and track how the balance factor changes after each insertion. After inserting Honolulu, the tree looks like this.

Huntsville comes after Honolulu in lexicographic order, so it becomes the right child of Honolulu. New balance factors of both nodes are within the permissible range. Therefore, the tree is still an AVL tree.

Lakewood comes after Huntsville, hence, it becomes the the right child of Huntsville and the tree looks like shown below.

The balance factor of Honolulu is $+2$ and the tree is no longer an AVL tree. If we somehow make Huntsville the root of the tree and Honolulu its left child, the balance factor of all nodes would become $0$ and the tree would again become an AVL tree.

Single rotation#

Treating the arrow from Honolulu to Huntsville as axis of rotation and, keeping Huntsville fixed, perform a counter-clockwise rotation, making Huntsville the root of the tree and Honolulu its left child as shown below. All balance factors are 0 and the tree becomes a valid AVL tree.

Next node to insert is Boston. Boston must become the left child of Honolulu. After the insertion, the tree looks like the following. All balance factors are within the permissible range.

The next node to insert is Baltimore. Baltimore comes before Boston in the lexicographic order, hence, it must become the left child of Boston. After inserting Baltimore, the tree looks like as shown below.

The balance factor of Honolulu is outside the permissible range. So is the balance factor of Huntsville. After inserting a new node, we go up the tree, updating balance factors, and stop at the first node whose balance factor is outside the permissible range. Therefore, we stop at Honolulu and do not go to Huntsville to update its balance factor. That is why there is a question mark after $-3$ in the above tree.

A balance factor of $-2$ indicates the left subtree is bigger than the right one. A clockwise rotation is expected to bring the balance factor within the permissible range. The axis of rotation is Honolulu-Boston as shown below.

Keeping Boston fixed, perform a clockwise rotation to make Honolulu the right child of Boston, and make Boston the left child of Huntsville, as shown below.

It is interesting to note that after performing the clockwise rotation, the balance factor of the node above the axis of rotation, Huntsville in this case, remains unchanged. Before inserting Baltimore, the balance factor of Huntsville was $-1$, and after performing the clockwise rotation, it is still $-1$. This is an interesting and useful result.

The next node in the list is Chicago. Chicago comes after Boston but before Honolulu in the lexicographic order. Hence, it must become the left child of Honolulu. After inserting Chicago, the tree looks like as shown below.

The balance factor of $-2$ shows the left subtree of Huntsville is bigger than the right one. As before, we expect a clockwise rotation would bring the balance factor of the root node within the permissible range. The axis of rotation is Huntsville-Boston as shown below.

Keeping Boston fixed, we rotate Huntsville clockwise to make it the right child of Boston, which incidentally becomes the new root node. The right subtree of Boston is now orphaned as Huntsville has taken its place. That orphaned subtree naturally becomes the left subtree of Huntsville which is without a left subtree after becoming the right child of Boston. The result is shown below.

This rotation did not work! Before the clockwise rotation, Huntsville had a balance factor of $-2$ and after the operation, the new root node Boston has a balance factor of $+2$. We need to find out why the rotation worked in earlier cases and not in this case. If we look at all the previous rotations, the nodes forming the axis of rotation had balance factor with the same sign. In this failed case, the nodes forming the axis of rotation had opposite signs. That is the reason the rotation operation failed to bring the balance factor within the permissible range.

Double rotation#

The solution is simple; make the balance factor of Boston negative. The tree, before the rotation operation, was in the state shown below.

We want to make the balance factor of Boston negative. To accomplish this, we perform a counter-clockwise rotation on the Boston-Honolulu axis as shown below.

Keeping Honolulu fixed, rotate Boston counter-clockwise to become the left child of Honolulu. Chicago is orphaned by this operation and must become the right child of Boston which does not have a right child after rotation. Here is what the resulting tree looks like.

Once the balance factors have the same sign, we perform a clockwise rotation on the Huntsville-Honolulu axis. Honolulu becomes the new root node, and Huntsville becomes its right subtree, as shown below.

The above operation is called a double rotation. A double rotation is required when the nodes on the axis of rotation have balance factors of opposite signs. If balance factors have the same sign, a single clockwise or counter-clockwise rotation is sufficient to bring the balance factor within the permissible range.

The next node to insert is Newark. It comes after Lakewood in the lexicographic order. Hence, it must become the right child of Lakewood, as shown below.

Axis of rotation is Huntsville-Lakewood. Both nodes have positive balance factors. A single counter-clockwise rotation is required. After the counter-clockwise rotation, the tree looks as shown below.

Types of balancing operations#

When the balance factor of a node exceeds the permissible range, one of the four possible types of rotations must be performed to bring the balance factor within the permissible range.

We first consider the case in which the balance factor of a node goes from $+1$ to $+2$. The state of the tree before the insertion that causes imbalance is shown below. $T_1$, $T_2$, and $T_3$ are AVL trees with height $h$.

The balance factor of node $B$ is $0$ and that of node $A$ is $+1$. The tree with root node $A$ is a balanced tree. Any new node inserted in the tree would end up in either the subtree $T_1$ or the subtree $T_2$ or the subtree $T_3$. If the new node is inserted in $T_1$, the balance factor of node $A$ would decrease from $+1$ to $0$. This is not what we want—we want the balance factor of node$A$ to increase from $+1$ to $+2$. This can only happen if the new node is inserted in either the subtree $T_2$ or the subtree $T_3$. It is important to keep in mind that after the insertion operation, node $A$ is the first node which becomes unbalanced; neither of its subtrees lose balance. We will discuss both cases but first consider the case where the new node is inserted in $T_3$ causing its height to increase from $h$to $h+1$.

The balance factor of node $B$ will increase from $0$ to $+1$, and that of node $A$ will increase from $+1$ to $+2$. A rotation operation is required to bring the balance factor of node $A$within the permissible range. The axis of rotation is $A\rule[0.25em]{0.15in}{0.5pt} B$ and both nodes have positive balance factors. A single counter-clockwise rotation is required. After performing the rotation operation, node $B$ becomes the new root node and node $A$, along with its left subtree $T_1$, becomes the left child of node $B$. The left subtree of node $B$ is orphaned and must be attached to node $A$ which, after rotation, has no right child or subtree. The state of the tree after the rotation operation is shown below.

We now talk about the case where the new node ends up in subtree $T_2$. This changes the balance factor of node $B$from $0$ to $-1$. The balance factor of node $A$ goes from $+1$ to $+2$ just as in the previous case where the new node ended up in the subtree $T_3$.

Once again, the node that loses balance is $A$, and the axis of a counter-clockwise rotation is $A\rule[0.25em]{0.15in}{0.5pt} B$. However, in this case the balance factors of the nodes have opposite signs. Hence, a double rotation is required; first rotation to make the balance factor of node $B$ positive, followed by the second rotation to bring all balance factors within the permissible range.

The axis of rotation to make the balance factor of node $B$ positive, by performing a clockwise rotation, consists of node $B$ and its left child. We have to zoom in on subtree $T_2$, to reveal the left child of node $B$ as shown below.

Node $C$ is the left child of node $B$. While we know the new node ends up in the left subtree of node $B$, we do not know whether it ends up in the subtree $T_{2L}$ or the subtree $T_{2R}$. Furthermore, the height of the tree with node $C$ as its root must change after insertion because otherwise the height of the left subtree of node $B$ would not change, and as a result, that of node $A$ would also not change. This leads us to the conclusion that before the insertion both subtrees $T_{2L}$ and $T_{2R}$ had height $h-1$ and after the insertion one of them has height $h$ and the other one has height $h-1$. This is depicted in the above figure by dotted lines in subtrees $T_{2L}$ and $T_{2R}$.

After performing a clockwise rotation on $B\rule[0.25em]{0.15in}{0.5pt} C$ axis with $C$ fixed, the balance factor of the new right child of node $A$ becomes positive, as shown in the figure below.

Since the balance factors of both node $A$ and its right child node $C$ are positive, we can perform a counter-clockwise rotation along $A\rule[0.25em]{0.15in}{0.5pt} C$ axis with node $C$ fixed. The node $C$ becomes the new root node of the tree and node $A$ becomes the left child of node $C$, as shown below.

The balance factor of the new root node (node $C$) is $0$. The left subtree of node $C$ has a balance factor of $0$ or $-1$, depending on the height of $T_{2L}$. Similarly the balance factor of the right subtree of node $C$ is either $+1$ or $0$, depending on the height of height of $T_{2R}$.

In the foregoing paragraphs we discussed operations to perform when the balance factor of a node becomes $+2$. If the balance factor of a node becomes $-2$, operations similar to the ones described above are performed to bring the balance factor of the node within the permissible range. If balance factors of the unbalanced node and its left child have the same sign, only a single clockwise rotation is required, as shown below.

After the single clockwise rotation, node $B$ becomes the new root note of the tree and node $A$ becomes its right child and the subtree $T_2$ becomes the left subtree of node $A$, as shown below.

If the balance factors have opposite signs, a counter-clockwise rotation followed by a clockwise rotation is required. In the figure shown below, the balance factors of nodes $A$ and $B$ are of opposite signs. A single rotation along the $A\rule[0.25em]{0.15in}{0.5pt} B$ axis will not fix the imbalance.

To make the balance factor of node $B$ negative, we have to zoom in on the subtree $T_1$ as shown in the figure below. The right child of node $B$ is labeled $C$, and the left and the right subtrees of node $C$ are labeled $T_{2L}$ and $T_{2R}$in the figure. As discussed previously, the height of one of the subtrees of node $C$ is $h$ and that of the other one is $h-1$.

We first perform a single counter-clockwise rotation to make the balance factor of node $B$ negative. The first rotation is performed on $B\rule[0.25em]{0.15in}{0.5pt} C$ axis with node $C$ fixed. The rotation is counter-clockwise. The result of this rotation is shown below. The new left child of node $A$ is node $C$.

In the figure above, node $A$ and its left child have balance factors of the same sign. A single clockwise rotation about $A\rule[0.25em]{0.15in}{0.5pt} C$ axis, with node $C$ fixed, is required. The new root node of the tree is node $C$, as shown below.

If the balance factor of node C is $-1$, after the tri-node rebalance, the left child of the new root node will have a balance factor of $0$ and the right child will have a balance factor of $+1$. If the balance factor of node C is $+1$, after the tri-node rebalance, the left child of the new root node will have a balance factor of $-1$ and the right child will have a balance factor of 0. If the balance factor of node C is $0$, after the tri-node rebalance, both children of the new root node will have a balance factor of $0$.

Deleting a node from a BST#

Deleting a node from a binary search tree is slightly more involved than insertion. Deleting a leaf node is simple; just update the parent node and we are done. If the node to be deleted has only one subtree, that subtree is attached to the parent of the deleted node and we are done. If, however, the node to be deleted has both left and right subtrees, we have to bring another node in its place. Consider the binary search tree shown below:

Suppose we want to delete the node 70. This node has two subtrees. We want to maintain the binary search property of the tree after the node 70 is deleted. There are only two options. We can replace the node 70 with the smallest value node (leftmost node) of its right subtree or the largest value node (rightmost node) of its left subtree.

The leftmost node of the right subtree has the smallest value in the right subtree and is greater than that of the node we want to delete. The rightmost node of the left subtree has the largest value in the left subtree and is smaller than that of the node we want to delete. The right subtree of node 70 is shown below.

The leftmost node of the above tree is 75. This node can replace the node 70 while maintaining the binary search property of the tree. Moving node 75 to the position of the deleted node 70 will orphan the right subtree of node 75. We attached the right subtree of node 75 with its parent which is node 80, as shown below.

The state of the binary search tree after deleting node 70 and bringing node 75 in its place is shown below.

Instead of replacing the node 70 with the leftmost node of its right subtree, let's replace it with the rightmost node of its left subtree. The left subtree of node 70 is shown below.

The rightmost node of the above tree is node 65. We can replace node 70 with this node and the binary search property of the tree will be maintained. We attached the left subtree of node 65 with its parent, which is node 55, as shown below.

The state of the tree after replacing node 70 with node 65 is shown below.

Deleting node from an AVL tree#

Let's consider the AVL tree of some three-digit prime numbers shown below. The numbers within the parentheses are the balance factors of the nodes.

When a node is deleted from an AVL tree, the heights and balance factors of all its ancestor nodes may change. If we delete the node 211, the heights and balance factors of all highlighted nodes may change, as shown below.

Before deleting node 211, the balance factor of its parent node 197 was $+1$ and that of its grandparent node 227 was $0$. After deleting the node, the new balance factors are $0$ and $+1$ respectively. The balance factor of root node 179 is not changed. The state of the AVL tree after deleting node 211 is shown below.

After the delete operation, if the balance factor of any node goes from $0$ to $+1$ or from $0$ to $-1$, the height of the tree rooted at that node does not change. If, on the other hand, after the delete operation, the balance factor of any node goes from $+1$ to or from $-1$ to $0$, the height of the tree rooted at that node changes. The height is reduced. If the balance factor, after delete operation, goes from $+1$ to $+2$ or from $-1$ to $-2$, single or double rotation is required at that node. The following table lists all cases.

Continuing our discussion, let's delete the leaf node 197. The nodes affected by this operation are highlighted below, along with their balance factors. The parent of the deleted node, as a result of delete operation, has become unbalanced.

A counter-clockwise rotation operation must be performed to balance the tree. The axis of rotation is $227\rule[0.25em]{0.15in}{0.5pt}241$, highlighted below.

The two nodes forming the axis of rotation have balance factors of opposite signs. Therefore, a single rotation will not fix the imbalance. A double rotation is required. The first rotation will make the balance factor of child of node 227 positive, and the second one will remove the imbalance of node 227. The axis of the first rotation is $241\rule[0.25em]{0.15in}{0.5pt}233$, and is highlighted below.

A clockwise rotation makes node 233 the right child of node 227, and node 241 becomes the right child of node 233, as shown below, with the axis of second rotation highlighted.

After the second rotation, which is counter-clockwise rotation about $227\rule[0.25em]{0.15in}{0.5pt}233$ axis, the state of the tree is shown below.

The height of the right subtree of the root node has reduced and the root node itself has become unbalanced. We have to fix the imbalance. The balance factor of the root node is $-2$. A clockwise rotation is required. The axis of rotation is $179\rule[0.25em]{0.15in}{0.5pt}137$, as shown below.

Since the balance factors of the nodes forming the axis of rotation have opposite signs, a single rotation will not restore balance. A double rotation is required; a counter-clockwise rotation about $137\rule[0.25em]{0.15in}{0.5pt}157$ to make the balance factor of the left child of the root node negative, followed by a clockwise rotation to balance the root node.

When the counter-clockwise rotation is performed, node 157 becomes the left child of the root node, node 137 becomes the right child of node 157, and the left subtree of node 157 becomes the right subtree of node 137, as shown below.

The new left child of the root node is 157, and the new axis for the second of the two rotations is $179\rule[0.25em]{0.15in}{0.5pt}157$, as shown below.

Since both nodes of the axis of rotation have balance factors of the same sign, a clockwise rotation will fix the imbalance of the new root node, as shown below.

We have seen that deleting a leaf node caused two double rotations to restore the balance and bring in a new root node. This is how the delete operation is different from the insert operations. When a node becomes unbalanced after an inert operation, one single or one double rotation restores the balance as well as the balance factors of the nodes above that level do not change. In contrast, when a node becomes unbalanced after a delete operation, restoring the balance by performing a single or a double rotation may cause a ripple effect all the way up to the root node.

Deleting an internal node#

The two nodes that we deleted above, and balanced the tree afterwards, were leaf nodes. We now consider the case in which a non-leaf node is deleted. We will see the steps required to balance the tree when an internal (non-leaf) node is deleted. Let's consider the AVL tree below.

We want to delete node 227 from the AVL tree shown above. This node has both left and right subtrees. To delete this node, we have to replace it with the rightmost node of its left subtree or the leftmost node of its right subtree. We replace the node to delete with the rightmost node of its left subtree. This is node 211.

Moving node 211 to the position of the deleted node makes node 197 unbalanced, as shown below.

A balance factor of $-2$ means a clockwise rotation is required. The axis of rotation would be the unbalanced node and its left child, $197\rule[0.25em]{0.15in}{0.5pt}191$ in this case.

The two nodes forming the axis of rotation have balance factors of opposite signs. A single rotation would not work. A double rotation is required; a counter-clockwise rotation on $191\rule[0.25em]{0.15in}{0.5pt}193$ axis, followed by a clockwise rotation.

The state of the tree after the counter-clockwise rotation is shown below.

Since both nodes have balance factors of the same sign, a single clockwise rotation will balance the nodes, as shown below.

Propagation of effect of delete#

In the above example, the root node was not affected. Let's look at an example where the root node will also be affected. Consider the AVL tree shown below.

The above AVL tree is a slightly modified version of the one discussed previously. We have added a two-digit prime number to the tree to illustrate delete operation on an internal node. Once again, we delete node 227. After deleting the node 227 and fixing the imbalance, the state of the tree is shown below.

The double rotation operation shown above has made the root node unbalanced. A clockwise rotation is required to fix the imbalance of the root node. The axis of rotation is $179\rule[0.25em]{0.15in}{0.5pt}137$, and both nodes of the axis have negative balance factors. Therefore, a single clockwise rotation fixes the imbalance of the new root node, as shown below.

Double rotation as a single operation#

Now that we have discussed the insert and the delete operation with examples, it is important to point out that double rotations as discussed above were meant to make it easier to understand the balancing operation when the nodes forming the axis of rotation have balance factors of opposite signs. While implementing this operation on a computer, we only look at the signs of the balance factors and re-arrange all three nodes in one step. We may call this operation a tri-node rearrangement or a tri-node rebalance. We show the operation in the following figure.

Summary#

Following are the main points of the above discussion about AVL tree insertion and deletion:

• Insert operation either leaves the height of a tree and its subtrees unchanged or increases it.

  • If the height of a tree/subtree remains unchanged, the balance factors of all ancestor nodes remain unchanged.

  • If the height of a tree/subtree increases, the balance factor of its immediate ancestor changes but the height of its immediate ancestor may or may not change.

  • The balance factor of a node may change from

    • $-1\to-2$ (height increases)

    • $-1\to0$ (height unchanged)

    • $0\to-1$ (height increases)

    • $0\to+1$ (height increases)

    • $+1\to0$ (height unchanged)

    • $+1\to+2$ (height increases)

  • If the balance factor of a node becomes $-2$, and the balance factor of its left child is negative, a single clockwise rotation fixes the imbalance.

  • If the balance factor of a node becomes $-2$, and the balance factor of its left child is positive, a double rotation (counter-clockwise rotation followed by clockwise rotation) fixes the imbalance.

  • If the balance factor of a node becomes $+2$, and the balance factor of its right child is positive, a single counter-clockwise rotation fixes the imbalance.

  • If the balance factor of a node becomes $+2$, and the balance factor of its right child is negative, a double rotation (clockwise rotation followed by counter-clockwise rotation) fixes the imbalance.

  • Once a single or a double rotation is performed, the balance factors of all nodes above that level remain unchanged.

• The delete operation leaves the height of a tree and its subtrees unchanged or decreases it.

  • If the height of a tree/subtree remains unchanged, the balance factors of all ancestor nodes remain unchanged.

  • If the height of a tree/subtree is reduced, the balance factors of, at least some, ancestor nodes change

  • The balance factor of a node may change from

    • $-1\to-2$

    • $-1\to0$

    • $0\to-1$

    • $0\to+1$

    • $+1\to0$

    • $+1\to+2$

  • If the balance factor of a node becomes $+2$ or $-2$, and the balance factor of the appropriate child node has the same sign, a single rotation fixes the imbalance.

  • If the balance factor of a node becomes $+2$ or $-2$, and the balance factor of the appropriate child node has the opposite sign, a double rotation fixes the imbalance. We also call it tri-node rearrangement or tri-node rebalance.

  • After a single or a double rotation, the height of the tree is reduced, and this may lead to more single or double rotations further up the tree.

  • Unlike the insert operation, the effect of the delete operation must be checked all the way up to the root node and may bring in a new node at root level.

References#

Explore the following courses from Educative to learn more about AVL trees.

1. Advanced Programming Techniques in C

2. Data Structures for Coding Interviews in Java

3. Data Structures for Coding Interviews in C++