Red Black Trees

The Red Black Tree is one of the most popular implementation of sets and dictionaries.

Definition

A red-black tree is a binary search tree in which each node is colored red or black such that

Example:

redblacktree.png

Red black trees do not necessarily have minimum height, but they never get really bad. The height is never greater than $2 \log_2 n$, where $n$ is the number of nodes.

Uses

Red Black Trees are used to represent sets and dictionaries. In fact, they are used to implement the TreeSet and TreeMap classes in the Java Core API, as well as the Standard C++ sets and maps.

How They Work

Demos first! An online, interactive, animated applet that will teach you how they work, is here.

Lookup

A red black tree is a BST. Lookup in an RBT is just lookup in a BST. The colors don't matter.

Insertion

The algorithm has three steps:

  1. Insert as you would into a BST, coloring the node red.
  2. If the parent of the node you just inserted was red, you have a double-red problem which you must correct.
  3. Color the root node black.

A double red problem is corrected with zero or more recolorings followed by zero or one restructuring.

Recoloring

Recolor whenever the sibling of a red node's red parent is red:

rbtrecoloring.png

Restructuring

Restructure whenever the red child's red parent's sibling is black or null. There are four cases:

When you restructure, the root of the restructured subtree is colored black and its children are colored red.

rbrestructuring.png

An Example

Let's insert into an initially empty red-black tree, the following: 4 7 12 15 3 5 14 18 16 17. The tree takes shape like this:

  1. (4B)
  2. (4B (7R))
  3. (4B (7R (12R))) - whoops, need to rotate left
    ((4R) 7B (12R))
  4. ((4R) 7B (12R (15R))) - whoops, need to recolor
    ((4B) 7B (12B (15R)))
  5. (((3R) 4B) 7B (12B (15R)))
  6. (((3R) 4B (5R)) 7B (12B (15R)))
  7. (((3R) 4B (5R)) 7B (12B ((14R) 15R))) -- whoops, need RL rotation
    (((3R) 4B (5R)) 7B ((12R) 14B (15R))))
  8. (((3R) 4B (5R)) 7B ((12R) 14B (15R (18R))))) -- whoops, recolor
    (((3R) 4B (5R)) 7B ((12B) 14R (15B (18R)))))
  9. (((3R) 4B (5R)) 7B ((12B) 14R (15B ((16R) 18R))))) -- whoops, need RL rotation
    (((3R) 4B (5R)) 7B ((12B) 14R ((15R) 16B (18R))))
  10. (((3R) 4B (5R)) 7B ((12B) 14R ((15R) 16B ((17R) 18R)))) -- whoops, need to recolor
    (((3R) 4B (5R)) 7B ((12B) 14R ((15B) 16R ((17R) 18B))))
    -- whoa, the recolor caused a problem higher up in the tree!
    -- we need to do a left rotation
    ((((3R) 4B (5R)) 7R (12B)) 14B ((15B) 16R ((17R) 18B)))

Deletion

The algorithm is in the code below. Have fun figuring it out.

An Implementation

Since Red Black Trees are just a kind of binary search tree, it makes sense to subclass:

RedBlackTree.java
import java.awt.Color;
import java.util.Comparator;

/**
 * A simple red-black tree class.
 */
public class RedBlackTree extends BinarySearchTree {

    /**
     * Constructs an empty RedBlackTree that can only accept Comparables as items.
     */
    public RedBlackTree() {
        this(null);
    }

    /**
     * Constructs an empty RedBlackTree that orders its items according to the given
     * comparator.
     */
    public RedBlackTree(Comparator c) {
        super(c);
    }

    /**
     * The nodes in a red-black tree store a color together with the actual data in
     * the node.
     */
    class Node extends LinkedBinaryTreeNode {
        Color color = Color.black;

        public Node(Object data) {
            super(data);
        }
    }

    /**
     * Adds a single data item to the tree. If there is already an item in the tree
     * that compares equal to the item being inserted, it is "overwritten" by the
     * new item. Overrides BinarySearchTree.add because the tree needs to be
     * adjusted after insertion.
     */
    public void add(Object data) {
        if (root == null) {
            root = new Node(data);
        }
        BinaryTreeNode n = root;
        while (true) {
            int comparisonResult = compare(data, n.getData());
            if (comparisonResult == 0) {
                n.setData(data);
                return;
            } else if (comparisonResult < 0) {
                if (n.getLeft() == null) {
                    n.setLeft(new Node(data));
                    adjustAfterInsertion((Node) n.getLeft());
                    break;
                }
                n = n.getLeft();
            } else { // comparisonResult > 0
                if (n.getRight() == null) {
                    n.setRight(new Node(data));
                    adjustAfterInsertion((Node) n.getRight());
                    break;
                }
                n = n.getRight();
            }
        }
    }

    /**
     * Removes the node containing the given value. Does nothing if there is no such
     * node.
     */
    public void remove(Object data) {
        Node node = (Node) nodeContaining(data);
        if (node == null) {
            // No such object, do nothing.
            return;
        } else if (node.getLeft() != null && node.getRight() != null) {
            // Node has two children, Copy predecessor data in.
            BinaryTreeNode predecessor = predecessor(node);
            node.setData(predecessor.getData());
            node = (Node) predecessor;
        }
        // At this point node has zero or one child
        Node pullUp = leftOf(node) == null ? rightOf(node) : leftOf(node);
        if (pullUp != null) {
            // Splice out node, and adjust if pullUp is a double black.
            if (node == root) {
                setRoot(pullUp);
            } else if (node.getParent().getLeft() == node) {
                node.getParent().setLeft(pullUp);
            } else {
                node.getParent().setRight(pullUp);
            }
            if (isBlack(node)) {
                adjustAfterRemoval(pullUp);
            }
        } else if (node == root) {
            // Nothing to pull up when deleting a root means we emptied the tree
            setRoot(null);
        } else {
            // The node being deleted acts as a double black sentinel
            if (isBlack(node)) {
                adjustAfterRemoval(node);
            }
            node.removeFromParent();
        }
    }

