Homework 3: Binary Search Trees
You will implement the OrderedDictionary interface using binary search
trees. You will need to use the compareTo() function to define an order
on the keys.
The input to your program will be a file which contains a sequence
of {Insert, Find, Remove, Pred, Succ, Min, Max} commands. The output should
be one line
for each command. The format of the output lines for {Insert, Find, Remove}
is shown below. The format of output lines for {Pred, Succ, Min, Max} is
similar (see input_sample and output_sample for the exact format).
For an insert command, the output should read as:
Insert "key", "value" succeeded.
or
Insert "key", "value" failed. "key" already exists.
For a find command, the output should read as:
Find "key" returned "key", "value"
or
Find "key" returned null
For a remove command, the output should read as:
Remove "key" removed "key", "value"
or
Remove "key" failed. "key" does not exist.
Notice that keys and key-value pairs should always be in quotes as shown.
The name of the file will be specified as a command-line argument:
e.g.: java BST commands-file
We have provided an "input_sample" and the corresponding "output_sample"
files. To test your programs, do the following:
java BST input_sample
For a correct implementation, the output should be identical to "output_sample"
To test if your implementation is correct, use:
- java BST commands > out
- diff out output_sample
Support files:
- OrderedDictionary.java
- Entry.java
- BST.java
- input_sample
- output_sample
Test Outputs:
- Test1
- Test2
Results
grading