9.1-3 Show that there is no sorting algorithm which sorts at least instances in O(n) time.
Moral: there cannot be too many good cases for any sorting algorithm!
9.1-4 Show that the lower bound for sorting still holds with ternary comparisons.
So it goes for any constant base.
Binary Search Trees
``I think that I shall never see
a poem as lovely as a tree Poem's
are wrote by fools like me but only
G-d can make a tree ``
- Joyce Kilmer
Binary search trees provide a data structure which efficiently supports all six dictionary operations.
A binary tree is a rooted tree where each node contains at most two children.
Each child can be identified as either a left or right child.
Binary Search Trees
A binary search tree labels each node in a binary tree with a single key such that for any node x, and nodes in the left subtree of x have keys and all nodes in the right subtree of x have key's .
The search tree labeling enables us to find where any key is. Start at the root - if that is not the one we want, search either left or right depending upon whether what we want is or then the root.
Searching in a Binary Tree
Dictionary search operations are easy in binary trees ...
TREE-SEARCH(x, k)
if (x = NIL) and (k = key[x])
then return x
if (k < key[x])
then return TREE-SEARCH(left[x],k)
else return TREE-SEARCH(right[x],k)
The algorithm works because both the left and right subtrees of a binary search tree are binary search trees - recursive structure, recursive algorithm.
This takes time proportional to the height of the tree, O(h).
Maximum and Minimum
Where are the maximum and minimum elements in a binary tree?
TREE-MAXIMUM(X)
while
do x = right[x]
return x
TREE-MINIMUM(x)
while
do x = left[x]
return x
Both take time proportional to the height of the tree, O(h).
Where is the predecessor?
Where is the predecessor of a node in a tree, assuming all keys are distinct?
What if a node doesn't have children?
The proof of correctness comes from looking at the in-order traversal of the tree.
Tree-Successor(x)
if
then return Tree-Minimum(right[x])
while and (x = right[y])
do
return y
Tree predecessor/successor both run in time proportional to the height of the tree.
In-Order Traversal
Inorder-Tree-walk(x)
if (x <> NIL)
then Inorder-Tree-Walk(left[x])
print key[x]
Inorder-Tree-walk(right[x])
A-B-C-D-E-F-G-H
Tree Insertion
Do a binary search to find where it should be, then replace the termination NIL pointer with the new item.
Tree-insert(T,z)
y = NIL
x = root[T]
while
do y = x
if key[z] < key[x]
then x = left[x]
else x = right[x]
if y = NIL
then
else if key[z] < key[y]
then
else
y is maintained as the parent of x, since x eventually becomes NIL.
The final test establishes whether the NIL was a left or right turn from y.
Insertion takes time proportional to the height of the tree, O(h).
Tree Deletion
Deletion is somewhat more tricky than insertion, because the node to die may not be a leaf, and thus effect other nodes.
Case (a), where the node is a leaf, is simple - just NIL out the parents child pointer.
Case (b), where a node has one chld, the doomed node can just be cut out.
Case (c), relabel the node as its successor (which has at most one child when z has two children!) and delete the successor!
This implementation of deletion assumes parent pointers to make the code nicer, but if you had to save space they could be dispensed with by keeping the pointers on the search path stored in a stack.
Tree-Delete(T,z)
if (left[z] = NIL) or (right[z] = NIL)
then
else Tree-Successor(z)
if
then
else
if
then
if p[y] = NIL
then
else if (y = left[p[y]])
then
else
if (y <> z)
then
/* If y has other fields, copy them, too. */
return y
Lines 1-3 determine which node y is physically removed.
Lines 4-6 identify x as the non-nil decendant, if any.
Lines 7-8 give x a new parent.
Lines 9-10 modify the root node, if necessary
Lines 11-13 reattach the subtree, if necessary.
Lines 14-16 if the removed node is deleted, copy.
Conclusion: deletion takes time proportional to the height of the tree. Listen To Part 8-13
Balanced Search Trees
All six of our dictionary operations, when implemented with binary search trees, take O(h), where h is the height of the tree.
The best height we could hope to get is , if the tree was perfectly balanced, since
But if we get unlucky with our order of insertion or deletion, we could get linear height!
insert(a)
insert(b)
insert(c)
insert(d)
We can't easily use randomization - Why?
Perfectly Balanced Trees
Perfectly balanced trees require a lot of work to maintain:
Therefore, when we talk about "balanced" trees, we mean trees whose height is , so all dictionary operations (insert, delete, search, min/max, successor/predecessor) take time.
Red-Black trees are binary search trees where each node is assigned a color, where the coloring scheme helps us maintain the height as .
Red-Black Tree Definition
Red-black trees have the following properties:
What does this mean?
If the root of a red-black tree is black can we just color it red?
No! For one of its children might be red.
No! Because now all nodes may not have the same black height.
Red-Black Tree Height
Lemma: A red-black tree with n internal nodes has height at most .
Proof: Our strategy; first we bound the number of nodes in any subtree, then we bound the height of any subtree.
We claim that any subtree rooted at x has at least - 1 internal nodes, where bh(x) is the black height of node x.
Proof, by induction:
Now assume it is true for all tree with black height < bh(x).
If x is black, both subtrees have black height bh(x)-1. If x is red, the subtrees have black height bh(x).
Therefore, the number of internal nodes in any subtree is
Now, let h be the height of our red-black tree. At least half the nodes on any single path from root to leaf must be black if we ignore the root.
Thus and , so .
This implies that ,so . height6pt width4pt
Therefore red-black trees have height at most twice optimal. We have a balanced search tree if we can maintain the red-black tree structure under insertion and deletion.