Red–black tree

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

1. a red node must have only black child nodes
2. every path from any node to any of its descendant leaf must contain the same number of black nodes

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

Example of a Red–black tree

Click `Insert` to add a node to the tree and notice how the tree rebalances and how the colors are changed.

Example of a normal BST tree

Implementation

In this article, we will examine an implementation in JavaScript. For simplicity, the implementation will not allow duplicate values.

Data structure

Normally, 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 will 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

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 recurise to either the left subtree (root.links[0]) or the right subtree (root.links[1]). In this codes, the dir function returns 0 if the searched value is less than the root's value and 1 otherwise.

function dir(target, value) {
  return target < value ? 0 : 1;
}

Insertion

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, node) {
  if (node == null) {
    return makeNode(value);
  }

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

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

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

  if (isRed(node.links[rd])) {
    node.color = RED;
    node.links[0].color = BLACK;
    node.links[1].color = BLACK;
    return node;
  }

  if (isRed(node.links[d].links[d])) {
    return rotate(node, rd);
  }

  if (isRed(node.links[d].links[rd])) {
    return doubleRotate(node, rd);
  }

  return node;
}

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

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 book Introduction to Algorithms, 3rd Edition (The MIT Press)