Due Wednesday, 21 October 2015 at 1300
Navigation
A. Introduction
For this assignment, you'll create a BST based implementation of the
StringSet interface, which provides an abstraction for sets that
contain Strings. To keep things simple, your set will only allow
put
and contains
operations. You'll then compare the
performance of your implementation to a reference implementation based
on linked lists as well as the built-in Java BST set.
To implement the interface, you'll be working completely from scratch, with no skeleton code.
B. BSTStringSet
Create a class BSTStringSet that implements the StringSet interface using a BST as its core data structure. As references, you might find the following resources useful:
- BST code from pages 110 and 111 of DSIJ.
LinkedListStringSet.java
, which provides a working linked list based StringSet implementation.
Your implementation should support the ability to create an initially
empty StringSet
with a no-argument BSTStringSet
constructor, e.g.
StringSet s = new BSTStringSet()
. While not required by the
interface, you'll need this for the speed tester (in part C) to work.
Look closely at LinkedListStringSet
to see how this
class achieves the ability to be instantiated as an initially empty
set.
Optionally: Override toString
that produces a textual representation
of your BSTStringSet
in order. This makes them easy to print or look at in
a debugger.
C. Speed Testing
The InsertRandomSpeedTest
class performs speed testing on LinkedListStringSet
, your BSTStringSet
, and Java's built-in TreeSet
class. It works by asking the user for an input size N, then generates N strings of length 10 and inserts them into the set.
Try it out and see how your data structure scales with N compared to the naive and industrial strength implementations. Record your results in speedTest.txt. There is no standard format required for your results, and there is no required number of data points.
Create a new test
InsertInOrderSpeedTest
. Instead of inserting random strings, it should insert strings in increasing lexicographic order. For example, it might insert "cow", "cox", "coy", "coz", "cpa", "cpb", .... You'll want to use the NextString
method provided in StringUtils
. I'd recommend starting by just copying and pasting the code from InsertRandomSpeedTest
and then making changes where necessary.
Now try running InsertInOrderSpeedTest
. Again record your results in speedTests.txt. If you observed anthing interesting (hopefully you did), then you should explain this interesting thing.
D. Generic Set
Create an implementation BSTGenericSet
that implements the
GenericSet
interface.
E. SimpleDictionary
Create an implementation BSTDictionary
that implements the
SimpleDictionary
interface.