Run your program on some small files, then try it on /usr/share/dict/linux.words, which is an online dictionary file of about 45,000 words. You will
probably find that its performance is unsatisfactory. You can
explore this a little
more using the Java method
long System.currentTimeMillis(), which returns the current system
time in milliseconds. Insert appropriate calls to this method and
run your program on smaller versions of linux.words to
find the time required to build the BST for the
first 1000 words,
then for the first 2000 words, then for the first 4000 words,
then for the first
8000 words. In each case also find the time to do a worst-case search (think
about how to produce this time.) Record both the build and search
times and interpret the results.
Since you have the entire file before you start building the BST, you
can modify the order in which you enter the words. Think about how to
do this, then write a second driver that is just like the first except that it
changes the order in which the words are inserted
to significantly improve performance.
Keep your same timing
tests in place, and again record and discuss the results.
What to turn in
Turn in hardcopy of your BTNode, BinaryTree and BST classes and corresponding
interfaces, both of your drivers, and your recorded times and
discussions of these times (these must be typed). E-mail your programs
and writeups to me
with cpsc220 prog2 in the subject.