red-black tree

constituents

a binary search tree

requirements

  • every node is colored red or black
  • root node is black
  • NIL children are black node
  • children of red nodes are black nodes
  • for all nodes x, all parts from x to NIL have the same number of black nodes
  • for all nodes, all paths from x to nil have the same number of black nodes

additional information

intuition

  1. black nodes are balanced — “every path from root to nil would have the same black nodes”
  2. red nodes are “spread out” so they don’t mess things up too much

Its weaker than perfect balance, and its not too weak to break things.

rotation

  • you can “lift” one node as the root of the tree
  • then we have to slide redundant nodes down such that nodes have exactly <= 2 children

proxy

We need a proxy for balance such that we can claim a tree is “approximately balanced”.

proof

The high of a red-black tree with \(n\) non-nil nodes is at most \(2 \log \qty(n+1)\)

Let’s define \(b\qty(x)\) to be the number of black nodes in any path from \(x\) to NIL, excluding \(x\), including NIL. Claim: there are at least \(2^{b\qty(x)} -1\) non NIL nodes in the subtree underneath \(x\), including \(x\). IH: claim is true for all nodes \(x\) of height at most \(h\).

So now consider the root. Our IH from above gives \(n \geq 2^{b\qty(\text{root})} -1\). Now, notice that \(b\qty(\text{root}) \geq \frac{\text{height}}{2}\), because at most every other node is red, and hence \(2b\qty(\text{root})\) must be greater than or equal to height. This gives:

\begin{equation} n \geq 2^{\frac{\text{height}}{2}} -1 \implies \text{height} \leq 2 \log \qty(n+1) \end{equation}

This gives that the tree is approximately balanced.