Binary Search Trees

BST in general

• Binary trees with the property $$ A[x.left] \leq A[x] \leq A[x.right] $$
• Supports the operations min/max, search, insert, delete, predecessor/successor in $O(h)$.
• Tree walk in $O(n)$, that is inorder, postorder and so on.

Problem: trees can be so unbalanced that the height operations take $n$ time.

Red Black Trees

Almost balanced. For a tree rooted in $x$, we call all nodes that are not leaves, internal nodes. They have the following properties

1. Every node is either red or black.
2. The root is black.
3. Every leaf $Nil$ is black.
4. If a node is red, then both its children are black.
5. For each node, all simple paths from the node to descendant leaves have the same number of black nodes.

For a tree rooted in $x$ we call the number of black nodes on any path down to any leaf the black-height of $x$. This is denoted $bh(x)$.

What makes these trees so coveted is this: A red-black tree with $n$ internal nodes has height at most $2 \cdot lg(n + 1)$. This we proof as follows

• First we want to proof that a subtree rooted in $x$ contains at least $2^{bh(x)} - 1$ internal nodes. We use induction on the height $h$ of $x$.
  • For the start we have a height of 0 which implies a $bh$ of 0 for which we get $2^{0} - 1 = 0$. For a tree with $bh = 0$ we have at least 0 internal nodes. That is true.
  • Inductive step. Let $x$ be root of the tree, and let $h(x) = k$. Assume true for $h$ less than $k$. Each child of $x$ has height at most $k - 1$, and thus we can apply the inductive hypotheses to conclude that each child has at least $2^{bh(x) - 1} - 1$ internal nodes. $x$ has at least internal nodes as the sum of the two children plus it self, that is $2(2^{bh(x) - 1} - 1) + 1 = 2^{bh(x)} - 1$.
  • And thus we conclude.
• Now observe that a tree rooted in $x$ with height $h$ has at least a $bh$ of $h/2$. This follows from the properties.
• Let $n$ be internal nodes. Now we have that $$ n \geq 2^{h/2} -1 \Rightarrow \\ n + 1 \geq 2^{h/2} \Rightarrow \\ lg(n + 1) \geq h/2 \Rightarrow \\ 2 \cdot lg(n + 1) \geq h $$
• And we are done

Rotations

After an insert og a delete the R/B-tree might have to be balanced. This is done using a rotations either left-wise or right. For left we have

Left-Rotate(T,x) y = x.right x.right = y.left if y.left \neq T.nil y.left.p = x y.p = x.p if x.p = T.nil T.root = y elseif x = x.p.left x.p.left = y else x.p.right = y y.left = x x.p = y

Rotations are $O(1)$. This can be drawn as