9.2 RedBlackTree: A Simulated 2-4 Tree

A red-black tree is a binary search tree in which each node, $\mathtt{u}$, has a color which is either red or black. Red is represented by the value 0 and black by the value $1$.

    class Node<T> extends BinarySearchTree.BSTNode<Node<T>,T> {
        byte color;
    }

Before and after any operation on a red-black tree, the following two properties are satisfied. Each property is defined both in terms of the colors red and black, and in terms of the numeric values 0 and 1.

Property 9..3 (black-height)   There are the same number of black nodes on every root to leaf path. (The sum of the colors on any root to leaf path is the same.)

Property 9..4 (no-red-edge)   No two red nodes are adjacent. (For any node $\mathtt{u}$, except the root, $\ensuremath{\mathtt{u.color}} + \ensuremath{\mathtt{u.parent.color}} \ge 1$.)

Notice that we can always color the root, $\mathtt{r}$, of a red-black tree black without violating either of these two properties, so we will assume that the root is black, and the algorithms for updating a red-black tree will maintain this. Another trick that simplifies red-black trees is to treat the external nodes (represented by $\mathtt{nil}$) as black nodes. This way, every real node, $\mathtt{u}$, of a red-black tree has exactly two children, each with a well-defined color. An example of a red-black tree is shown in Figure 9.4.

Figure 9.4: An example of a red-black tree with black-height 3. External ( $\mathtt{nil}$) nodes are drawn as squares.

9.2.1 Red-Black Trees and 2-4 Trees

At first it might seem surprising that a red-black tree can be efficiently updated to maintain the black-height and no-red-edge properties, and it seems unusual to even consider these as useful properties. However, red-black trees were designed to be an efficient simulation of 2-4 trees as binary trees.

Refer to Figure 9.5. Consider any red-black tree, $T$, having $\mathtt{n}$ nodes and perform the following transformation: Remove each red node $\mathtt{u}$ and connect $\mathtt{u}$'s two children directly to the (black) parent of $\mathtt{u}$. After this transformation we are left with a tree $T'$ having only black nodes.

Figure 9.5: Every red-black tree has a corresponding 2-4 tree.

Every internal node in $T'$ has 2, 3, or 4 children: A black node that started out with two black children will still have two black children after this transformation. A black node that started out with one red and one black child will have three children after this transformation. A black node that started out with two red children will have 4 children after this transformation. Furthermore, the black-height property now guarantees that every root-to-leaf path in $T'$ has the same length. In other words, $T'$ is a 2-4 tree!

The 2-4 tree $T'$ has $\ensuremath{\mathtt{n}}+1$ leaves that correspond to the $\ensuremath{\mathtt{n}}+1$ external nodes of the red-black tree. Therefore, this tree has height $\log (\ensuremath{\mathtt{n}}+1)$. Now, every root to leaf path in the 2-4 tree corresponds to a path from the root of the red-black tree $T$ to an external node. The first and last node in this path are black and at most one out of every two internal nodes is red, so this path has at most $\log (\ensuremath{\mathtt{n}}+1)$ black nodes and at most $\log(\ensuremath{\mathtt{n}}+1)-1$ red nodes. Therefore, the longest path from the root to any internal node in $T$ is at most

$$2\log(\ensuremath{\mathtt{n}}+1) -2 \le 2\log \ensuremath{\mathtt{n}} \enspace ,$$

for any $\ensuremath{\mathtt{n}}\ge 1$. This proves the most important property of red-black trees:

Lemma 9..2   The height of red-black tree with $\mathtt{n}$ nodes is at most $2\log \ensuremath{\mathtt{n}}$.

Now that we have seen the relationship between 2-4 trees and red-black trees, it is not hard to believe that we can efficiently maintain a red-black tree while adding and removing elements.

We have already seen that adding an element in a BinarySearchTree can be done by adding a new leaf. Therefore, to implement $\mathtt{add(x)}$ in a red-black tree we need a method of simulating splitting a degree 5 node in a 2-4 tree. A degree 5 node is represented by a black node that has two red children one of which also has a red child. We can ``split'' this node by coloring it red and coloring its two children black. An example of this is shown in Figure 9.6.

Figure 9.6: Simulating a 2-4 tree split operation during an addition in a red-black tree. (This simulates the 2-4 tree addition shown in Figure 9.2.)

