Algorithms and Datastructures/Data Structures :: 14-06-2018

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

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

CommentsGuest Name:Comment:

[Program_Synthesis] Auto Complete;;Default.aspx?id=16;;;;[Program_Synthesis] Sketching;;Default.aspx?id=15;;;;[Lambda_Calculus] Church Numerals;;Default.aspx?id=14;;;;[Lambda_Calculus] Church Pairs;;Default.aspx?id=13;;;;[Lambda_Calculus] Church Booleans;;Default.aspx?id=12;;;;[Computer_Systems] Virtual Memory #2;;Default.aspx?id=11;;;;[Computer_Systems] Virtual Memory #1;;Default.aspx?id=1;;;;[Computer_Systems] Race Conditions;;Default.aspx?id=3;;;;[Computer_Systems] Semaphores;;Default.aspx?id=2;;;;[Algorithms_and_Datastructures] Shortest Path;;Default.aspx?id=10;;;;[Algorithms_and_Datastructures] Minimum Spanning Trees;;Default.aspx?id=9;;;;[Algorithms_and_Datastructures] Binary Search Trees;;Default.aspx?id=8;;;;[Algorithms_and_Datastructures] Heaps;;Default.aspx?id=7;;;;[Algorithms_and_Datastructures] Huffmann Codes;;Default.aspx?id=6;;;;[Algorithms_and_Datastructures] LCS - Longest Common Subsequence;;Default.aspx?id=5;;;;[Algorithms_and_Datastructures] MergeSort;;Default.aspx?id=4;;;;