Red-Black Tree Operations

Addition

To implement add(x) in a RedBlackTree, we perform a standard BinarySearchTree insertion to add a new leaf, u, with u.x = x and set u.colour = 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 u is the right child of its parent), and it may violate the no-red-edge property (if u’s parent is red). To restore these properties, we call the method addFixup(u).

A single round in the process of fixing Property 2 after an insertion is illustrated in below figure:

The addFixup(u) method takes as input a node u whose color is red and which may violate the no-red-edge property and/or the left-leaning property. The following discussion is probably impossible to follow without referring to the above figure or recreating it on a piece of paper. Indeed, the reader may wish to study this figure before continuing.

If u is the root of the tree, then we can color u black to restore both properties. If u’s sibling is also red, then u’s parent must be black, so both the left-leaning and no-red-edge properties already hold.

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

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

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

The insertFixup(u) method takes constant time per iteration and each iteration either finishes or moves u closer to the root. Therefore, the insertFixup(u) method finishes after $O(\log n)$ iterations in $O(\log n)$ time.

Removal

The remove(x) operation in a RedBlackTree is the most complicated to implement, and this is true of all known red-black tree variants. Just like the remove(x) operation in a BinarySearchTree, this operation boils down to finding a node w with only one child, u, and splicing w out of the tree by having w.parent adopt u.

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

The removeFixup(u) method takes as its input a node u whose color is black (1) or double-black (2). If u is double-black, then removeFixup(u) performs a series of rotations and recoloring operations that move ...