CMSC 341 Project 4 Notes
- 20 Nov 2001
- New sample output files have been created in Mr. Frey's
public
directory. The original p4output file was renamed to p4output.64K
Note that it is not necessary to match every value in the same output
exactly. This shouldn't be a project in which you try to guess how I
implemented the project. What is important is that the sample output data
has certain properties that allow you to answer the project questions.
If your output doesn't match exactly, it still MUST exhibit these same
properties.
-
Some students are still confused about the definition of "comparison", so
here goes...
Counting comparisons is a way to measure the running time of
find/insert/remove/etc. By counting how many times these methods compare
the data value being found/inserted/removed with the data in a node in
the tree, we can measure how far down the tree find/insert/remove have
traversed
A comparison occurs when a tree method is traversing the tree, arrives
at a node and must decide to (a) go left, (b) go right, or (c) stop.
The code (in a BST) typically looks like
if ( a < b )
go left
else if ( a > b)
go right
else
stop
This if/else if/else structure counts as one comparison. In the top-down
splay tree code, it's not so obvious.
Hope that helps
Have a good Thanksgiving
- 09 Nov 2001
The data file of integers will contain only non-negative values.
Therefore, using -1 as ITEM_NOT_FOUND when contructing the trees
will work just fine.
- 08 Nov 2001
As in other projects, you are not permitted to change the public
interface of any classes provided for you. You may of course add
any private data members or method that you feel are necessary.
In this project there are two exceptions to this policy
- It may be necessary for some const tree functions to be
changed to non-const as the result of adding code to count nodes,
or count comparisons, or other similar record keeping
- Both SplayTree.H and BinarySearchTree.H
declare their nodes as BinaryNode classes. This duplication is likely
to cause compiler errors and/or warnings when both .H files are included
in Proj4.C. Change the name of one or both of them as you like. You
will also have to change all the references to the node class whose name
you change within SplayTree.C and/or BinarySearchTree.C
Any good editor (i.e. xemacs) will have a "global search and replace"
function that let's you do this effortlessly.