Red-black tree

Published 9 December 2012, updated 16 August 2015

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 \log n nodes high, allowing search in O(\log n) time. The re-organising does not guarantee a perfectly balanced tree, it is however good enough to guarantee O(\log n) search.

Insert and delete are also performed in O(\log n) 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

Operation	Description	Complexity
Delete	Deletes a node given a key	O(\log n)
Insert	Inserts a node with an associated key	O(\log n)
Search	Searches for and returns a node using its key	O(\log n)

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 + 1 and the index of the right is 2i + 2 where i is the index of the parent.

Array representation

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

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.

The deleted node a’s sibling is red
The deleted node a’s sibling b is black and both of b’s children and black
The deleted node a’s sibling b is black, b’s left child is red and a’s right child is black
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.

The inserted node a’s uncle is red
The inserted node a’s uncle is black and a is a right child
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), it’s O(\log n) 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 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

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;
    }

    private void insertFixup(RedBlackTreeNode<T> node) {
        while (node.getParent() != null &&
               node.getGrandparent() != null &&
               node.getParent().getColor() == RedBlackTreeNode.Color.RED) {

            if (node.getParent() == node.getGrandparent().getLeft()) {
                RedBlackTreeNode<T> uncle = node.getGrandparent().getRight();
                if (uncle.getColor() == RedBlackTreeNode.Color.RED) {
                    node.getParent().setColor(RedBlackTreeNode.Color.BLACK);
                    uncle.setColor(RedBlackTreeNode.Color.BLACK);
                    node = node.getGrandparent();
                    node.setColor(RedBlackTreeNode.Color.RED);
                } else {
                    if (node == node.getParent().getRight()) {
                        node = node.getParent();
                        rotateLeft(node);
                    }
                    node.getParent().setColor(RedBlackTreeNode.Color.BLACK);
                    node.getGrandparent().setColor(RedBlackTreeNode.Color.RED);
                    rotateRight(node.getGrandparent());
                }
            } else if (node.getParent() == node.getGrandparent().getRight()) {
                RedBlackTreeNode<T> uncle = node.getGrandparent().getLeft();
                if (uncle.getColor() == RedBlackTreeNode.Color.RED) {
                    node.getParent().setColor(RedBlackTreeNode.Color.BLACK);
                    uncle.setColor(RedBlackTreeNode.Color.BLACK);
                    node = node.getGrandparent();
                    node.setColor(RedBlackTreeNode.Color.RED);
                } else {
                    if (node == node.getParent().getLeft()) {
                        node = node.getParent();
                        rotateRight(node);
                    }
                    node.getParent().setColor(RedBlackTreeNode.Color.BLACK);
                    node.getGrandparent().setColor(RedBlackTreeNode.Color.RED);
                    rotateLeft(node.getGrandparent());
                }
            }
        }
        root.setColor(RedBlackTreeNode.Color.BLACK);
    }

    private void rotateLeft(RedBlackTreeNode<T> x) {
        RedBlackTreeNode<T> y = x.getRight();
        x.setRight(y.getLeft());
        if (y.getLeft() != null) {
            y.getLeft().setParent(x);
        }
        y.setParent(x.getParent());
        if (x.getParent() == null) {
            root = y;
        } else {
            if (x == x.getParent().getLeft())
                x.getParent().setLeft(y);
            else
                x.getParent().setRight(y);
        }
        y.setLeft(x);
        x.setParent(y);
    }

    private void rotateRight(RedBlackTreeNode<T> x) {
        RedBlackTreeNode<T> y = x.getLeft();
        x.setLeft(y.getRight());
        if (y.getRight() != null) {
            y.getRight().setParent(x);
        }
        y.setParent(x.getParent());
        if (x.getParent() == null)
            root = y;
        else {
            if (x == x.getParent().getLeft()) {
                x.getParent().setLeft(y);
            } else {
                x.getParent().setRight(y);
            }
        }
        y.setRight(x);
        x.setParent(y);
    }

    public void delete(T key) {
        RedBlackTreeNode<T> node = search(key);
        RedBlackTreeNode<T> y, x;
        if (node.getLeft().isNilNode() || node.getRight().isNilNode()) {
            y = node;
        } else {
            y = treeSuccessor(node);
        }
        if (y.getLeft() != null && !y.getLeft().isNilNode()) {
            x = y.getLeft();
        } else {
            x = y.getRight();
        }
        x.setParent(y.getParent());
        if (y.getParent() == null) {
            root = x;
        } else {
            if (y == y.getParent().getLeft())
                y.getParent().setLeft(x);
            else
                y.getParent().setRight(x);
        }
        if (y != node) {
            node.setKey(y.getKey());
        }
        if (y.getColor() == RedBlackTreeNode.Color.BLACK) {
            deleteFixup(x);
        }
    }

    private void deleteFixup(RedBlackTreeNode<T> node) {
        while (node != root && node.getColor() == RedBlackTreeNode.Color.BLACK) {
            if (node == node.getParent().getLeft()) {
                RedBlackTreeNode w = node.getParent().getRight();
                if (w.getColor() == RedBlackTreeNode.Color.RED) {
                    w.setColor(RedBlackTreeNode.Color.BLACK);
                    node.getParent().setColor(RedBlackTreeNode.Color.RED);
                    rotateLeft(node.getParent());
                }
                if (w.getLeft().getColor() == RedBlackTreeNode.Color.BLACK &&
                    w.getRight().getColor() == RedBlackTreeNode.Color.BLACK) {

                    w.setColor(RedBlackTreeNode.Color.RED);
                    node = node.getParent();
                } else  {
                    if (w.getRight().getColor() == RedBlackTreeNode.Color.BLACK) {
                        w.getLeft().setColor(RedBlackTreeNode.Color.BLACK);
                        w.setColor(RedBlackTreeNode.Color.RED);
                        rotateRight(w);
                        w = node.getParent().getRight();
                    }
                    w.setColor(node.getParent().getColor());
                    node.getParent().setColor(RedBlackTreeNode.Color.BLACK);
                    w.getRight().setColor(RedBlackTreeNode.Color.BLACK);
                    rotateLeft(node.getParent());
                    node = root;
                }
            } else {
                RedBlackTreeNode w = node.getParent().getLeft();
                if (w.getColor() == RedBlackTreeNode.Color.RED) {
                    w.setColor(RedBlackTreeNode.Color.BLACK);
                    node.getParent().setColor(RedBlackTreeNode.Color.RED);
                    rotateRight(node.getParent());
                }
                if (w.getRight().getColor() == RedBlackTreeNode.Color.BLACK &&
                    w.getLeft().getColor() == RedBlackTreeNode.Color.BLACK) {

                    w.setColor(RedBlackTreeNode.Color.RED);
                    node = node.getParent();
                } else  {
                    if (w.getLeft().getColor() == RedBlackTreeNode.Color.BLACK) {
                        w.getRight().setColor(RedBlackTreeNode.Color.BLACK);
                        w.setColor(RedBlackTreeNode.Color.RED);
                        rotateLeft(w);
                        w = node.getParent().getLeft();
                    }
                    w.setColor(node.getParent().getColor());
                    node.getParent().setColor(RedBlackTreeNode.Color.BLACK);
                    w.getLeft().setColor(RedBlackTreeNode.Color.BLACK);
                    rotateRight(node.getParent());
                    node = root;
                }
            }
        }
        node.setColor(RedBlackTreeNode.Color.BLACK);
    }

    private RedBlackTreeNode<T> treeSuccessor(RedBlackTreeNode<T> node) {
        if (node.getRight() != null && !node.isNilNode()) {
            return treeMinimum(node.getRight());
        }
        RedBlackTreeNode<T> successor = node.getParent();
        while (successor != null && !successor.isNilNode() &&
                node == successor) {
            node = successor;
            successor = node.getParent();
        }
        return successor;
    }

    private RedBlackTreeNode<T> treeMinimum(RedBlackTreeNode<T> node) {
        while (!node.getLeft().isNilNode() && !node.isNilNode()) {
            node = node.getLeft();
        }
        return node;
    }

    public RedBlackTreeNode<T> search(T key) {
        if (root == null) {
            return null;
        }

        return search(key, root);
      }

    public RedBlackTreeNode<T> search( T key, RedBlackTreeNode<T> node) {
        if (key == node.getKey()) {
            return node;
        }

        if (key.compareTo( node.getKey() ) < 0) {
            if (!node.leftExists()) {
                return null;
            }
            return search(key, node.getLeft());
        }

        if (key.compareTo( node.getKey() ) >= 0) {
            if (!node.rightExists()) {
                return null;
            }
            return search(key, node.getRight());
        }

        return null;
    }

    public String toString() {
        if (root == null) {
            return "(empty)";
        }
        return root.toString();
    }

}



