Red Black Tree

A red-black tree is a self-balancing binary search tree that uses color-coded nodes to maintain balance and ensure efficient search, insertion, and deletion operations.

Visualization

There are properties that a red-black tree must satisfy:

1. Node Color: Every node is either red or black.
2. Root: The root is black.
3. Red Node Property: No two consecutive red nodes. In other words, if a node is red, then all of its children (if any) are black.
4. Black height: For each node, all simple paths from the node to descendant null pointers contain the same number of black nodes (black height).

These properties ensure that the longest possible path (the one with alternating black and red nodes) is no more than twice as long as the shortest possible path (the one with only black nodes).

These properties ensure that with every node in the red-black tree, the height difference between the left and right sub-tree is no more than twice. This guarantees that the worst-case time complexity for search, insertion, and deletion operations is O(log n), where n is the number of nodes in the tree. Especially the no more than twice property makes red-black tree very efficient in a high frequency of insertion and deletion operations, because it only needs a little reconstruction, which is formed by many rotation steps.

Insertion

First, we insert the new node as we do in a regular Binary Search Tree, then color the newly inserted node red. We call the new node K, parent of the new node P, grandparent of the new node G, and uncle node U (sibling of the parent node).

1. If the new node is root, change its color to black and done.
2. If the parent of the new node is black, the insertion is done.
3. If the parent of the new node is red, we have to fix the above Property(3) violation.
   1. (3.1) P and U are red: change P and U into black, G into red. Repeat with G as the new node (repeat to fix the violation if needed upper in the tree).
   2. (3.2) P is red and U is black (or NULL), base on P and K is left or right child

      1. (3.2.1) P is right child of G, K is right child of P

         1. Left rotation at G.
         2. Change P into black, G into red.

      2. (3.2.2) P is right child of G, K is left child of P

         1. Right rotation at P.
         2. Back to case 3.2.1.

      3. (3.2.3) P is left child of G, K is left child of P (reverse of 3.2.1)

         1. Right rotation at G.
         2. Change P into black, G into red.

      4. (3.2.4) P is left child of G, K is right child of P

         1. Left rotation at P.
         2. Back to case 3.2.3.

Deletion

First, we follow steps of deletion in a regular binary search tree, bring to the case we will delete x at the leaf or has only 1 child.

The idea of the algorithm is finding red nearby x then trying to turn x into red by applying rotation and color change. Then we can simply remove red node x without violating red-black tree properties.

We call the sibling of x S, parent of x P.

1. If x is red, simply remove x.

2. If x is black and has only 1 child. This child should be red or the Property(4) above is violated.

   • Swapping color of x and its child.
   • We remove x by replacing it with its child.

3. If x is black and not case 2. We apply rotation and color changing to turn x into red. To simplify we consider the case x is left-child (in case x is right-child we do the same steps but reverse the rotation)

   • (3.1) S is black, S.right is red. In this case P, S.left are either red or black still ok.

     • Rotate left at P.
     • Make S color same to P.
     • Make P, S.right black.
     • Make x red.

   • (3.2) S is black, S.right is black (or NULL), S.left is red.

     • Make S red, S.left black.
     • Rotate right at S.
     • Back to case 3.1.

   • (3.3) S is black, both S children are black.

     • (3.3.1) P is red.
       • Make P black.
       • Make S, x red.
     • (3.3.2) P is black.
       • The subtree we are checking all black, we repeat from the beginning of step 3 with mission to turn P into red (recursive call upper in the tree, with P plays the new x role).
       • After turn P into red, back to case 3.3.1.

   • (3.4) S is red. In this case, both S children are black according to Property 3.

     • Rotate left P.
     • Make S black, P red.
     • Back to case 3.1, 3.2 or 3.3.1 (x black, P red and new S black).

Sample code

export interface RedBlackNode {
  value: number
  color: 0 | 1
  parent: RedBlackNode | null
  left: RedBlackNode | null
  right: RedBlackNode | null
}

function createNode(value: number): RedBlackNode {
  return {
    value,
    color: 1,
    parent: null,
    left: null,
    right: null
  }
}

export class RedBlackTree {
  root: RedBlackNode | null = null

  insert(value: number) {
    console.log('insert', value)
    const k = insertNode(this.root, value)
    if (!k) return
    if (!this.root) {
      this.root = k
    }

    this.fixInsert(k)
  }

  remove(value: number) {
    const delNode = searchNode(this.root, value)
    if (!delNode) return

    // find actual removed node
    let altNode: RedBlackNode | null = null
    if (delNode.left && delNode.right) {
      altNode = findMinNode(delNode.right)
    }

    const xNode = altNode || delNode

    // fix the node to be deleted
    this.fixDelete(xNode)

    // override delnode if different, then delete
    delNode.value = xNode.value
    this.deleteNode(xNode)
  }

  private rotateLeft(x: RedBlackNode): void {
    if (!x) return
    const p = x.parent
    const y = x.right
    if (!y) return
    const b = y.left

    // update b
    if (b) b.parent = x

    // update x
    x.parent = y
    x.right = b

    // update y
    y.parent = p
    y.left = x

    // update p
    if (p) {
      // not rotate root
      if (p.left === x) {
        p.left = y
      } else {
        p.right = y
      }
    } else {
      // rotate root
      this.root = y
    }
  }

  private rotateRight(y: RedBlackNode): void {
    if (!y) return
    const p = y.parent
    const x = y.left
    if (!x) return
    const b = x.right

    // update b
    if (b) b.parent = y

    // update y
    y.parent = x
    y.left = b

    // update x
    x.parent = p
    x.right = y

    // update p
    if (p) {
      // not rotate root
      if (p.left === y) {
        p.left = x
      } else {
        p.right = x
      }
    } else {
      // rotate root
      this.root = x
    }
  }

