Solutions/Hints for Sample Test 2

Q1

First look at the tree to figure out what the only possible value of t is.

When I taught this class in 2009, we only covered the B-tree insertion
algorithm with pre-emptive/eager splitting of nodes.  That algorithm
will split the nodes containing FLP and SWY, and then insert Q into the
leaf containing R.

Q2

The depth of node x is the number of edges along a path from the root to x.
Only a rotation can modify the depth of x, increasing or decreasing it by 1.
How many rotations can an insertion cause?  Can you think of an example
RBT where all of the rotations caused by the insertion modify the depth
of the same node x?

Q3

To do union by height, you would have to know the height of each tree.
Why is it difficult to keep track of the height?

Q4

This is similar to the SUCCESSOR function for BSTs:  see p.319 of the
textbook (4th ed).

Q5

INCORRECT solution:  augment the BST so that each node x has a new field
x.avg that stores the average of all elements in the subtree rooted at x.
This doesn't work because you can't figure out x.avg from the avg fields
of x's children.

What TWO numbers could you keep track of as you do insertions and deletions
that would allow you to compute the average of the elements currently
in the set.

Once you can compute the average, you can do an EXTRACT-AVERAGE using
a combination of known BST routines.

Q6

To get the best possible bound, you can do an amortized analysis so
that INSERTS pay for DELETES and EXTRACT-AVERAGES.

Remark:  the lower bound on comparison-based sorting says you can't
tighten the bound.