public class RedBlackTreeNode<T extends Comparable<T>> implements Comparable<RedBlackTreeNode<T>> {

    private final String nullNodeString = "_B";
    private RedBlackTreeNode left;
    private RedBlackTreeNode right;
    private RedBlackTreeNode parent;

    private T key;
    private boolean isNilNode;
    private Color color;

    /**
     * Creates a new {@link RedBlackTreeNode}.
     *
     * @param key The key of the new node.
     * @param parent The parent of the new node.
     */
    public RedBlackTreeNode(T key, RedBlackTreeNode parent) {
        this.key = key;
        this.parent = parent;
        this.color = Color.RED;
        this.setNilNode(false);
    }

    /**
     * Creates a new nil (black) {@link RedBlackTreeNode}.
     *
     * @param parent The parent of the new node.
     */
    private RedBlackTreeNode(RedBlackTreeNode parent) {
        this.parent = parent;
        this.color = Color.BLACK;
        this.setNilNode(true);
    }

    /**
     * @return A string that textually describes the node.
     */
    @Override
    public String toString() {
        if (isNilNode) {
            return nullNodeString;
        }
        return key + getColorCode() + " : { " +
                (leftExists() ? left.toString() : nullNodeString) + " , " +
                (rightExists() ? right.toString() : nullNodeString) + " }";
    }

