Red-Black Tree

The red-black tree is a type of self-balancing binary search tree that assigns a colour of red or black to each node. On every insert or delete, the tree re-organises itself so that it is approximately logn\log nlogn nodes high, allowing search in O(logn)O(\log n)O(logn) time. The re-organising does not guarantee a perfectly balanced tree, it is however good enough to guarantee O(logn)O(\log n)O(logn) search.

Insert and delete are also performed in O(logn)O(\log n)O(logn) time. The ‘fixup’ operations where the balancing occurs after insert and delete have quite complex implementations as you will see below. This is because we need the properties of the red-black tree to hold otherwise it may not be balanced.

This article assumes knowledge of the binary search tree (BST) data structure.

Complexity #

Representation #

There are two main ways of representing a binary tree. The first is using node objects that have references to their children.

Tree representation

The second is using a regular array and manipulating the index of the node to find its children. The index of the left child of a node is 2i+12i + 12i+1 and the index of the right is 2i+22i + 22i+2 where iii is the index of the parent.

Array representation

The index of node's parent can also be retrieved with ⌊(i−1)/2⌋\lfloor(i - 1) / 2\rfloor⌊(i−1)/2⌋.

Properties #

Here are the set of rules that a red-black tree must follow:

• Each node is either red or black
• The root node is black
• All leaf nodes (nil) are black
• Both children of every red node are black
• For each node, all paths from the node to descendant leaves contain the same number of black nodes

Operations #

Rotation #

Performing a left rotate and a right rotate on nodes is an important operation used in both delete and insert operations. Here is an illustration of the process:

Delete(a) #

Delete performs a slightly modified binary search tree delete and then performs a fix-up function. Here are the cases that need to be fixed up if they occur.

1. The deleted node a’s sibling is red
2. The deleted node a’s sibling b is black and both of b’s children and black
3. The deleted node a’s sibling b is black, b’s left child is red and a’s right child is black
4. The deleted node a’s sibling b is black and b’s right child is red

Insert(a) #

Insert performs a slightly modified binary search tree insert and then performs a fix-up function. Here are the cases that need to be fixed up if they occur.

1. The inserted node a’s uncle is red
2. The inserted node a’s uncle is black and a is a right child
3. The inserted node a’s uncle is black and a is a left child

Search(n) #

For search we use the search operation on the regular binary search tree. Only now instead of having a worst case of O(n)O(n)O(n), it’s O(logn)O(\log n)O(logn) as we balance the tree.

Which binary search tree is best? #

The AVL tree, red-black tree and splay tree are all self-adjusting binary search trees, so which one is better in which situation? And when is it better to use a regular BST?

A paper by Ben Pfaff of Stanford University performs an in-depth study of the performance characteristics of each tree under various circumstances. Each data structure excels based on runtime patterns in the input and the calling of operations. It comes to the following conclusions:

• [Regular BSTs](/content/data-structures/binary-search-tree/overview/ excel when randomly ordered input can be relied upon.
• Splay trees excel when data is often inserted in a sorted order and later accesses are sequential or clustered.
• AVL trees excel when data is often inserted in a sorted order and later accesses are random.
• Red-black trees excel when data is often inserted in random order but occasional runs of sorted order are expected.

Code #

Java

public class RedBlackTree<T extends Comparable<T>> {
    private RedBlackTreeNode root;
    public RedBlackTree() { }
    public boolean insert(T key) {
        RedBlackTreeNode<T> parent = null;
        RedBlackTreeNode<T> node = root;
        while (node != null && !node.isNilNode()) {
            parent = node;
            int compare = key.compareTo(parent.getKey());
            if (compare == 0) {
                return false;
            }
            if (compare < 0) {
                node = parent.getLeft();
            } else {
                node = parent.getRight();
            }
        }
        if (parent == null) {
            node = new RedBlackTreeNode(key, null);
            root = node;
        } else {
            node.setParent(parent);
            node.setKey(key);
            node.setNilNode(false);
            node.setColor(RedBlackTreeNode.Color.RED);
        }
        node.setColor(RedBlackTreeNode.Color.RED);
        insertFixup(node);
        return true;
    }
    ...  // Other methods and class implementation follow
}

JavaScript

// file: red-black-tree.js
var BaseBinaryTree = require('./base-binary-tree');
var RedBlackTreeNode = require('./red-black-tree-node');
var RedBlackTree = function (customCompare) {
  BaseBinaryTree.call(this);
  this.root = undefined;
  this.nodeCount = 0;
  if (customCompare) {
    this.compare = customCompare;
  }
};
RedBlackTree.prototype = Object.create(BaseBinaryTree.prototype);
RedBlackTree.prototype.constructor = RedBlackTree;
RedBlackTree.prototype.add = function (key) {
  ... // Other methods and class implementation follow
};

References #

• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, “Red-Black Trees” in Introduction to Algorithms, 2nd ed., Cambridge, MA: The MIT Press, 2001, ch. 13, pp.273-296

Textbooks #

Here are two CS textbooks I personally recommend; the Algorithm Design Manual (Steven S. Skiena) is a fantastic introduction to data structures and algorithms without getting to deep into the maths side of things, and Introduction to Algorithms (CLRS) which provides a much deeper, math heavy look.