Red–black tree

Red–black tree is a binary search tree (BST) that can re-balance to maintain the height of the tree that is efficient for all three operations. To maintain the acceptable height, the red-black tree re-structures itself by assigning colors to the nodes: red or black. There are rules how black and red nodes can be arranged in a tree:

1. a red node must have only black child nodes (if not, it's called red violation)
2. every path from any node to any of its descendant leaf must contain the same number of black nodes (if not, it's called black violation)

If the rules are violated, the tree structure knows that the balance needs to be recovered.

Example of a Red–black tree

Click `Next` to add a node to the tree and notice how the tree rebalances and how the colors are moving.

Example of a BST tree without rebalancing

Implementation

In this article, we examine an implementation in JavaScript. For simplicity, the implementation does not allow duplicate values to be inserted in the tree. Also, we implement only insertion and searching because the algorithm to delete a node is more complicated.

Data structure

Usually, red-black tree nodes consist of a key, the color, a left child, a right child and a reference to the parent node. In this implementation, we don't not use the reference to the parent node so that the structure is exactly like in standard BST + color:

function makeNode(value) {
  return {
    value,
    color: RED,
    links: [null, null], // [left, right]
  };
}

Searching O(log n)

Searching in a Red–black tree is done in the same way as in a normal BST. The complexity of this operation is O(log n)if the tree is balanced.

function find(root, value) {
  if (root === null) {
    return null;
  }

  if (value === root.value) {
    return root;
  }

  return find(root.links[dir(value, root.value)], value);
}

Let me explain the algorithm: the function gets a sub-tree root and a value we are searching for. If the root is null, it means that the value does not exist in this subtree. If the root's value equals the searched value, we simply return the root. And then we recurse to either the left subtree (root.links[0]) or the right subtree (root.links[1]). In this code, the dir function returns 0 if the searched value is less than the root's value and 1 otherwise.

// stands for direction to go, left (0) or right (1) subtree
function dir(target, value) {
  return target < value ? 0 : 1;
}

Insertion O(log n)

In addition to the normal BST insertion you have to re-balance the tree so that the rules of a Red–black tree are not violated. Every node that we insert is, by default, red. When we insert the first element, the root, we mark it as black explicitly.

function insert(value, root) {
  if (root == null) {
    return makeNode(value);
  }

  const d = dir(value, root.value); // left or right subtree
  const rd = 1 - d; // the opposite of d

  root.links[d] = insert(value, root.links[d]);

  if (!isRed(root.links[d])) {
    return root;
  }

  if (isRed(root.links[rd])) {
    // black violation
    root.color = RED;
    root.links[0].color = BLACK;
    root.links[1].color = BLACK;
    return root;
  }

  if (isRed(root.links[d].links[d])) {
    // red violation # 1
    return rotate(root, rd);
  }

  if (isRed(root.links[d].links[rd])) {
    // red violation # 2
    return doubleRotate(root, rd);
  }

  return root;
}

So after we inserted the new node, the recursion brings us up the call stack, and we can fix the violations for every node on the path of the insertion.

So how do we fix the violations? Consider, the following tree: the next node 5 is inserted as the right child of node 4. Since the color of 5 is red, we have a red violation. How do we fix it? We perform a left rotate at node 3 so that node 3 becomes the left child of node 4 and the new node 5 becomes the right child of the node 4. So the rotation of the tree helps to fix red violations.

Another type of red violation is the following tree. Here node 4 (red) will be added as the left child of node 5, and then we do a double left rotate (e.g., one right rotate at node 5 and one left rotate at node 3)

Here is the code for rotation functions:

function rotate(node, d) {
  const rd = 1 - d
  const save = node.links[rd]

  node.links[rd] = save.links[d]
  save.links[d] = node

  node.color = RED
  save.color = BLACK

  return save
}

function doubleRotate(node, d) {
  const rd = 1 - d

  node.links[rd] = rotate(node.links[rd], rd)

  return rotate(node, d)
}

Another kind of violation is a black violation. It happens when one sibling is red, and another one is black. In this case, we make the parent red and both children black and continue fixing the tree upstream.

Note that all cases are symmetric for left & right child nodes.

Finally, we can wrap the functions into a class so that we can create instances of a tree.

class RedBlackTree {
  constructor() {
    this.root = null
  }

  insert(value) {
    this.root = insert(value, this.root, true)
  }

  find(value) {
    return find(this.root, value)
  }

  getRoot() {
    return this.root
  }
}

The article is prepared based on Eternally Confuzzled's tutorial on red-black trees. Also, learn more about trees and other data structures from the following books:

1. Introduction to Algorithms, 3rd Edition (The MIT Press)
2. Cracking the Coding Interview: 189 Programming Questions and Solutions
3. Algorithms (4th Edition)