    /**
     * @return The color code for the node, either red or black.
     */
    private String getColorCode() {
        if (color == Color.BLACK) {
            return "B";
        }
        return "R";
    }

    /**
     * @return Whether the node has a left child.
     */
    public boolean leftExists() {
        return left != null;
    }

    /**
     * @return Whether the node has a right child.
     */
    public boolean rightExists() {
        return right != null;
    }

    /**
     * @return The node's key.
     */
    public T getKey() {
        return key;
    }

    /**
     * Sets the node's key.
     *
     * @param key The new key.
     */
    public void setKey(T key) {
        this.key = key;
    }

    /**
     * @return The left child node.
     */
    public RedBlackTreeNode getLeft() {
        // Create nil leaf nodes lazily
        if (left == null) {
            left = new RedBlackTreeNode(this);
        }
        return left;
    }

    /**
     * Sets the left child node.
     *
     * @param left The new left child node.
     */
    public void setLeft(RedBlackTreeNode left) {
        this.left = left;
    }

    /**
     * @return The right child node.
     */
    public RedBlackTreeNode getRight() {
        // Create nil leaf nodes lazily
        if (right == null) {
            right = new RedBlackTreeNode(this);
        }
        return right;
    }

    /**
     * Sets the right child node.
     *
     * @param right The new right child node.
     */
    public void setRight(RedBlackTreeNode right) {
        this.right = right;
    }

    /**
     * @return The parent of this node.
     */
    public RedBlackTreeNode getParent() {
        return parent;
    }

