|
You may want to consult
Bruce
Schneier's article on red black trees before starting
the assignment.
- Exercise 1. In the class text on page 280, an example
implementation of the Set class is given. The author uses a
simple binary tree to do this. As I've discussed in class, a binary
tree may become unbalanced and the O(logn) search property may be
lost. A way around this is to keep the tree balanced. A
red-black tree is one kind of balanced tree that I've presented
in class. Implement Set in terms of red-black trees.
- Exercise 2.
Using the hash table implementation given in the book on pages
422--425, implement buckets using red-black trees.
- Exercise 3.
Do Exercise 12 on page 427.
- Exercise 4. In this exercise, you will compute a word
histogram for a text file. That is, given an input file, build a
program that computes a table of word frequencies. Using the
hash table class that you developed in Exercise 1 or 2, write a
program that will prompt the user for an input file name and then
compute and print out the word histogram for that file. You may want
to change your red-black tree implementation slightly so
that node values are pairs (p. 388 in the text),
so that word counts can be indexed via word names.
|
![[CS Dept logo]](/images/logos/cs-dept-logo.gif){kind=logo}