  private deleteNode(node: RedBlackNode) {
    if (!node) return
    if (node.left && node.right) return

    const child = node.left || node.right
    const p = node.parent
    if (p) {
      if (p.left === node) {
        p.left = child
      } else {
        p.right = child
      }
      if (child) {
        child.parent = p
      }
    } else {
      this.root = child
      if (child) {
        child.parent = null
      }
    }
  }

  // fix 2 consecutive red nodes (mainly)
  private fixInsert(k: RedBlackNode) {
    const p = k.parent
    if (!p) {
      // root node, make it black
      k.color = 0
      return
    }

    const isNodeLeft = p.left === k

    if (!isRed(p)) {
      // Case 2: nothing to do if parent is black
      return
    }

    const g = p.parent
    if (!g) return

    const isParentLeft = g.left === p
    const u = isParentLeft ? g.right : g.left

    if (u && isRed(u)) {
      p.color = 0
      u.color = 0
      g.color = 1
      this.fixInsert(g)
      return
    }

    // u is black

    if (!isParentLeft) {
      // p is right child
      if (!isNodeLeft) {
        // node is right child
        this.rotateLeft(g)
        p.color = 0
        g.color = 1
      } else {
        // node is left child
        this.rotateRight(p)
        // repeat the above fix
        this.fixInsert(p)
      }
    } else {
      // p is left child
      if (isNodeLeft) {
        // node is left
        this.rotateRight(g)
        p.color = 0
        g.color = 1
      } else {
        this.rotateLeft(p)
        this.fixInsert(p)
      }
    }
  }

  // try to turn the node into red
  private fixDelete(x: RedBlackNode) {
    console.log('fix_Delete', x)
    if (isRed(x)) {
      return
    }

    // only 1 red child node
    if (!x.left || !x.right) {
      const child = x.left || x.right
      if (child && isRed(child)) {
        x.color = 1
        child.color = 0
        return
      }
    }

    // x's children are black (possibly NULL)

    const p = x.parent
    // if x is root change color to red
    // (to remove or swap again after recursive call)
    if (!p) {
      // TODO document this case
      x.color = 1
      return
    }

    const isNodeLeft = p.left === x
    // sibling

    if (isNodeLeft) {
      const s = p.right
      // this case not exist (break attribute 5)
      if (!s) return

      // s is black
      if (!isRed(s)) {
        if (s.right && isRed(s.right)) {
          // 3.1, s.right is red
          this.rotateLeft(p)
          s.color = p.color
          p.color = 0
          s.right.color = 0
          x.color = 1 // done
        } else  if (s.left && isRed(s.left)) {
          // 3.2, s.left is red
          s.color = 1
          s.left.color = 0
          this.rotateRight(s)
          // reduce to 3.1
          this.fixDelete(x)
        } else {
          // 3.3, both s's children are black
          if (isRed(p)) {
            // 3.3.1
            p.color = 0
            s.color = 1
            x.color = 1
          } else {
            // 3.3.2
            // TODO check if P root do {...}
            this.fixDelete(p)
            // changed p into red, reduce to 3.3.1
            this.fixDelete(x)
          }
        }
      } else {
        // 3.4
        this.rotateLeft(p)
        s.color = 0
        p.color = 1
        // reduce to 3.1, 3.2 or 3.3.1
        this.fixDelete(x)
      }
    } else {
      // mirror of above 3.* cases
      const s = p.left
      // this case not exist (break attribute 5)
      if (!s) return
      // s is black
      if (!isRed(s)) {
        if (s.left && isRed(s.left)) {
          // mirror 3.1, s.left is red
          this.rotateRight(p)
          s.color = p.color
          p.color = 0
          s.left.color = 0
          x.color = 1 // done
        } else  if (s.right && isRed(s.right)) {
          // mirror 3.2, s.right is red
          this.rotateLeft(s)
          s.color = 1
          s.right.color = 0
          // reduce to mirror 3.1
          this.fixDelete(x)
        } else {
          // mirror 3.3, both s's children are black
          if (isRed(p)) {
            // mirror 3.3.1
            p.color = 0
            s.color = 1
            x.color = 1
          } else {
            // mirror 3.3.2
            this.fixDelete(p)
            // changed p into red, reduce to mirror 3.3.1
            this.fixDelete(x)
          }
        }
      } else {
        // mirror 3.4
        this.rotateRight(p)
        s.color = 0
        p.color = 1
        // reduce to mirror 3.1, 3.2 or 3.3.1
        this.fixDelete(x)
      }
    }
  }
}

function insertNode(node: RedBlackNode | null, value: number): RedBlackNode | null {
  if (!node) {
    return createNode(value)
  }

  // no insert duplicate value
  if (node.value === value) return null

  const isGoLeft = value < node.value
  const next = isGoLeft ? node.left : node.right

  const k = insertNode(next, value)
  if (!k) return null

  if (!next) {
    // just created k
    k.parent = node
    if (isGoLeft) {
      node.left = k
    } else {
      node.right = k
    }
  }

  return k
}

function isRed(node: RedBlackNode | null): boolean {
  return node ? node.color === 1 : false
}

function searchNode(node: RedBlackNode | null, value: number): RedBlackNode | null {
  if (!node) return null
  if (node.value === value) return node
  if (value < node.value) {
    return searchNode(node.left, value)
  }

  return searchNode(node.right, value)
}

function findMinNode(node: RedBlackNode): RedBlackNode {
  let n = node
  while (n.left) n = n.left

  return n
}