Skip to main content
Logo image

Problem Solving with Algorithms and Data Structures using Java: The Interactive Edition

Bradley N. Miller, David L. Ranum, Roman Yasinovskyy, J. David Eisenberg

Section 6.18 AVL Tree Implementation

Now that we have demonstrated that keeping an AVL tree in balance is going to be a big performance improvement, let’s look at how we will augment the procedure to insert a new key into the tree. Since all new keys are inserted into the tree as leaf nodes, and we know that the balance factor for a new leaf is zero, there are no new requirements for the node that has just been inserted. But once the new leaf is added, we must update the balance factor of its parent. How this new leaf affects the parent’s balance factor depends on whether the leaf node is a left child or a right child. If the new node is a right child, the balance factor of the parent will be reduced by one. If the new node is a left child, then the balance factor of the parent will be increased by one. This rule can be applied recursively to the grandparent of the new node, and possibly to every ancestor, all the way up to the root of the tree. Since this is a recursive procedure, let’s examine the two base cases for updating balance factors:
  • The recursive call has reached the root of the tree.
  • The balance factor of the parent has been adjusted to zero. You should convince yourself that once a subtree has a balance factor of zero, then the balance of its ancestor nodes does not change.
We will implement the AVL tree in a class named AVLTree It uses a copy of BinarySearchTree as our starting point, changing TreeNode to AVLTreeNode, which adds an integer balanceFactor property. To begin, we will override the put helper method and write a new updateBalance helper method. These methods are shown in Listing 6.18.1. You will notice that the definition for _put is exactly the same as in simple binary search trees except for the addition of the calls to updateBalance on lines 8 and 16.
void put(K key, V value, AVLTreeNode currentNode) {
    if (key.compareTo(currentNode.key) < 0) {
        if (currentNode.leftChild != null) {
            put(key, value, currentNode.leftChild);
        } else {
            currentNode.leftChild = new AVLTreeNode(
                key, value, currentNode);
            updateBalance(currentNode.leftChild);
        }
    } else {
        if (currentNode.rightChild != null) {
            put(key, value, currentNode.rightChild);
        } else {
            currentNode.rightChild = new AVLTreeNode(
                key, value, currentNode);
            updateBalance(currentNode.rightChild);
        }
    }
}

void updateBalance(AVLTreeNode node) {
    if (node.balanceFactor > 1 || node.balanceFactor < -1) {
        rebalance(node);
    } else {
        if (node.parent != null) {
            if (node.isLeftChild()) {
                node.parent.balanceFactor += 1;
            } else if (node.isRightChild()) {
                node.parent.balanceFactor -= 1;
            }

            if (node.parent.balanceFactor != 0) {
                updateBalance(node.parent);
            }
        }
    }
}
Listing 6.18.1.
The new updateBalance method is where most of the work is done. This implements the recursive procedure we just described. It first checks to see if the current node is out of balance enough to require rebalancing (line 22). If that is the case then the rebalancing is done and no further updating to parents is required. If the current node does not require rebalancing then the balance factor of the parent is adjusted. If the balance factor of the parent is nonzero then the algorithm continues to work its way up the tree toward the root by recursively calling updateBalance on the parent.
When a rebalancing of the tree is necessary, how do we do it? Efficient rebalancing is the key to making the AVL Tree work well without sacrificing performance. In order to bring an AVL Tree back into balance, we will perform one or more rotations on the tree.
To understand what a rotation is, let’s look at a very simple example. Consider the tree in the left half of Figure 6.18.2. This tree is out of balance with a balance factor of -2. To bring this tree into balance we will use a left rotation around the subtree rooted at node A.
Figure 6.18.2. Transforming an Unbalanced Tree Using a Left Rotation
To perform a left rotation we essentially do the following:
  1. Promote the right child (B) to be the root of the subtree.
  2. Move the old root (A) to be the left child of the new root.
  3. If new root (B) already has a left child, then make it the right child of the new left child (A). Note: since the new root (B) was the right child of A, the right child of A is guaranteed to be empty at this point. This allows us to add a new node as the right child without any further consideration.