Similarly, implementing $\mathtt{remove(x)}$ requires a method of merging two nodes and borrowing a child from a sibling. Merging two nodes is the inverse of a split (shown in Figure 9.6), and involves coloring two (black) siblings red and coloring their (red) parent black. Borrowing from a sibling is the most complicated of the procedures and involves both rotations and recoloring of nodes.

Of course, during all of this we must still maintain the no-red-edge property and the black-height property. While it is no longer surprising that this can be done, there are a large number of cases that have to be considered if we try to do a direct simulation of a 2-4 tree by a red-black tree. At some point, it just becomes simpler to forget about the underlying 2-4 tree and work directly towards maintaining the red-black tree properties.

9.2.2 Left-Leaning Red-Black Trees

There is no single definition of a red-black tree. Rather, there are a family of structures that manage to maintain the black-height and no-red-edge properties during $\mathtt{add(x)}$ and $\mathtt{remove(x)}$ operations. Different structures go about it in different ways. Here, we implement a data structure that we call a RedBlackTree. This structure implements a particular variant of red-black trees that satisfies an additional property:

Property 9..5 (left-leaning)   At any node $\mathtt{u}$, if $\mathtt{u.left}$ is black, then $\mathtt{u.right}$ is black.

Note that the red-black tree shown in Figure 9.4 does not satisfy the left-leaning property; it is violated by the parent of the red node in the rightmost path.

The reason for maintaining the left-leaning property is that it reduces the number of cases encountered when updating the tree during $\mathtt{add(x)}$ and $\mathtt{remove(x)}$ operations. In terms of 2-4 trees, it implies that every 2-4 tree has a unique representation: A node of degree 2 becomes a black node with 2 black children. A node of degree 3 becomes a black node whose left child is red and whose right child is black. A node of degree 4 becomes a black node with two red children.

Before we describe the implementation of $\mathtt{add(x)}$ and $\mathtt{remove(x)}$ in detail, we first present some simple subroutines used by these methods that are illustrated in Figure 9.7. The first two subroutines are for manipulating colors while preserving the black-height property. The $\mathtt{pushBlack(u)}$ method takes as input a black node $\mathtt{u}$ that has two red children and colors $\mathtt{u}$ red and its two children black. The $\mathtt{pullBlack(u)}$ method reverses this operation:

    void pushBlack(Node<T> u) {
        u.color--;
        u.left.color++;
        u.right.color++;
    }
    void pullBlack(Node<T> u) {
        u.color++;
        u.left.color--;
        u.right.color--;
    }

Figure 9.7: Flips, pulls and pushes

The $\mathtt{flipLeft(u)}$ method swaps the colors of $\mathtt{u}$ and $\mathtt{u.right}$ and then performs a left rotation at $\mathtt{u}$. This reverses the colors of these two nodes as well as their parent-child relationship:

    void flipLeft(Node<T> u) {
        swapColors(u, u.right);
        rotateLeft(u);
    }

The $\mathtt{flipLeft(u)}$ operation is especially useful in restoring the left-leaning property at a node $u$ that violates it (because $\mathtt{u.left}$ is black and $\mathtt{u.right}$ is red). In this special case, we can be assured this operation preserves both the black-height and no-red-edge properties. The $\mathtt{flipRight(u)}$ operation is symmetric to $\mathtt{flipLeft(u)}$ with the roles of left and right reversed.

    void flipRight(Node<T> u) {
        swapColors(u, u.left);
        rotateRight(u);
    }

9.2.3 Addition

