next up previous index CD Book Algorithms
Next: Lecture 9 - catch Up: No Title Previous: Lecture 7 - elementary

Lecture 8 - binary trees

Listen To Part 8-1

9.1-3 Show that there is no sorting algorithm which sorts at least tex2html_wrap_inline14430 instances in O(n) time.

Think of the decision tree which can do this.    What is the shortest tree with tex2html_wrap_inline14434 leaves?



Moral: there cannot be too many good cases for any sorting algorithm!

Listen To Part 8-2

9.1-4 Show that the tex2html_wrap_inline14436 lower bound for sorting still holds with ternary comparisons.

The maximum number of leaves in a tree of height h is tex2html_wrap_inline14438 ,


So it goes for any constant base.

Listen To Part 8-3

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.

A binary tree can be implemented where each node has left and right pointer fields, an (optional) parent pointer, and a data field.

Listen To Part 8-4

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 tex2html_wrap_inline14440 and all nodes in the right subtree of x have key's tex2html_wrap_inline14442 .

tex2html_wrap14586 tex2html_wrap14588
Left: A binary search tree. Right: A heap but not a binary search tree.

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 tex2html_wrap_inline14444 or tex2html_wrap_inline14446 then the root.

Listen To Part 8-5

Searching in a Binary Tree

Dictionary search operations are easy in binary trees ...


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).

Listen To Part 8-6

Maximum and Minimum

Where are the maximum and minimum elements in a binary tree?  



while tex2html_wrap_inline14456

do x = right[x]

return x


while tex2html_wrap_inline14458

do x = left[x]

return x

Both take time proportional to the height of the tree, O(h).

Listen To Part 8-7

Where is the predecessor?

Where is the predecessor of a node in a tree, assuming all keys are distinct?   

If X has two children, its predecessor is the maximum value in its left subtree and its successor the minimum value in its right subtree.

Listen To Part 8-8

What if a node doesn't have children?

If it does not have a left child, a node's predecessor is its first left ancestor.

The proof of correctness comes from looking at the in-order traversal of the tree.


if tex2html_wrap_inline14462

then return Tree-Minimum(right[x])


while tex2html_wrap_inline14468 and (x = right[y])

do tex2html_wrap_inline14472


return y

Tree predecessor/successor both run in time proportional to the height of the tree.

Listen To Part 8-9

In-Order Traversal



if (x <> NIL)

then Inorder-Tree-Walk(left[x])

print key[x]



Listen To Part 8-10

Tree Insertion

Do a binary search to find where it should be, then replace the termination NIL pointer with the new item.  



y = NIL

x = root[T]

while tex2html_wrap_inline14486

do y = x

if key[z] < key[x]

then x = left[x]

else x = right[x]


if y = NIL

then tex2html_wrap_inline14498

else if key[z] < key[y]

then tex2html_wrap_inline14502

else tex2html_wrap_inline14504

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).

Listen To Part 8-12

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.


if (left[z] = NIL) or (right[z] = NIL)

then tex2html_wrap_inline14512

else tex2html_wrap_inline14514 Tree-Successor(z)

if tex2html_wrap_inline14516

then tex2html_wrap_inline14518

else tex2html_wrap_inline14520

if tex2html_wrap_inline14522

then tex2html_wrap_inline14524

if p[y] = NIL

then tex2html_wrap_inline14528

else if (y = left[p[y]])

then tex2html_wrap_inline14532

else tex2html_wrap_inline14534

if (y <> z)

then tex2html_wrap_inline14538

/* 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 tex2html_wrap_inline14542 , if the tree was perfectly balanced, since


But if we get unlucky with our order of insertion or deletion, we could get linear height!






In fact, random search trees on average have tex2html_wrap_inline14548 height, but we are worried about worst case height.

We can't easily use randomization - Why?

Listen To Part 8-14

Perfectly Balanced Trees

Perfectly balanced trees require a lot of work to maintain:

If we insert the key 1, we must move every single node in the tree to rebalance it, taking tex2html_wrap_inline14550 time.

Therefore, when we talk about "balanced" trees, we mean trees whose height is tex2html_wrap_inline14552 , so all dictionary operations (insert, delete, search, min/max, successor/predecessor) take tex2html_wrap_inline14554 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 tex2html_wrap_inline14556 .

Listen To Part 8-15

Red-Black Tree Definition

Red-black trees have the following properties:  

  1. Every node is colored either red or black.
  2. Every leaf (NIL pointer) is black.
  3. If a node is red then both its children are black.
  4. Every single path from a node to a decendant leaf contains the same number of black nodes.

Listen To Part 8-16

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.

If an arbitrary node is red can we color it black?

No! Because now all nodes may not have the same black height.


What tree maximizes the number of nodes in a tree of black height h?

Listen To Part 8-17

What does a red-black tree with two real nodes look like?

Not (1) - consecutive reds Not (2), (4) - Non-Uniform black height

Listen To Part 8-18

Red-Black Tree Height

Lemma: A red-black tree with n internal nodes has height at most tex2html_wrap_inline14558 .

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 tex2html_wrap_inline14560 - 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


Listen To Part 8-19

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 tex2html_wrap_inline14570 and tex2html_wrap_inline14572 , so tex2html_wrap_inline14574 .

This implies that tex2html_wrap_inline14576 ,so tex2html_wrap_inline14578 . 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.

next up previous index CD Book Algorithms
Next: Lecture 9 - catch Up: No Title Previous: Lecture 7 - elementary

Mon Jun 2 09:21:39 EDT 1997