CS410, Summer 1998
Quiz #5
July 10
							Name:
Consult no sources.

1. Name two specific kinds of binary search trees we have learned this week.

2. What is the guaranty we have for splay tree operations? 

3. What information do we store at the interior nodes of a 2-3 tree?

4. Why is rebalancing necessary after inserting an object into a 2-3 tree?
(That is, what property might be violated after the naive insertion?)

ANSWERS
=======

1. Red-black trees and splay trees.

2.5 points -- 0 points if you list 2-3 trees, else 1 point if you list
one of the two above.

2. That m insert, delete, lookup operations, starting with an empty tree will
take time O(mlog n)

2.5 points -- 2 points if left out "starting with an empty tree", 0 points if
just said O(log n) per operations.

3. The minimum key present in that node's subtree.

2.5 points.

4. The parent of the inserted node may now have 4 children.

2.5 points.