To implement $\mathtt{add(x)}$ in a RedBlackTree, we perform a standard BinarySearchTree insertion, which adds a new leaf, $\mathtt{u}$, with $\ensuremath{\mathtt{u.x}}=\ensuremath{\mathtt{x}}$ and set $\ensuremath{\mathtt{u.color}}=\ensuremath{\mathtt{red}}$. Note that this does not change the black height of any node, so it does not violate the black-height property. It may, however, violate the left-leaning property (if $\mathtt{u}$ is the right child of its parent) and it may violate the no-red-edge property (if $\mathtt{u}$'s parent is $\mathtt{red}$). To restore these properties, we call the method $\mathtt{addFixup(u)}$.

    boolean add(T x) {
        Node<T> u = newNode(x);
        u.color = red;
        boolean added = add(u);
        if (added)
            addFixup(u);
        return added;
    }

The $\mathtt{addFixup(u)}$ method, illustrated in Figure 9.8, takes as input a node $\mathtt{u}$ whose color is red and which may be violating the no-red-edge property and/or the left-leaning property. The following discussion is probably impossible to follow without referring to Figure 9.8 or recreating it on a piece of paper. Indeed, the reader may wish to study this figure before continuing.

Figure 9.8: A single round in the process of fixing Property 2 after an insertion.

If $\mathtt{u}$ is the root of the tree, then we can color $\mathtt{u}$ black and this restores both properties. If $\mathtt{u}$'s sibling is also red, then $\mathtt{u}$'s parent must be black, so both the left-leaning and no-red-edge properties already hold.

Otherwise, we first determine if $\mathtt{u}$'s parent, $\mathtt{w}$, violates the left-leaning property and, if so, perform a $\mathtt{flipLeft(w)}$ operation and set $\ensuremath{\mathtt{u}}=\ensuremath{\mathtt{w}}$. This leaves us in a well-defined state: $\mathtt{u}$ is the left child of its parent, $\mathtt{w}$, so $\mathtt{w}$ now satisfies the left-leaning property. All that remains is to ensure the no-red-edge property at $\mathtt{u}$. We only have to worry about the case where $\mathtt{w}$ is red, since otherwise $\mathtt{u}$ already satisfies the no-red-edge property.

Since we are not done yet, $\mathtt{u}$ is red and $\mathtt{w}$ is red. The no-red-edge property (which is only violated by $\mathtt{u}$ and not by $\mathtt{w}$) implies that $\mathtt{u}$'s grandparent $\mathtt{g}$ exists and is black. If $\mathtt{g}$'s right child is red, then the left-leaning property ensures that both $\mathtt{g}$'s children are red, and a call to $\mathtt{pushBlack(g)}$ makes $\mathtt{g}$ red and $\mathtt{w}$ black. This restores the no-red-edge property at $\mathtt{u}$, but may cause it to be violated at $\mathtt{g}$, so the whole process starts over with $\ensuremath{\mathtt{u}}=\ensuremath{\mathtt{g}}$.

If $\mathtt{g}$'s right child is black, then a call to $\mathtt{flipRight(g)}$ makes $\mathtt{w}$ the (black) parent of $\mathtt{g}$ and gives $\mathtt{w}$ two red children, $\mathtt{u}$ and $\mathtt{g}$. This ensures that $\mathtt{u}$ satisfies the no-red-edge property and $\mathtt{g}$ satisfies the left-leaning property. In this case we can stop.

    void addFixup(Node<T> u) {
        while (u.color == red) {
            if (u == r) { // u is the root - done
                u.color = black;
                return;
            }
            Node<T> w = u.parent;
            if (w.left.color == black) { // ensure left-leaning
                flipLeft(w);
                u = w;
                w = u.parent;
            }
            if (w.color == black)
                return; // no red-red edge = done
            Node<T> g = w.parent; // grandparent of u
            if (g.right.color == black) {
                flipRight(g);
                return;
            } else {
                pushBlack(g);
                u = g;
            }
        }
    }

The $\mathtt{insertFixup(u)}$ method takes constant time per iteration and each iteration either finishes or moves $\mathtt{u}$ closer to the root. This implies that the $\mathtt{insertFixup(u)}$ method finishes after $O(\log \ensuremath{\mathtt{n}})$ iterations in $O(\log \ensuremath{\mathtt{n}})$ time.

9.2.4 Removal

The $\mathtt{remove(x)}$ operation in a RedBlackTree is the most complicated operation to implement, and this is true of all known implementations. Like $\mathtt{remove(x)}$ in a BinarySearchTree, this operation boils down to finding a node $\mathtt{w}$ with only one child, $\mathtt{u}$, and splicing $\mathtt{w}$ out of the tree by having $\mathtt{w.parent}$ adopt $\mathtt{u}$.

The problem with this is that, if $\mathtt{w}$ is black, then the black-height property will now be violated at $\mathtt{w.parent}$. We get around this problem, temporarily, by adding $\mathtt{w.color}$ to $\mathtt{u.color}$. Of course, this introduces two other problems: (1)  $\mathtt{u}$ and $\mathtt{w}$ both started out black, then $\ensuremath{\mathtt{u.color}}+\ensuremath{\mathtt{w.color}}=2$ (double black), which is an invalid color. If $\mathtt{w}$ was red, then it is replaced by a black node $\mathtt{u}$, which may violate the left-leaning property at $\ensuremath{\mathtt{u.parent}}$. Both of these problems are resolved with a call to the $\mathtt{removeFixup(u)}$ method.

    boolean remove(T x) {
        Node<T> u = findLast(x);
        if (u == nil || compare(u.x, x) != 0)
            return false;
        Node<T> w = u.right;
        if (w == nil) {
            w = u;
            u = w.left;
        } else {
            while (w.left != nil)
                w = w.left;
            u.x = w.x;
            u = w.right;
        }
        splice(w);
        u.color += w.color;
        u.parent = w.parent;
        removeFixup(u);
        return true;
    }

The $\mathtt{removeFixup(u)}$ method takes as input a node $\mathtt{u}$ whose color is black (1) or double-black (2). If $\mathtt{u}$ is double-black, then $\mathtt{removeFixup(u)}$ performs a series of rotations and recoloring operations that move the double-black node up the tree until it can be gotten rid of. During this process, the node $\mathtt{u}$ changes until, at the end of this process, $\mathtt{u}$ refers to the root of the subtree that has been changed. The root of this subtree may have changed color. In particular, it may have gone from red to black, so the $\mathtt{removeFixup(u)}$ method finishes by checking if $\mathtt{u}$'s parent violates the left-leaning property and, if so, fixes it.

    void removeFixup(Node<T> u) {
        while (u.color > black) {
            if (u == r) {
                u.color = black;
            } else if (u.parent.left.color == red) {
                u = removeFixupCase1(u);
            } else if (u == u.parent.left) {
                u = removeFixupCase2(u);
            } else { 
                u = removeFixupCase3(u);
            }
        }
        if (u != r) { // restore left-leaning property, if necessary
            Node<T> w = u.parent;
            if (w.right.color == red && w.left.color == black) {
                flipLeft(w);
            }
        }
    }

The $\mathtt{removeFixup(u)}$ method is illustrated in Figure 9.9. Again, the following text will be very difficult, if not impossible, to follow without referring constantly to Figure 9.9. Each iteration of the loop in $\mathtt{removeFixup(u)}$ processes the double-black node $\mathtt{u}$ based on one of four cases.

Figure 9.9: A single round in the process of eliminating a double-black node after a removal.

Case 0: $\mathtt{u}$ is the root. This is the easiest case to treat. We recolor $\mathtt{u}$ to be black and this does not violate any of the red-black tree properties.

Case 1: $\mathtt{u}$'s sibling, $\mathtt{v}$, is red. In this case, $\mathtt{u}$'s sibling is the left child of its parent, $\mathtt{w}$ (by the left-leaning property). We perform a right-flip at $\mathtt{w}$ and then proceed to the next iteration. Note that this causes $\mathtt{w}$'s parent to violate the left-leaning property and it causes the depth of $\mathtt{u}$ to increase. However, it also implies that the next iteration will be in Case 3 with $\mathtt{w}$ colored red. When examining Case 3, below, we will see that this means the process will stop during the next iteration.

    Node<T> removeFixupCase1(Node<T> u) {
        flipRight(u.parent);
        return u;
    }

Case 2: $\mathtt{u}$'s sibling, $\mathtt{v}$, is black and $\mathtt{u}$ is the left child of its parent, $\mathtt{w}$. In this case, we call $\mathtt{pullBlack(w)}$, making $\mathtt{u}$ black, $\mathtt{v}$ red, and darkening the color of $\mathtt{w}$ to black or double-black. At this point, $\mathtt{w}$ does not satisfy the left-leaning property, so we call $\mathtt{flipLeft(w)}$ to fix this.

At this point, $\mathtt{w}$ is red and $\mathtt{v}$ is the root of the subtree we started with. We need to check if $\mathtt{w}$ causes no-red-edge property to be violated. We do this by inspecting $\mathtt{w}$'s right child, $\mathtt{q}$. If $\mathtt{q}$ is black, then $\mathtt{w}$ satisfies the no-red-edge property and we can continue to the next iteration with $\ensuremath{\mathtt{u}}=\ensuremath{\mathtt{v}}$.

Otherwise ( $\mathtt{q}$ is red), both the no-red-edge property and the left-leaning property are violated at $\mathtt{q}$ and $\mathtt{w}$, respectively. A call to $\mathtt{rotateLeft(w)}$ restores the left-leaning property, but the no-red-edge property is still violated. At this point, $\mathtt{q}$ is the left child of $\mathtt{v}$ and $\mathtt{w}$ is the left child of $\mathtt{q}$, $\mathtt{q}$ and $\mathtt{w}$ are both red and $\mathtt{v}$ is black or double-black. A $\mathtt{flipRight(v)}$ makes $\mathtt{q}$ the parent of both $\mathtt{v}$ and $\mathtt{w}$. Following this up by a $\mathtt{pushBlack(q)}$ makes both $\mathtt{v}$ and $\mathtt{w}$ black and sets the color of $\mathtt{q}$ back to the original color of $\mathtt{w}$.

At this point, there is no more double-black node and the no-red-edge and black-height properties are reestablished. The only possible problem that remains is that the right child of $\mathtt{v}$ may be red, in which case the left-leaning property is violated. We check this and perform a $\mathtt{flipLeft(v)}$ to correct it if necessary.

    Node<T> removeFixupCase2(Node<T> u) {
        Node<T> w = u.parent;
        Node<T> v = w.right;
        pullBlack(w); // w.left
        flipLeft(w); // w is now red
        Node<T> q = w.right;
        if (q.color == red) { // q-w is red-red
            rotateLeft(w);
            flipRight(v);
            pushBlack(q);
            if (v.right.color == red)
                flipLeft(v);
            return q;
        } else {
            return v;
        }
    }

Case 3: $\mathtt{u}$'s sibling is black and $\mathtt{u}$ is the right child of its parent, $\mathtt{w}$. This case is symmetric to Case 2 and is handled mostly the same way. The only differences come from the fact that the left-leaning property is asymmetric, so it requires different handling.

As before, we begin with a call to $\mathtt{pullBlack(w)}$, which makes $\mathtt{v}$ red and $\mathtt{u}$ black. A call to $\mathtt{flipRight(w)}$ promotes $\mathtt{v}$ to the root of the subtree. At this point $\mathtt{w}$ is red, and the code branches two ways depending on the color of $\mathtt{w}$'s left child, $\mathtt{q}$.

If $\mathtt{q}$ is red, then the code finishes up exactly the same way that Case 2 finishes up, but is even simpler since there is no danger of $\mathtt{v}$ not satisfying the left-leaning property.

The more complicated case occurs when $\mathtt{q}$ is black. In this case, we examine the color of $\mathtt{v}$'s left child. If it is red, then $\mathtt{v}$ has two red children and its extra black can be pushed down with a call to $\mathtt{pushBlack(v)}$. At this point, $\mathtt{v}$ now has $\mathtt{w}$'s original color and we are done.

If $\mathtt{v}$'s left child is black then $\mathtt{v}$ violates the left-leaning property and we restore this with a call to $\mathtt{flipLeft(v)}$. The next iteration of $\mathtt{removeFixup(u)}$ then continues with $\ensuremath{\mathtt{u}}=\ensuremath{\mathtt{v}}$.

    Node<T> removeFixupCase3(Node<T> u) {
        Node<T> w = u.parent;
        Node<T> v = w.left;
        pullBlack(w);       
        flipRight(w);            // w is now red
        Node<T> q = w.left;
        if (q.color == red) {    // q-w is red-red
            rotateRight(w);
            flipLeft(v);
            pushBlack(q);
            return q;
        } else {
            if (v.left.color == red) {
                pushBlack(v);   // both v's children are red
                return v;
            } else {            // ensure left-leaning
                flipLeft(v);
                return w;
            }
        }                
    }

Each iteration of $\mathtt{removeFixup(u)}$ takes constant time. Cases 2 and 3 either finish or move $\mathtt{u}$ closer to the root of the tree. Case 0 (where $\mathtt{u}$ is the root) always terminates and Case 1 leads immediately to Case 3, which also terminates. Since the height of the tree is at most $2\log \ensuremath{\mathtt{n}}$, we conclude that there are at most $O(\log \ensuremath{\mathtt{n}})$ iterations of $\mathtt{removeFixup(u)}$ so $\mathtt{removeFixup(u)}$ runs in $O(\log \ensuremath{\mathtt{n}})$ time.