Balanced Binary Search Trees

As we saw in the previous section, the height of a binary tree with $N$ nodes can be $N$ in the worst case, when no node has more than one child. This means that the worst-case search time in a binary search tree is $O(N)$, which is no better than linear search through a linked-list or array. The point of using a binary search tree is to take advantage of branching to improve on the search time—every time we choose to go left or right, we would like our search space to be cut (roughly) in half, which should give us a running time of $O(\log N)$.

Therefore, when we use a binary search tree we will need to do some work to ensure that it maintains some sort of balance. We will explore several choices for a precise definition of balance.

One definition that will not work is to require a perfect binary tree, where every node has exactly two children except for the leaves, and all of the leaves are at the same level. The problem with this balance condition is that it only works for certain numbers of nodes. Here are perfect binary search trees with 1, 2, and 3 levels:

A perfect binary tree with 4 levels would need 8 more nodes, for a total of 15. It is easy to see that the number of nodes in a perfect binary tree with $k$ levels is $\sum_{i=0}^{k-1} 2^i$, which is $2^k - 1$.

We could modify this definition to require only that our binary search tree be complete, which is like a perfect tree except the bottom row might be only partially filled in, with all of its nodes to the left. Here is an example of a complete binary search tree with 8 nodes:

The number of nodes in a complete binary tree of height $k$ will be between $2^{k-1}$ and $2^k - 1$, which is enough to establish our desired bound of $O(\log N)$ on the running time of search on a complete binary search tree. However, although complete binary trees are useful for some applications, such as heaps, they are not flexible enough to handle binary search tree insertion or deletion efficiently. To get some intuition why this is so, compare the trees above with 7 and 8 nodes, and observe how many nodes would have had to change position just to insert the value "8".

AVL Trees

The key to finding a definition of balance that both guarantees $O(\log N)$ search time and also efficient insertion and deletion is to allow minor imbalances locally. As long as we can guarantee that the local imbalance doesn't accumulate out of control, this will give enough flexibility to enable insertions and deletions to only require local modifications to the tree. In particular, if the only changes needed to the tree's structure are along a single path from the root, we know that they can only take $O(\log N)$ time (because the maximum path lengths are bounded by the height, and the balance condition will ensure a logarithmic bound on the height).

The first such balance condition we will look at is for the AVL Tree, named after its inventors, Georgy Adelson-Velsky and Evgenii Landis. For each node in the tree, we will require that the heights of its children differ by at most one. That is, if we define the balance factor BF(Node(left, value, right)) to be height(right) - height(left), then the AVL condition says that -1 <= BF(n) <= +1 for every node n.

This looser balance condition is enough to guarantee that the height is bounded by the logarithm of the number of nodes,¹ but it is also flexible enough that we can preserve the condition with only minor adjustments as each value is inserted or deleted.

The key to this obervation is the concept of a rotation of a subtree. Suppose the node n has a left child (L) whose height is one greater than its right child (R). This means that L is non-empty, so we may decompose it into its root node (l) and children (ll and lr).

Now we can perform a right rotation by moving node l up to the root and pushing n down into its right child:

This rotation converts a tree with balance factor -1 into one with balance factor +1. Importantly, note that we have also preserved the binary search tree property, because all of the values in the subtree ll are $\leq$ the value in node l, the values in subtree lr are between the values in l and n, and the values in subtree R are $\geq$ the value in n. The rotated tree still has the correct relative positioning of all of these values, but we have "shifted its weight" from the left to the right. We can also perform a left rotation to reverse this operation.

Suppose we have just inserted a value in the left subtree of n that would violate the AVL balance condition. There are two cases to consider: either the subtree ll is too tall (the "Left-Left" case) or the subtree lr is too tall (the "Left-Right" case), depending on which one contains the new element.

In the Left-Left case, a right rotation as shown above will be enough to fix the AVL condition, and the new root l will have balance factor 0:

The Left-Right case is slightly more involved, because a single rotation will leave it unbalanced. However, if we first perform a left rotation on the subtree L we can produce an intermediate tree that looks like the Left-Left case, so a second rotation (this time to the right) on the full subtree will fix up the balance:

We may check that the resulting height of the tree after these modifications is the same as it was before the insertion, so the balance condition further up in the tree will not need further repair. Of course, if the AVL balance condition were violated by insertion in a right child, we would fix it by considering analogous Right-Right and Right-Left cases and performing rotations the other direction.

