union(1, 2), union(3,4), union(3,5), union(1,7), union(3,6), union(8,9), union(1,8), union(3,10), union(3,11), union(3,12), union(3,13), union(14,15), union(16,0), union(14,16), union(1,3), union(1,14)
a) Using union where the set containing the second parameter should be added to the set containing the first parameter (retaining the name of the set containing the first parameter).
b) Using union by size (number of nodes) as described in class.
2. Disjoint Sets: For your final answers to both a and b above, perform a find with path compression on one of the deepest nodes.
One application of BSTs is to implement ordered
sets. A set is a container that stores a
collection of items with no duplicates; attempting to add a duplicate item to a
set has no effect. An ordered set is a
set with the additional property that when we iterate through it, we retrieve
the elements in order as defined by the comparison function for those
elements. Note that this is different from the disjoint
sets we discussed in class and referred to above in the written problems that
have the operations union and find. Here
we are representing a single set, and the values in the set have an ordering.
For this assignment, create Java interfaces for ordered sets and their iterators and implement those interfaces using splay tree as the underlying data structure. Specifically, define and implement the following two interfaces:
BasicSet. This is the interface
describing the set operations.
Include the following: add(item) Add the specified item
to the set if it is not already present. Return true if the item was added;
false if not.contains(item) Return true if the
item is an element of the set, false if not.size() Return the number of
elements in the set.iterator() Return an iterator for
this set.BasicSetIterator. This interface specifies
iterator operations for a BasicSet.
hasNext() Return true if there is
another available element in the iteration; false if not.next() Return the next item in the
iteration. Throw a NoSuchElementException
if there is no next item. Successive calls to next() should return the items in
the set in order.Because this is a sorted set, the items in the set must have type Comparable, meaning that whatever kind
of objects they are, they implement the Comparable
interface, which includes the compareTo()
method. The ordering specified by compareTo()
is the one that determines the order in which the items are returned from the
set by successive calls to the iterator's next()
method.
After defining the interfaces, create an implementation of BasicSet in a class named BasicOrderedSplayTreeSet. That class
should contain a nested class BasicOrderedSplayTreeSetIterator
that implements the BasicSetIterator
interface.
BasicOrderedSplayTreeSet must use a
Splay tree to store the set items.BasicOrderedSplayTreeSet. A tree node should contain a reference
to the item stored at that node and single links to the node's left and
right children, plus a pointer to the parent node. (you may add more information if
desired).BasicOrderedSplayTreeSet
to refer to the root node of the tree. This should be null for an empty
tree.contains() should only search the
left or right subtree of a node when looking for a particular item.add(item) and contains(item) should splay those values to the top of the tree.previous(), hasPrevious() or remove() for the BasicSetIterator. Comparable
objects that is sufficient.Instead of trying to implement everything at once, it would probably be easier to implement the set as a regular binary tree first, then add the necessary code to do splay operations.
The splay tree representation is quite similar to that needed for the AVL tree, with two changes. First, there is no need to store an AVL balance factor or tree height in each node. Second you should add a "parent" pointer to each node that refers to that node's parent. To be efficient, splay operations require fast access to parent nodes. You may find the AVL code from the book a useful starting point.
If you are rusty on iterators, you may find these slides and this linked list code useful. (Although you do NOT need to know the material on JavaDoc or understand the code in BasicLinkedListTest.java that uses JUnit – but feel free to take a look!)
Please submit your Java source code for both the interfaces and
implementations of the tree set electronically as
individual files (not zipped into one file) using the turn-in link here. Please also print out these files and bring
them to class on the due date with your answers to the written problems.
If you work with a partner, 1) only one partner needs to submit the code electronically and make a printout. 2) Be sure that both partners’ names are listed in all files. 3) Include a text file (submit electronically and print out) that describes how you developed and tested your code. If you divided it into pieces somehow, describe that. If you worked on everything together, describe the actual process used – how long you talked about what, how long and in what order you wrote and tested the code. Be sure to describe at least one good thing and one bad thing about the process of working together. (Remember both partners need to submit individual answers to the written problems.)