    /**
     * Classic algorithm for fixing up a tree after inserting a node.
     */
    private void adjustAfterInsertion(Node n) {
        // Step 1: color the node red
        setColor(n, Color.red);

        // Step 2: Correct double red problems, if they exist
        if (n != null && n != root && isRed(parentOf(n))) {

            // Step 2a (simplest): Recolor, and move up to see if more work
            // needed
            if (isRed(siblingOf(parentOf(n)))) {
                setColor(parentOf(n), Color.black);
                setColor(siblingOf(parentOf(n)), Color.black);
                setColor(grandparentOf(n), Color.red);
                adjustAfterInsertion(grandparentOf(n));
            }

            // Step 2b: Restructure for a parent who is the left child of the
            // grandparent. This will require a single right rotation if n is
            // also
            // a left child, or a left-right rotation otherwise.
            else if (parentOf(n) == leftOf(grandparentOf(n))) {
                if (n == rightOf(parentOf(n))) {
                    rotateLeft(n = parentOf(n));
                }
                setColor(parentOf(n), Color.black);
                setColor(grandparentOf(n), Color.red);
                rotateRight(grandparentOf(n));
            }

            // Step 2c: Restructure for a parent who is the right child of the
            // grandparent. This will require a single left rotation if n is
            // also
            // a right child, or a right-left rotation otherwise.
            else if (parentOf(n) == rightOf(grandparentOf(n))) {
                if (n == leftOf(parentOf(n))) {
                    rotateRight(n = parentOf(n));
                }
                setColor(parentOf(n), Color.black);
                setColor(grandparentOf(n), Color.red);
                rotateLeft(grandparentOf(n));
            }
        }

        // Step 3: Color the root black
        setColor((Node) root, Color.black);
    }

    /**
     * Classic algorithm for fixing up a tree after removing a node; the parameter
     * to this method is the node that was pulled up to where the removed node was.
     */
    private void adjustAfterRemoval(Node n) {
        while (n != root && isBlack(n)) {
            if (n == leftOf(parentOf(n))) {
                // Pulled up node is a left child
                Node sibling = rightOf(parentOf(n));
                if (isRed(sibling)) {
                    setColor(sibling, Color.black);
                    setColor(parentOf(n), Color.red);
                    rotateLeft(parentOf(n));
                    sibling = rightOf(parentOf(n));
                }
                if (isBlack(leftOf(sibling)) && isBlack(rightOf(sibling))) {
                    setColor(sibling, Color.red);
                    n = parentOf(n);
                } else {
                    if (isBlack(rightOf(sibling))) {
                        setColor(leftOf(sibling), Color.black);
                        setColor(sibling, Color.red);
                        rotateRight(sibling);
                        sibling = rightOf(parentOf(n));
                    }
                    setColor(sibling, colorOf(parentOf(n)));
                    setColor(parentOf(n), Color.black);
                    setColor(rightOf(sibling), Color.black);
                    rotateLeft(parentOf(n));
                    n = (Node) root;
                }
            } else {
                // pulled up node is a right child
                Node sibling = leftOf(parentOf(n));
                if (isRed(sibling)) {
                    setColor(sibling, Color.black);
                    setColor(parentOf(n), Color.red);
                    rotateRight(parentOf(n));
                    sibling = leftOf(parentOf(n));
                }
                if (isBlack(leftOf(sibling)) && isBlack(rightOf(sibling))) {
                    setColor(sibling, Color.red);
                    n = parentOf(n);
                } else {
                    if (isBlack(leftOf(sibling))) {
                        setColor(rightOf(sibling), Color.black);
                        setColor(sibling, Color.red);
                        rotateLeft(sibling);
                        sibling = leftOf(parentOf(n));
                    }
                    setColor(sibling, colorOf(parentOf(n)));
                    setColor(parentOf(n), Color.black);
                    setColor(leftOf(sibling), Color.black);
                    rotateRight(parentOf(n));
                    n = (Node) root;
                }
            }
        }
        setColor(n, Color.black);
    }

    // The following helpers dramatically simplify the code by getting
    // all the null pointer checking out of the adjustment methods.

    private Color colorOf(Node n) {
        return n == null ? Color.black : n.color;
    }

    private boolean isRed(Node n) {
        return n != null && colorOf(n) == Color.red;
    }

    private boolean isBlack(Node n) {
        return n == null || colorOf(n) == Color.black;
    }

    private void setColor(Node n, Color c) {
        if (n != null)
            n.color = c;
    }

    private Node parentOf(Node n) {
        return n == null ? null : (Node) n.getParent();
    }

    private Node grandparentOf(Node n) {
        return (n == null || n.getParent() == null) ? null : (Node) n.getParent().getParent();
    }

    private Node siblingOf(Node n) {
        return (n == null || n.getParent() == null) ? null
                : (n == n.getParent().getLeft()) ? (Node) n.getParent().getRight() : (Node) n.getParent().getLeft();
    }

    private Node leftOf(Node n) {
        return n == null ? null : (Node) n.getLeft();
    }

    private Node rightOf(Node n) {
        return n == null ? null : (Node) n.getRight();
    }
}

Summary

We’ve covered:

  • What a red black tree is
  • Where they are used
  • An interactive viewer
  • The algorithms for lookup, insertion, and deletion
  • .