Here is Scala code that implements AVL tree insertion. As an optimization, we have added a height field to each Tree object, which is computed and saved when the leaf or node is constructed; this avoids multiple traversals of the tree to recompute the heights when checking the balance condition.

object AVLTree {
  enum Tree(val height: Int):
    case Empty extends Tree(0)
    case Node(left: Tree, value: Int, right: Tree) extends Tree(1 + (left.height max right.height))
  import Tree.*

  def insert(t: Tree, x: Int): Tree = {
    t match
      case Empty => Node(Empty, x, Empty)
      case Node(left, value, right) =>
        if x < value then
          rotate(Node(insert(left, x), value, right))
        else
          rotate(Node(left, value, insert(right, x)))
  }

  def rotate(t: Tree): Tree = {
    t match
      case Empty => t
      case Node(left, value, right) =>
        val BF = right.height - left.height
        if BF < -1 then
          val Node(ll, lv, lr) = left
          if ll.height > lr.height then // Left-Left
            Node(ll, lv, Node(lr, value, right))
          else // Left-Right
            val Node(rl, rv, rr) = lr
            Node(Node(Node(ll, lv, rl), rv, rr), value, right)
        else if BF > 1 then
          val Node(rl, rv, rr) = right
          if rl.height < rr.height then // Right-Right
            Node(Node(left, value, rl), rv, rr)
          else // Right-Left
            val Node(ll, lv, lr) = rl
            Node(left, value, Node(ll, lv, Node(lr, rv, rr)))
        else // BF is in valid range
          Node(rotate(left), value, rotate(right))
  }
}

Finally, here is the result of inserting the numbers 1 to 20, in order, into an initially empty AVL tree:

Red-Black Trees

TODO

Here is Scala code that implements Red-Black tree insertion:

object RedBlackTree {
  enum Color:
    case Red
    case Black

  enum Tree:
    case Empty
    case Node(color: Color, left: Tree, value: Int, right: Tree)

  import Color.*
  import Tree.*

  def insert(t: Tree, x: Int): Tree = {
    def aux(t: Tree, x: Int): Tree = {
      t match
      case Empty =>
        Node(Red, Empty, x, Empty)
      case Node(color, left, value, right) =>
        if x < value
        then balance(color, aux(left, x), value, right)
        else balance(color, left, value, aux(right, x))
    }

    def balance(color: Color, left: Tree, value: Int, right: Tree): Tree = {
      (color, left, value, right) match
        case (Black, Node(Red, Node(Red, a, llv, b), lv, lr), value, right) => 
          Node(Red, Node(Black, a, llv, b), lv, Node(Black, lr, value, right))
        case (Black, Node(Red, ll, lv, Node(Red, a, lrv, b)), value, right) => 
          Node(Red, Node(Black, ll, lv, a), lrv, Node(Black, b, value, right))
        case (Black, left, value, Node(Red, Node(Red, a, rlv, b), rv, rr)) => 
          Node(Red, Node(Black, left, value, a), rlv, Node(Black, b, rv, rr))
        case (Black, left, value, Node(Red, rl, rv, Node(Red, a, rrv, b))) => 
          Node(Red, Node(Black, left, value, rl), rv, Node(Black, a, rrv, b))
        case _ => Node(color, left, value, right)
    }

    def makeBlack(t: Tree): Tree = {
      t match
        case Node(Red, left, value, right) =>
          Node(Black, left, value, right)
        case _ => t
    }

    makeBlack(aux(t, x))
  }
}

Here is the result of inserting the numbers 1 to 20, in order, into an initially empty Red-Black tree:

TODO show the colors...

Footnotes

1. Interestingly, we can show that the minimum number of nodes in an AVL tree of height h is proportional to the Fibonacci number $F_h$. This should make sense, because the most unbalanced case is when one child has height $h-1$ and the other has height $h-2$, so the recurrence for the total number of nodes looks like $N(h) = N(h-1) + N(h-2) + 1$. Since the Fibonacci numbers grow exponentially, with growth factor $\varphi=1.618\ldots$ (the Golden Ratio), we can see that the height of an AVL tree with $N$ nodes is at most $\log_\varphi N$. ↩