    /**
     * @return The grandparent of the node if it exists, otherwise null.
     */
    public RedBlackTreeNode getGrandparent() {
        if (parent != null && parent.getParent() != null) {
            return parent.getParent();
        }
        return null;
    }

    /**
     * Sets the parent of this node.
     *
     * @param right The new parent node.
     */
    public void setParent(RedBlackTreeNode parent) {
        this.parent = parent;
    }

    /**
     * @return The color of this node.
     */
    public Color getColor() {
        return color;
    }

    /**
     * Sets the color of this node.
     *
     * @param color The new color node.
     */
    public void setColor(Color color) {
        this.color = color;
    }

    /**
     * @return Whether this is a nil node.
     */
    public boolean isNilNode() {
        return isNilNode;
    }

    /**
     * Sets weather this is a nil node.
     *
     * @param isNilNode Whether it is a nil node.
     */
    public final void setNilNode(boolean isNilNode) {
        this.isNilNode = isNilNode;
    }

    /** {@inheritDoc} */
    @Override
    public int compareTo(RedBlackTreeNode<T> o) {
        return this.key.compareTo(o.getKey());
    }

    /**
     * Represents the color of a Red Black Tree node.
     */
    public enum Color {
        BLACK,
        RED
    }
}

// file: red-black-tree.js

var BaseBinaryTree = require('./base-binary-tree');
var RedBlackTreeNode = require('./red-black-tree-node');

/**
 * Creates a red-black tree.
 *
 * @constructor
 * @param {function} customCompare An optional custom node comparison
 * function.
 */
var RedBlackTree = function (customCompare) {
  BaseBinaryTree.call(this);

  this.root = undefined;

  /**
   * The number of nodes in the tree.
   * @private
   */
  this.nodeCount = 0;

  if (customCompare) {
    this.compare = customCompare;
  }
};

RedBlackTree.prototype = Object.create(BaseBinaryTree.prototype);

RedBlackTree.prototype.constructor = RedBlackTree;

/**
 * Adds a key to the {@link BinarySearchTree}.
 *
 * @param {Object} key The key to add.
 * @return {boolean} Whether the node was added.
 */
RedBlackTree.prototype.add = function (key) {
  var parent;
  var node = this.root;
  while (node && !node.isNilNode()) {
    parent = node;
    var compare = this.compare(key, parent.key);
    if (compare === 0) {
      return false;
    }
    if (compare < 0) {
      node = parent.getLeft();
    } else {
      node = parent.getRight();
    }
  }
  if (!parent) {
    node = new RedBlackTreeNode(key);
    this.root = node;
  } else {
    node.parent = parent;
    node.key = key;
  }
  node.color = 'red';
  this.insertFixup(node);
  this.nodeCount++;
  return true;
};

/**
 * Ensure all of the tree's properties are maintained after an insertion.
 *
 * @param {Object} node The node that was inserted.
 */
RedBlackTree.prototype.insertFixup = function (node) {
  while (node.parent && node.parent.parent && node.parent.color === 'red') {
    var uncle;
    if (node.parent === node.parent.parent.getLeft()) {
      uncle = node.parent.parent.getRight();
      if (uncle.color === 'red') {
        node.parent.color = 'black';
        uncle.color = 'black';
        node = node.parent.parent;
        node.color = 'red';
      } else {
        if (node === node.parent.getRight()) {
          node = node.parent;
          this.rotateLeft(node);
        }
        node.parent.color = 'black';
        node.parent.parent.color = 'red';
        this.rotateRight(node.parent.parent);
      }
    } else if (node.parent === node.parent.parent.getRight()) {
      uncle = node.parent.parent.getLeft();
      if (uncle.color === 'red') {
        node.parent.parent.color = 'black';
        uncle.color = 'black';
        node = node.parent.parent;
        node.color = 'red';
      } else {
        if (node === node.parent.getLeft()) {
          node = node.parent;
          this.rotateRight(node);
        }
        node.parent.color = 'black';
        node.parent.parent.color = 'red';
        this.rotateLeft(node.parent.parent);
      }
    }
  }
  this.root.color = 'black';
};