While this procedure is fairly easy in concept, the details of the code are a bit tricky since we need to move things around in just the right order so that all properties of a binary search tree are preserved. Furthermore, we need to make sure to update all of the parent pointers appropriately.
Let’s look at a slightly more complicated tree to illustrate the right rotation. The left side of Figure 6.18.3 shows a tree that is left-heavy and with a balance factor of 2 at the root.
Figure 6.18.3. Transforming an Unbalanced Tree Using a Right Rotation
To perform a right rotation we essentially do the following:
  1. Promote the left child (C) to be the root of the subtree.
  2. Move the old root (E) to be the right child of the new root.
  3. If the new root (C) already has a right child (D) then make it the left child of the new right child (E). Note: since the new root (C) was the left child of E, the left child of E is guaranteed to be empty at this point. This allows us to add a new node as the left child without any further consideration.
Now that you have seen the rotations and have the basic idea of how a rotation works let us look at the code. Listing 6.18.4 shows the code for the left rotation (the rotateRight method is symmetrical to rotateLeft so we will leave it to you to study the code for rotateRight). In line 2 we create a temporary variable to keep track of the new root of the subtree. As we said before, the new root is the right child of the previous root. Now that a reference to the right child has been stored in this temporary variable, we replace the right child of the old root with the left child of the new.
The next step is to adjust the parent pointers of the two nodes. If newRoot has a left child then the new parent of the left child becomes the old root. The parent of the new root is set to the parent of the old root. If the old root was the root of the entire tree then we must set the root of the tree to point to this new root. Otherwise, if the old root is a left child then we change the parent of the left child to point to the new root; otherwise we change the parent of the right child to point to the new root. (lines 11–15). Finally we set the parent of the old root to be the new root. This is a lot of complicated bookkeeping, so we encourage you to trace through this function while looking at Figure 6.18.2.
void rotateLeft(AVLTreeNode rotationRoot) {
    AVLTreeNode newRoot = rotationRoot.rightChild;
    rotationRoot.rightChild = newRoot.leftChild;
    if (newRoot.leftChild != null) {
        newRoot.leftChild.parent = rotationRoot;
    }
    newRoot.parent = rotationRoot.parent;
    if (rotationRoot.isRoot()) {
        root = newRoot;
    } else {
        if (rotationRoot.isLeftChild()) {
            rotationRoot.parent.leftChild = newRoot;
        } else {
            rotationRoot.parent.rightChild = newRoot;
        }
    }
    newRoot.leftChild = rotationRoot;
    rotationRoot.parent = newRoot;
    rotationRoot.balanceFactor = rotationRoot.balanceFactor + 1 -
        Math.min(newRoot.balanceFactor, 0);
    newRoot.balanceFactor = newRoot.balanceFactor + 1 +
        Math.max(rotationRoot.balanceFactor, 0);
}
Listing 6.18.4.
Finally, lines 19-22 require some explanation. In these lines we update the balance factors of the old and the new root. Since all the other moves involve moving entire subtrees, the balance factors of all other nodes are unaffected by the rotation. But how can we update the balance factors without completely recalculating the heights of the new subtrees? Figure 6.18.5 and the following derivation should convince you that these lines are correct.
Figure 6.18.5. A Left Rotation
Figure 6.18.5 shows a left rotation. B and D are the pivotal nodes and A, C, E are their subtrees. Let \(h_x\) denote the height of a particular subtree rooted at node \(x\text{.}\) By definition we know the following:
\begin{gather*} new\_bal(B) = h_A - h_C\\ old\_bal(B) = h_A - h_D \end{gather*}
But we know that the old height of D can also be given by \(1 + max(h_C, h_E)\text{,}\) that is, the height of D is one more than the maximum height of its two children. Remember that \(h_C\) and \(h_E\) have not changed. So, let us substitute that in to the second equation, which gives us
\(old\_bal(B) = h_A - (1 + max(h_C,h_E))\)
and then subtract the two equations. The following steps do the subtraction and use some algebra to simplify the equation for \(new\_bal(B)\text{.}\)
\begin{gather*} new\_bal(B) - old\_bal(B) = h_A - h_C - (h_A - (1 + max(h_C,h_E))) \\ new\_bal(B) - old\_bal(B) = h_A - h_C - h_A + (1 + max(h_C,h_E)) \\ new\_bal(B) - old\_bal(B) = h_A - h_A + 1 + max(h_C,h_E) - h_C \\ new\_bal(B) - old\_bal(B) = 1 + max(h_C,h_E) - h_C \end{gather*}
Next we will move \(old\_bal(B)\) to the right-hand side of the equation and make use of the fact that \(max(a,b)-c = max(a-c, b-c)\text{.}\)
\begin{equation*} new\_bal(B) = old\_bal(B) + 1 + max(h_C - h_C ,h_E - h_C) \end{equation*}
But \(h_E - h_C\) is the same as \(-old\_bal(D)\text{.}\) So we can use another identity that says \(max(-a,-b) = -min(a,b)\text{.}\) So we can finish our derivation of \(new\_bal(B)\) with the following steps:
\begin{gather*} new\_bal(B) = old\_bal(B) + 1 + max(0 , -old\_bal(D))\\ new\_bal(B) = old\_bal(B) + 1 - min(0 , old\_bal(D) \end{gather*}
Now we have all of the parts in terms that we readily know. If we remember that B is rotationRoot and D is newRoot, then we can see this corresponds exactly to the statement on lines 19–20 in Listing 6.18.4, or:
rotationRoot.balanceFactor = rotationRoot.balanceFactor + 1 -
            Math.min(newRoot.balanceFactor, 0);
A similar derivation gives us the equation for the updated node D as well as the balance factors after a right rotation. We leave these as an exercise for you.
Now you might think that we are done. We know how to do our left and right rotations, and we know when we should do a left or right rotation. But take a look at Figure 6.18.6. Since node A has a balance factor of -2 we should do a left rotation. But what happens when we do the left rotation around A?
Figure 6.18.6. An Unbalanced Tree that is More Difficult to Balance
Figure 6.18.7 shows us that after the left rotation we are now out of balance the other way. If we do a right rotation to correct the situation we are right back where we started.
Figure 6.18.7. After a Left Rotation the Tree is Out of Balance in the Other Direction
To correct this problem we must use the following set of rules:
  1. If a subtree needs a left rotation to bring it into balance, first check the balance factor of the right child. If the right child is left-heavy, then do a right rotation on right child followed by the original left rotation.
  2. If a subtree needs a right rotation to bring it into balance, first check the balance factor of the left child. If the left child is right-heavy, then do a left rotation on the left child followed by the original right rotation.
Figure 6.18.8 shows how these rules solve the dilemma we encountered in Figure 6.18.6 and Figure 6.18.7. Starting with a right rotation around node C puts the tree in a position where the left rotation around A brings the entire subtree back into balance.
Figure 6.18.8. A Right Rotation Followed by a Left Rotation
The code that implements these rules can be found in our rebalance method, which is shown in Listing 6.18.9. Rule number 1 from above is implemented by the if statement starting on line 2. Rule number 2 is implemented by the else if statement starting on line 9.
void rebalance(AVLTreeNode node) {
    if (node.balanceFactor < 0) {
        if (node.rightChild.balanceFactor > 0) {
            rotateRight(node.rightChild);
            rotateLeft(node);
        } else {
            rotateLeft(node);
        }
    } else if (node.balanceFactor > 0) {
        if (node.leftChild.balanceFactor < 0) {
            rotateLeft(node.leftChild);
            rotateRight(node);
        } else {
            rotateRight(node);
        }
    }
}
Listing 6.18.9.
By keeping the tree in balance at all times, we can ensure that the get method will run in order \(O(log_2(n))\) time. But the question is at what cost to our put method? Let us break this down into the operations performed by put. Since a new node is inserted as a leaf, updating the balance factors of all the parents will require a maximum of \(log_2(n)\) operations, one for each level of the tree. If a subtree is found to be out of balance, a maximum of two rotations are required to bring the tree back into balance. But each of the rotations works in \(O(1)\) time, so even our put operation remains \(O(log_2(n))\text{.}\)
Listing 6.18.10 shows a program that inserts items into a tree in increasing order.
Listing 6.18.10. Example of Inserting into an AVL Tree
You can see in the output that the tree is rebalancing to ensure that we do not end up with a right-heavy tree.
[Albania]
[Albania [] [Bolivia]]
[Bolivia [Albania] [Germany]]
[Bolivia [Albania] [Germany [] [Lesotho]]]
[Bolivia [Albania] [Lesotho [Germany] [Madagascar]]]
[Lesotho [Bolivia [Albania] [Germany]] [Madagascar [] [South Korea]]]
At this point we have implemented a functional AVL tree, unless you need the ability to delete a node. We leave the deletion of the node and subsequent updating and rebalancing as an exercise for you.
You have attempted of activities on this page.
PrevTopNext