Data Structures with Generic Types in Java/

...

/

Red-Black Tree Operations

Red-Black Tree Operations

Learn to add and remove elements in red-black trees.

We'll cover the following...

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).

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

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.

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

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)O(\log n) iterations in O(log⁡n)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.

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.colour += w.colour;
  u.parent = w.parent;
  removeFixup(u);
  return true;
}

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 the double-black node up the ...