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. Break ties by adding the set that contains the second parameter to the set containing the first parameter.
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.
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 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 a 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. (For example for integers this would mean returning values in increasing order.)
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. (Note:
If the call to add(item)
attempts to insert a duplicate value, the duplicate should not be added,
but the original value should splay to the
top. If a call to
contains(item)
returns false, it should splay the last (deepest)
node in the access path to the top of the tree.)previous(), hasPrevious() or remove() for the BasicSetIterator. 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.
Although the book contains an implementation of a top-down splay tree in chapter 12, this is not what we discussed in class and is not likely to be very useful. To be clear, you should NOT submit code for a top down splay tree for this assignment.
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) via catalyst.
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.)