Red Black Tree

From Textbook: Red-Black Trees

Invariant¶

1. Every node is colored either red or black

2. Leaves and root colored black

3. Local Invariant: no red node has a direct red child (only applies to its direct children and doesn’t apply to grand children or grand-grandchildren; in other words, red nodes cannot be repeated)

4. Global Invariant: Every path from the root to a leaf has the same number of black nodes

The invariant implies that: length of longest path is at most twice as long as as the shortest path. (extreme case: path with red node in between each black node vs. path with only black nodes: B-R-B-R-B-R-B vs. B-B-B-B)

Implementation¶

红黑树的 OCaml 实现着实震惊了我，让我惊讶 OCaml 原来是这么强大的一个语言

Note where in the code we applied balance. It is the father of the node that breaks the invariant and is also the deepest black node where an invariant is violated.

let balance = function
  | Black, z, Node (Red, y, Node (Red, x, a, b), c), d
  | Black, z, Node (Red, x, a, Node (Red, y, b, c)), d
  | Black, x, a, Node (Red, z, Node (Red, y, b, c), d)
  | Black, x, a, Node (Red, y, b, Node (Red, z, c, d)) ->
      Node (Red, y, Node (Black, x, a, b), Node (Black, z, c, d))
  | a, b, c, d -> Node (a, b, c, d)

let insert x s =
  let rec ins = function
    | Leaf -> Node (Red, x, Leaf, Leaf)
    | Node (color, y, a, b) as s ->
      if x < y then balance (color, y, ins a, b)
      else if x > y then balance (color, y, a, ins b)
      else s in
  match ins s with
    | Node (_, y, a, b) -> Node (Black, y, a, b)
    | Leaf -> (* guaranteed to be nonempty *)
        failwith "RBT insert failed with ins returning leaf"