Left-leaning red-black tree

README.md

Left-Leaning Red-Black Tree

This is a TypeScript implementation of the Left-Leaning Red-Black Tree.

Usage

import LLRBTree from './llrbtree'

const tree = new LLRBTree((a: number, b: number) => a - b);

tree.insert(10, 'foo');
tree.insert(20, 'bar');
tree.insert(42, 'baz');

console.log(tree.search(42));

llrbtree.ts

type Color = boolean;

const red = true;
const black = false;

class LLRBNode<Key, Value> {
  left: LLRBNode<Key, Value> = null
  right: LLRBNode<Key, Value> = null
  color: Color = red

  constructor(public key: Key, public value: Value) {}

  get isRed(): boolean { return this.color === red; }
}

const isRed = <Key, Value>(node: LLRBNode<Key, Value>) => {
  if (node === null) { return false; }
  return node.color === red;
};

const colorFlip = <Key, Value>(h: LLRBNode<Key, Value>) => {
  h.color = !h.color;
  h.left.color = !h.left.color;
  h.right.color = !h.right.color;
};

const rotateLeft = <Key, Value>(
  h: LLRBNode<Key, Value>
): LLRBNode<Key, Value> => {
  let x = h.right;
  h.right = x.left;
  x.left = h;
  x.color = h.color;
  h.color = red;
  return x;
}

const rotateRight = <Key, Value>(
  h: LLRBNode<Key, Value>
): LLRBNode<Key, Value> => {
  let x = h.left;
  h.left = x.right;
  x.right = h;
  x.color = h.color;
  h.color = red;
  return x;
}

const moveRedLeft = <Key, Value>(
  h: LLRBNode<Key, Value>
): LLRBNode<Key, Value> => {
  colorFlip(h);
  if (isRed(h.right.left)) {
    h.right = rotateRight(h.right);
    h = rotateLeft(h);
    colorFlip(h);
  }
  return h;
};

const moveRedRight = <Key, Value>(
  h: LLRBNode<Key, Value>
): LLRBNode<Key, Value> => {
  colorFlip(h);
  if (isRed(h.left.left)) {
    h = rotateRight(h);
    colorFlip(h);
  }
  return h;
};

const fixup = <Key, Value>(h: LLRBNode<Key, Value>): LLRBNode<Key, Value> => {
  if (isRed(h.right) && !isRed(h.left)) { h = rotateLeft(h); }
  if (isRed(h.left) && isRed(h.left.left)) { h = rotateRight(h); }
  return h;
};

const min = <Key, Value>(h: LLRBNode<Key, Value>): LLRBNode<Key, Value> => {
  if (h.left === null) { return h; }
  return min(h.left);
};

export default class LLRB<Key, Value> {
  private root: LLRBNode<Key, Value> = null;

  constructor(private comparator) {}

  search(key: Key): Value {
    let x = this.root;
    while (x !== null) {
      const cmp = this.comparator(key, x.key);
      if (cmp === 0) { return x.value; }
      else if (cmp < 0) { x = x.left; }
      else if (cmp > 0) { x = x.right; }
    }
    return null
  }

  get(h: LLRBNode<Key, Value>, key: Key): Value {
    let x = h;
    while (x !== null) {
      const cmp = this.comparator(key, x.key);
      if (cmp === 0) { return x.value; }
      else if (cmp < 0) { x = x.left; }
      else if (cmp > 0) { x = x.right; }
    }
    return null;
  }

  insert(key: Key, value: Value) {
    this.root = this._insert(this.root, key, value);
    this.root.color = black;
  }

  private _insert(h: LLRBNode<Key, Value>, key: Key, value: Value): LLRBNode<Key, Value> {
    if (h === null) { return new LLRBNode<Key, Value>(key, value); }
    if (isRed(h.left) && isRed(h.right)) { colorFlip(h); }

    const cmp = this.comparator(key, h.key);
    if (cmp === 0) { h.value = value; }
    else if (cmp < 0) { h.left = this._insert(h.left, key, value); }
    else { h.right = this._insert(h.right, key, value); }

    return fixup(h);
  }

  deleteMin() {
    this.root = this._deleteMin(this.root);
    this.root.color = black;
  }

  private _deleteMin(h: LLRBNode<Key, Value>): LLRBNode<Key, Value> {
    if (h.left === null) { return null; }
    if (!isRed(h.left) && !isRed(h.left.left)) {
      h = moveRedLeft(h);
    }
    h.left = this._deleteMin(h.left);

    return fixup(h);
  }

  delete(key: Key) {
    this.root = this._delete(this.root, key);
    this.root.color = black;
  }

  _delete(h: LLRBNode<Key, Value>, key: Key): LLRBNode<Key, Value> {
    if (this.comparator(key, h.key) < 0) {
      if (!isRed(h.left) && !isRed(h.left.left)) { h = moveRedLeft(h); }
      h.left = this._delete(h.left, key);
    } else {
      if (isRed(h.left)) { h = rotateRight(h); }
      if (this.comparator(key, h.key) === 0 && (h.right === null)) {
        return null;
      }
      if (!isRed(h.right) && !isRed(h.right.left)) { h = moveRedRight(h); }
      if (this.comparator(h.key) === 0) {
        h.value = this.get(h.right, min(h.right).key);
        h.key = min(h.right).key;
        h.right = this._deleteMin(h.right);
      } else { h.right = this._delete(h.right, key); }
    }
    return fixup(h);
  }

}