1.
Do enough insertions to convince yourself that if red-black rules 1, 2, and 3 are
followed exactly, Rule 4 will take care of itself.
2.
Draw by hand what a 2-3-4 tree looks like after each of the following insertions:
10, 20, 30, 40, 50, 60, 70, 80, and 90. Don’t use the Tree234 Workshop
applet.
3.
Draw by hand what a 2-3 tree looks like after inserting the same sequence of
values as in Experiment 1.
4.
Think about how you would remove a node from a 2-3-4 tree.
5.
In linear probing, the time for an unsuccessful search is related to the cluster
size. Using the Hash workshop applet, find the average cluster size for 30 items
filled into 60 cells, with a load factor of 0.5. Consider an isolated cell (that is,
with empty cells on both sides) to be a cluster of size 1. To find the average,
you could count the number of cells in each cluster and divide by the number
of clusters, but there’s an easier way. What is it? Repeat this experiment for a
half-dozen 30-item fills and average the cluster sizes. Repeat the entire process
for load factors of 0.6, 0.7, 0.8, and 0.9. Do your results agree with the chart?