/**
 * Determines whether the tree contains a key.
 *
 * @param {Object} key The key to check.
 * @return {boolean} Whether the node contains the key.
 */
RedBlackTree.prototype.contains = function (key) {
  return !!this.search(key);
};

/**
 * Finds the element matching a key.
 *
 * @param {Object} key The key to check.
 * @return {RedBlackTreeNode} The matching node.
 */
RedBlackTree.prototype.search = function (key) {
  if (!this.root) {
    return undefined;
  }

  var current = this.root;
  while (true) {
    if (this.compare(key, current.key) < 0) {
      if (typeof current.getLeft().key === 'undefined') {
        return undefined;
      }
      current = current.getLeft();
    } else if (this.compare(key, current.key) > 0) {
      if (typeof current.getRight().key === 'undefined') {
        return undefined;
      }
      current = current.getRight();
    } else {
      return current;
    }
  }
};

/**
 * Removes a key from the tree.
 *
 * @param {Object} key The key to remove.
 * @return {boolean} Whether the key was removed.
 */
RedBlackTree.prototype.remove = function (key) {
  var node = this.search(key);
  if (!node) {
    return false;
  }
  this.nodeCount--;
  var y;
  var x;
  if (node.getLeft().isNilNode() || node.getRight().isNilNode()) {
    y = node;
  } else {
    y = this.treeSuccessor(node);
  }
  if (!y.getLeft().isNilNode()) {
    x = y.getLeft();
  } else {
    x = y.getRight();
  }
  x.parent = y.parent;
  if (!y.parent) {
    this.root = x;
  } else {
    if (y === y.parent.getLeft()) {
      y.parent.left = x;
    } else {
      y.parent.right = x;
    }
  }
  if (y !== node) {
    node.key = y.key;
  }
  if (y.color === 'black') {
    this.deleteFixup(x);
  }
  return true;
};

/**
 * Ensure all of the tree's properties are maintained after a removal.
 *
 * @param {Object} node The removed node's successor.
 */
RedBlackTree.prototype.deleteFixup = function (node) {
  while (node !== this.root && node.color === 'black') {
    var w;
    if (node === node.parent.getLeft()) {
      w = node.parent.getRight();
      if (w.color === 'red') {
        w.color = 'black';
        node.parent.color = 'red';
        this.rotateLeft(node.parent);
      }
      if (w.getLeft().color === 'black' && w.getRight().color === 'black') {

        w.color = 'red';
        node = node.parent;
      } else {
        if (w.getRight().color === 'black') {
          w.getLeft().color = 'black';
          w.color = 'red';
          this.rotateRight(w);
          w = node.parent.getRight();
        }
        w.color = node.parent.color;
        node.parent.color = 'black';
        w.getRight().color = 'black';
        this.rotateLeft(node.parent);
        node = this.root;
      }
    } else {
      w = node.parent.getLeft();
      if (w.color === 'red') {
        w.color = 'black';
        node.parent.color = 'red';
        this.rotateRight(node.parent);
      }
      if (w.getRight().color === 'black' && w.getLeft().color === 'black') {
        w.color = 'red';
        node = node.parent;
      } else {
        if (w.getLeft().color === 'black') {
          w.getRight().color = 'black';
          w.color = 'red';
          this.rotateLeft(w);
          w = node.parent.getLeft();
        }
        w.color = node.parent.color;
        node.parent.color = 'black';
        w.getLeft().color = 'black';
        this.rotateRight(node.parent);
        node = this.root;
      }
    }
  }
  node.color = 'black';
};

RedBlackTree.prototype.treeSuccessor = function (node) {
  if (node.getRight() && !node.isNilNode()) {
    return this.treeMinimum(node.getRight());
  }
  var successor = node.parent;
  while (successor && !successor.isNilNode() && node === successor) {
    node = successor;
    successor = node.parent;
  }
  return successor;
};

