Welcome to Programming and Data Structures

Now that we know how rotations can be used to restructure a tree, we can explore how to use them to maintain balance in a binary search tree. As we discussed in the previous chapter, the efficiency of many binary search tree operations depends on the height of the tree. If the tree becomes unbalanced, with some branches much deeper than others, the performance of operations like insertion, deletion, and lookup can degrade from \(O(\log n)\) to \(O(n)\text{.}\) All of the self-balancing technologies we will explore seek to prevent this and provide some guarantee that the height of the tree remains logarithmic.

The first self balancing structure we will consider is the AVL Tree, named after its inventors G.M. Adelson-Velsky and E.M. Landis. An AVL tree is a binary search tree that maintains a balance condition: for every node in the tree, the heights of the left and right subtrees can differ by at most 1. This balance condition will ensure that the height of the tree remains logarithmic in relation to the number of nodes.

To calculate the balance of nodes efficiently, each node in an AVL tree typically stores its height as an additional piece of data. (Recall that a leaf has a height of 0. This means that if we ever need to reason about the height of an empty subtree, we can consider it to be -1.) When we perform insertions or deletions, that may change the heights of nodes along the path from the modified node back up to the root. So, as we return from our recursive calls, we will need to update the heights of the nodes we visit.

We also need to check the current balance factor of the node. This value is not stored. It is calculated on demand as the difference in the heights of the left and right subtrees. (We will use the convention of height(left) - height(right) though it is arbitrary.) A balance factor of 0, 1, or -1 indicates that the node is balanced. A balance factor greater than 1 or less than -1 indicates that the node is unbalanced and requires rebalancing through rotations.

You can explore this in the animation below.

In the “same direction” case, a single rotation away from the taller child will restore balance. In the “zig-zag” case, we need to perform a double rotation: first a rotation on the child node to straighten out the zig-zag, and then a rotation on the unbalanced node to complete the balancing.

Use the animation below to explore these two cases.

The rotation can happen at any level of the tree. For example, if you insert 900 into the tree shows in the animation above (after resetting it), the imbalance will occur 509. It would have children of height 0 and of 2 and require a left rotation to fix.

In an insertion, we should only need to perform one rotation (single or double) to restore balance. This is because the insertion of a new leaf can only increase the height of the tree by 1, and that increase can only propagate up the tree until it reaches a node that was already balanced. Once we perform a rotation to fix an unbalanced node, the height of the subtree rooted at that node will be restored to what it was before the insertion, preventing further imbalances up the tree.

Deletions can be a bit more complex. Removing a node can decrease the height of the tree, which can cause multiple nodes along the path back to the root to become unbalanced. Therefore, after a deletion, we may need to perform multiple rotations (single or double) as we backtrack up the tree to restore balance at each unbalanced node.