Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in C++

Red-Black Tree Operations

Explore the detailed implementation of red-black tree operations such as adding and removing nodes while preserving red-black properties. Understand balancing techniques with fixup methods to maintain efficient tree structure, enabling logarithmic time complexity for search, insertion, and deletion operations.

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 addFixup(u) method.

C++
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 figure below:

The addFixup(u) method takes as input a node u whose colour 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 Figure 9.8 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 colour 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 u already satisfies the no-red-edge property.

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.

C++
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 ...