/**
 * @return {Object} Gets the minimum node in a sub-tree.
 */
RedBlackTree.prototype.treeMinimum = function (node) {
  while (!node.isNilNode() && !node.getLeft().isNilNode()) {
    node = node.getLeft();
  }
  return node;
};

/**
 * Rotates a node in a tree left.
 *
 *     a                             b
 *    / \                           / \
 *   c   b   -> rotateLeft(a) ->   a   e
 *      / \                       / \
 *     d   e                     c   d
 *
 * @param {BinaryTreeNode} x The node being rotated.
 */
RedBlackTree.prototype.rotateLeft = function (x) {
  var y = x.getRight();
  x.right = y.getLeft();
  if (typeof y.getLeft().key !== 'undefined') {
    y.getLeft().parent = x;
  }
  y.parent = x.parent;
  if (!x.parent) {
    this.root = y;
  } else {
    if (x === x.parent.getLeft()) {
      x.parent.left = y;
    } else {
      x.parent.right = y;
    }
  }
  y.left = x;
  x.parent = y;
};

/**
 * Rotates a node in a tree right.
 *
 *       b                          a
 *      / \                        / \
 *     a   e -> rotateRight(b) -> c   b
 *    / \                            / \
 *   c   d                          d   e
 *
 * @param {BinaryTreeNode} x The node being rotated.
 */
RedBlackTree.prototype.rotateRight = function (x) {
  var y = x.getLeft();
  x.left = y.getRight();
  if (typeof y.getRight().key !== 'undefined') {
    y.getRight().parent = x;
  }
  y.parent = x.parent;
  if (!x.parent) {
    this.root = y;
  } else {
    if (x === x.parent.getLeft()) {
      x.parent.left = y;
    } else {
      x.parent.right = y;
    }
  }
  y.right = x;
  x.parent = y;
};

/**
 * @return {Object} The maximum key of the tree.
 */
RedBlackTree.prototype.findMaximum = function () {
  if (!this.root) {
    return undefined;
  }

  var current = this.root;
  while (true) {
    if (typeof current.getRight().key !== 'undefined') {
      current = current.getRight();
    } else {
      return current.key;
    }
  }
};

/**
 * @return {Object} The minimum key of the tree.
 */
RedBlackTree.prototype.findMinimum = function () {
  if (!this.root) {
    return undefined;
  }

  var current = this.root;
  while (true) {
    if (typeof current.getLeft().key !== 'undefined') {
      current = current.getLeft();
    } else {
      return current.key;
    }
  }
};

/**
 * @return {boolean} Whether the tree is empty.
 */
RedBlackTree.prototype.isEmpty = function () {
  return !this.nodeCount;
};

/**
 * @return The size of the tree.
 */
RedBlackTree.prototype.size = function () {
  return this.nodeCount;
};

/**
 * Compares two nodes with each other.
 *
 * @param {Object} a The first key to compare.
 * @param {Object} b The second key to compare.
 * @return -1, 0 or 1 if a < b, a == b or a > b respectively.
 */
RedBlackTree.prototype.compare = function (a, b) {
  if (a > b) {
    return 1;
  }
  if (a < b) {
    return -1;
  }
  return 0;
};

module.exports = RedBlackTree;



// file: base-binary-tree.js

/**
 * Creates a base binary tree.
 * @constructor
 */
var BaseBinaryTree = function () {
  /**
   * The root of the tree.
   * @protected
   */
  this.root = undefined;
};

/**
 * Performs a pre-order traversal, calling a function on each node.
 *
 * @param {function} visit A function that takes a node's key.
 */
BaseBinaryTree.prototype.traversePreOrder = function (visit) {
  if (!this.root) {
    return;
  }

  var parentStack = [];
  parentStack.push(this.root);
  do {
    var top = parentStack.pop();
    visit(top.key);
    if (top.right) {
      parentStack.push(top.right);
    }
    if (top.left) {
      parentStack.push(top.left);
    }
  } while (parentStack.length);
};

