These notes might change over time, some might also be incomplete. If you find any errors or misleading text, please comment about it.

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

Every node is either red or black.

The root is black.

Every leaf $Nil$ is black.

If a node is red, then both its children are black.

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