redblack.js

  function RedBlackNode(data) {
    this.data = data;
    this.left = null;
    this.right = null;
    this.parent = null;
    this.red = false;
  }
  RedBlackNode.prototype = {
    next: function () {
      var n = this;
      if (n.right) {
        n = n.right;
        while (n.left) {
          n = n.left;
        }
        return n;
      }
      var p = n.parent;
      while (p && (p.right === n || !p.right)) {
        n = p;
        p = p.parent;
      }
      return p;
    },
    prev: function () {
      var n = this;
      if (n.left) {
        n = n.left;
        while (n.right) {
          n = n.right;
        }
        return n;
      }
      var p = n.parent;
      while (p && (p.left === n || !p.left)) {
        n = p;
        p = p.parent;
      }
      return p;
    }
  };


  function defaultComparer(a, b) {
    return a < b ? -1 : a > b ? 1 : 0;
  }

  function RedBlackTree() {
    this.root = null;
    this.comparer = defaultComparer;
    this.length = 0;
  }

  RedBlackTree.prototype = {
    clear: function () {
      this.root = null;
      this.length = 0;
    },
    insert: function (value) {
      this.root = insertNode(this.root, new RedBlackNode(value), this.comparer);
      this.length++;
    },
    has: function (value) {
      return !!find(this.root, value, this.comparer);
    },
    remove: function (value) {
      var node = findNode(this.root, value, this.comparer);
      if (!node) {
        return;
      }
      this.root = deleteNode(this.root, node, this.comparer);
      this.length--;
    },
    min: function () {
      if (!this.root) {
        return null;
      }
      var p = this.root;
      while (p.left) {
        p = p.left;
      }
      return p;
    },
    max: function () {
      if (!this.root) {
        return null;
      }
      var p = this.root;
      while (p.right) {
        p = p.right;
      }
      return p;
    },
    forEach: function (fn, thisArg) {
      for (var p = this.min(); p; p = p.next()) {
        fn.call(thisArg, p.data, p);
      }
    },
    filter: function (fn, thisArg) {
      var node = this.root;
      var cmp;
      while (node && (cmp = fn.call(thisArg, node.data)) !== 0) {
        node = cmp < 0 ? node.left : node.right;
      }
      if (!node) {
        return [];
      }
      var result = [node.data], p;
      for (p = node.prev(); p && fn.call(thisArg, p) === 0; p = p.prev()) {
        result.unshift(p.data);
      }
      for (p = node.next(); p && fn.call(thisArg, p) === 0; p = p.next()) {
        result.push(p.data);
      }
      return result;
    },
    verify: function () {
      if (this.root) {
        verify(this.root);
      }
    }
  };


  // http://en.literateprograms.org/Red-black_tree_%28C%29

  function verify(root) {
    if (root.red) {
      throw new Error('The root node must be black.');
    }
    var queue = [{node: root, blackCount: 1}];
    var globalBlackCount = -1;
    while (queue.length > 0) {
      var nodeInfo = queue.shift();
      var node = nodeInfo.node, blackCount = nodeInfo.blackCount;
      if (node.red &&
          ((node.left && node.left.red) || (node.right && node.right.red))) {
        throw new Error('A red node has two children, and one is red.');
      }
      if (!node.red) {
        blackCount++;
      }
      if (node.left) {
        if (node.left.parent !== node) {
          throw new Error('Invalid parent node.');
        }
        queue.push({node: node.left, blackCount: blackCount});
      }
      if (node.right) {
        if (node.right.parent !== node) {
          throw new Error('Invalid parent node.');
        }
        queue.push({node: node.right, blackCount: blackCount});
      }
      if (!node.left || !node.right) {
        if (globalBlackCount < 0) { // first time?
          globalBlackCount = blackCount;
        } else if (blackCount !== globalBlackCount) {
          throw new Error('Paths from a node to its leaf nodes do not contain' +
                          ' the same number of black nodes');
        }
      }
    }
  }

  function rotateLeft(root, node) {
    var parent = node.parent;
    var right = node.right;
    node.right = right.left;
    if (node.right) {
      node.right.parent = node;
    }
    right.left = node;
    node.parent = right;

    right.parent = parent;
    if (!parent) {
      return right; // new root
    }
    if (parent.left === node) {
      parent.left = right;
    } else {
      parent.right = right;
    }
    return root;
  }

  function rotateRight(root, node) {
    var parent = node.parent;
    var left = node.left;
    node.left = left.right;
    if (node.left) {
      node.left.parent = node;
    }
    left.right = node;
    node.parent = left;

    left.parent = parent;
    if (!parent) {
      return left; // new root
    }
    if (parent.left === node) {
      parent.left = left;
    } else {
      parent.right = left;
    }
    return root;
  }

  function insertNode(root, node, comparer) {
    if (!root) {
      // The current node is at the root of the tree.
      return node;
    }

    node.red = true;
    var parent = root;
    while (true) {
      if (comparer(node.data, parent.data) < 0) {
        if (parent.left) {
          parent = parent.left;
        } else {
          parent.left = node;
          node.parent = parent;
          break;
        }
      } else {
        if (parent.right) {
          parent = parent.right;
        } else {
          parent.right = node;
          node.parent = parent;
          break;
        }
      }
    }

    var grandpa = parent.parent;
    while (true) {
      // insert case 2
      if (!parent.red) {
        // The current node's parent is black -- tree is still valid.
        return root;
      }

      // insert case 3
      var uncle = grandpa &&
        (grandpa.left === parent ? grandpa.right : grandpa.left);
      if (!uncle || !uncle.red) {
        break;
      }

      // The parent and the uncle are red.
      parent.red = false;
      uncle.red = false;
      // insert case 1
      if (!grandpa.parent) {
        grandpa.red = false;
        return root;
      }
      grandpa.red = true;
      node = grandpa;
      parent = grandpa.parent;
      grandpa = parent.parent;
    }

    // insert case 4
    // The parent is red but the uncle is black.
    if ((node === parent.right) && (parent === grandpa.left)) {
      root = rotateLeft(root, parent);
      node = parent;
    } else if ((node === parent.left) && (parent === grandpa.right)) {
      root = rotateRight(root, parent);
      node = parent;
    }
    parent = node.parent;
    parent.red = false;
    grandpa = parent.parent;
    grandpa.red = true;
    if (node === parent.left) {
      root = rotateRight(root, grandpa);
    } else {
      root = rotateLeft(root, grandpa);
    }
    return root;
  }

  function findNode(root, data, comparer) {
    var node = root;
    var cmp;
    while (node && (cmp = comparer(data, node.data)) !== 0) {
      node = cmp < 0 ? node.left : node.right;
    }
    return node;
  }

  function deleteCase1(root, node) {
    if (!node.parent) {
      return root;
    }
    return deleteCase2(root, node);
  }

  function deleteCase2(root, node) {
    var parent = node.parent;
    var sibling = !parent ? null :
      parent.left === node ? parent.right : parent.left;
    if (sibling && sibling.red) {
      node.parent.red = true;
      sibling.red = false;
      if (node === parent.left) {
        root = rotateLeft(root, parent);
      } else {
        root = rotateRight(root, parent);
      }
    }
    return deleteCase3(root, node);
  }

  function deleteCase3(root, node) {
    var parent = node.parent;
    var sibling = !parent ? null :
      parent.left === node ? parent.right : parent.left;
    if (!(parent && parent.red) &&
        !(sibling && sibling.red) &&
        !(sibling.left && sibling.left.red) &&
        !(sibling.right && sibling.right.red)) {
      sibling.red = true;
      return deleteCase1(root, parent);
    } else {
      return deleteCase4(root, node);
    }
  }

  function deleteCase4(root, node) {
    var parent = node.parent;
    var sibling = !parent ? null :
      parent.left === node ? parent.right : parent.left;
    if ((parent && parent.red) &&
        !(sibling && sibling.red) &&
        !(sibling.left && sibling.left.red) &&
        !(sibling.right && sibling.right.red)) {
      sibling.red = true;
      parent.red = false;
      return root;
    } else {
      return deleteCase5(root, node);
    }
  }

  function deleteCase5(root, node) {
    var parent = node.parent;
    var sibling = !parent ? null :
      parent.left === node ? parent.right : parent.left;
    if (node === parent.left &&
        !(sibling && sibling.red) &&
        (sibling.left && sibling.left.red) &&
        !(sibling.right && sibling.right.red)) {
      sibling.red = true;
      sibling.left.red = false;
      root = rotateRight(root, sibling);
    } else if (node === parent.right &&
        !(sibling && sibling.red) &&
        !(sibling.left && sibling.left.red) &&
        (sibling.right && sibling.right.red)) {
      sibling.red = true;
      sibling.right.red = false;
      root = rotateLeft(root, sibling);
    }
    return deleteCase6(root, node);
  }

  function deleteCase6(root, node) {
    var parent = node.parent;
    var sibling = !parent ? null :
      parent.left === node ? parent.right : parent.left;
    sibling.red = parent.red;
    parent.red = false;
    if (node === parent.left) {
      sibling.right.red = false;
      return rotateLeft(root, parent);
    } else {
      sibling.left.red = false;
      return rotateRight(root, parent);
    }
  }

  function deleteNode(root, node, comparer) {

    // If has to non-leaf children, moving data from and removing max element
    // node from left tree.
    if (node.left && node.right) {
      var maxLeft = node.left;
      while (maxLeft.right) {
        maxLeft = maxLeft.right;
      }
      // Merely copying a value does not violate any red–black properties.
      node.data = maxLeft.data;
      node = maxLeft;
    }

    node.data = undefined;

    var child = node.left || node.right;
    if (!node.red) {
      node.red = child ? child.red : false;
      root = deleteCase1(root, node);
    }

    // Replace node with a child (or null).
    var parent = node.parent;
    if (!parent) {
      // The child will be a new root.
      if (child) {
         child.parent = null;
         child.red = false; // shall be black
      }
      return child;
    }
    if (parent.left === node) {
      parent.left = child;
    } else {
      parent.right = child;
    }
    child && (child.parent = parent);

    return root;
  }