/**
 * Performs a in-order traversal, calling a function on each node.
 *
 * @param {function} visit A function that takes a node's key.
 */
BaseBinaryTree.prototype.traverseInOrder = function (visit) {
  var parentStack = [];
  var node = this.root;
  while (parentStack.length || node) {
    if (node) {
      parentStack.push(node);
      node = node.left;
    } else {
      node = parentStack.pop();
      visit(node.key);
      node = node.right;
    }
  }
};

/**
 * Performs a post-order traversal, calling a function on each node.
 *
 * @param {function} visit A function that takes a node's key.
 */
BaseBinaryTree.prototype.traversePostOrder = function (visit) {
  var parentStack = [];
  var node = this.root;
  var lastVisitedNode;
  while (parentStack.length || node) {
    if (node) {
      parentStack.push(node);
      node = node.left;
    } else {
      var nextNode = parentStack[parentStack.length - 1];
      if (nextNode.right && lastVisitedNode !== nextNode.right) {
        // if right child exists AND traversing node from left child, move
        // right
        node = nextNode.right;
      } else {
        parentStack.pop();
        visit(nextNode.key);
        lastVisitedNode = nextNode;
      }
    }
  }
};

module.exports = BaseBinaryTree;



// file: red-black-tree-node.js

var BinaryTreeNode = require('./binary-tree-node');

/**
 * Creates a red-black tree node.
 *
 * @constructor
 * @param {Object} key The key of the node. If this is undefined the node will
 * be marked as a nil (black) node.
 * @param {RedBlackTreeNode} parent The parent of the node.
 */
var RedBlackTreeNode = function (key, parent) {
  BinaryTreeNode.call(this, key, parent);

  /**
   * The color of the node.
   * @public
   */
  this.color = typeof key === 'undefined' ? 'black' : 'red';
};

RedBlackTreeNode.prototype = Object.create(BinaryTreeNode.prototype);

RedBlackTreeNode.prototype.constructor = RedBlackTreeNode;

/**
 * Gets the left child of the node, creating it as a nil (black) node if it
 * didn't exist.
 *
 * @return {RedBlackTreeNode} The left child of the node.
 */
RedBlackTreeNode.prototype.getLeft = function () {
  if (!this.left) {
    this.left = new RedBlackTreeNode(undefined, this);
  }
  return this.left;
};

/**
 * Gets the right child of the node, creating it as a nil (black) node if it
 * didn't exist.
 *
 * @return {RedBlackTreeNode} The right child of the node.
 */
RedBlackTreeNode.prototype.getRight = function () {
  if (!this.right) {
    this.right = new RedBlackTreeNode(undefined, this);
  }
  return this.right;
};

/**
 * @return Whether the node is a nil (black) node.
 */
RedBlackTreeNode.prototype.isNilNode = function () {
  return typeof this.key === 'undefined';
};

module.exports = RedBlackTreeNode;



// file: binary-tree-node.js

/**
 * Creates a binary tree node.
 *
 * @constructor
 * @param {Object} key The key of the node.
 * @param {BinaryTreeNode} parent The parent of the node.
 */
function BinaryTreeNode(key, parent) {
  /**
   * The key of the node.
   * @public
   */
  this.key = key;

  /**
   * The parent of the node.
   * @public
   */
  this.parent = parent;

  /**
   * The left child of the node.
   * @public
   */
  this.left = undefined;

  /**
   * The right child of the node.
   * @public
   */
  this.right = undefined;
}

/**
 * Removes a child from the node. This will remove the left or right node
 * depending on which one matches the argument.
 *
 * @param {Object} node The node to remove.
 */
BinaryTreeNode.prototype.removeChild = function (node) {
  if (this.left === node) {
    this.left = undefined;
  }
  if (this.right === node) {
    this.right = undefined;
  }
};

module.exports = BinaryTreeNode;

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.