Lab: BST

BSTBeast.java is here for your code!

Download bstlab.zip. In this lab, you will implement an efficient set using a binary search tree.

Implement parts 1 and 2 to earn 90%.
Implement parts 1, 2, and 3 to earn 95%.
Earn additional credit by completing the more challenging exercises listed at the bottom of the page.

Part 1:  Product

The Product class has been provided to you. It represents a product you might purchase, with a model name and a version number. For example:

Product p = new Product("iphone", 11);
String model = p.getModel(); //returns "iphone"
int version = p.getVersion(); //returns 11

Complete the Product class's compareTo method so that it behaves as follows.

Product x = new Product("iphone",5);
Product y = new Product("fire", 6);
Product z = new Product("fire", 7);

y is less than x, because "fire" comes before "iphone" alphabetically.
y is less than z, because these products have the same model name, and 6 is less than 7.

Part 2:  MyTreeSet

The MyTreeSet class represents a kind of set. Like all sets, MyTreeSet cannot have any duplicate elements. Inside a MyTreeSet, values are stored in a binary search tree with three fields:

private TreeNode<E> root;       // the root of the binary search tree containing all elements in the set

private int size;               // the number of elements in the set

private TreeDisplay<E> display; // a display that may be used to view the binary search tree

Because the elements of a MyTreeSet are stored in a binary search tree, they must implement the Comparable interface.

In this part, you must implement 3 methods in MyTreeSet, which you should complete in this order:

• peekMin: Returns the minimum value in the set. You should assume the set is not empty.

• contains: Returns true if obj is already in the set. Returns false otherwise.

• add: Adds obj to the set and returns true if successful. Returns false if obj is already in the set. You must call the MyTreeSet's updateDisplay method after modifying the tree and before returning, so that you can see the change in the TreeDisplay window.

Each of these MyTreeSet methods must have an expected time that is logarithmic and a worst-case time that is linear.

Part 3:  remove

Implement MyTreeSet's remove method:
public boolean remove(E obj)
This method removes obj from the set and returns true if successful. It returns false if obj was not present in the set. Like other methods in MyTreeSet, it runs in logarithmic expected time and linear worst-case time.

The key to removing an element is locating its predecessor. In the following binary search tree, 8's predecessor is 7, because 7 is the largest element less than 8. 14's predecessor is 13. The predecessor must be a decendant (child/grandchild/etc.) of the original element. Therefore, 7 and 10 have no predecessor.

To remove an element from a binary search tree, you must replace it with its predecessor. There are three cases to consider. The diagrams show how to modify the tree to remove element r.

Case 1: The element has no predecessor:

Case 2: The element's predecessor is its left child:

Case 3: The element's predecessor appears in its left child's right subtree.

Additional Credit Suggestions

Challenge #1
Implement a class called SetIterator, which behaves as follows:
MyTreeSet<Integer> set = new MyTreeSet<Integer>(true);
set.add(3);
set.add(5);
set.add(2);
SetIterator<Integer> it = set.iterator();
int n;
n = it.next(); // returns 2
n = it.next(); // returns 3
boolean b;
b = it.hasNext(); // returns true
n = it.next(); // returns 5
b = it.hasNext(); // returns false
n = set.size(); // returns 3 (set hasn't changed)

SetIterator must return the elements in sorted order. Like other methods in this lab, the iterator and next methods must run in logarithmic expected time and linear worst-case time. hasNext must run in constant time.

Challenge #2
Implement MyTreeMap<K,V>, with the following methods:
public int size()             // must run in constant time
public V get(K key)           // must run in logarithmic expected time and linear worst-case time
public V put(K key, V value)  // must run in logarithmic expected time and linear worst-case time

Challenge #3
A self-balancing binary search tree's operations run in logarithmic time in the worst-case. There are many kinds of self-balancing binary search trees. Research one and implement one of these ways.