This problem set is optional. You are required to know the material on this assignment, but you need not turn it in. If you do turn it in, it can only help your grade and not hurt it.

Below are two of the three problems on the assignment. The third problem (on hash tables) will be posted in the future.

---

Reading

• Tables: Chapter 13 of Bailey, Java Structures (Dictionaries).
• Heaps: Chapter 11 of Bailey, Java Structures (Priority Queues).

Reading Notes:

• Bailey distinguishes ordered dictionaries (in which keys are ordered) from unordered dictionaries (in which keys have no order). The Table interface I presented in lecture assumed that keys were ordered. It turns out that this was a bad design decision, since it interacts badly with Hashtables, in which it is difficult to enumerate keys in order. So I have changed the Table interface to specify that keys are unordered, and have added a new OrderedTable interface for tables with ordered keys.
• Chapter 11 of Bailey covers complete heaps (as we discussed in class) and something called skew heaps. The leftist heaps presented in class are similar to skew heaps, but better, since they have O(log(n)) worst case time for any enq and deq operation. In contrast, any particular enq or deq operation in a skew heap could take O(n) time, although a sequence of m such operations can only take O(m*log(m)) time if m is sufficiently large.
  
  Thus skew heaps have a good amortized efficiency even though a particular operation may be expensive. (This is similar to the array doubling implementation of vectors. It is expensive to double the size of the array, but this only happens rarely. Its cost can be amortized over a large number of addElement() operations in such a way that only a constant amount of time of time is charged per each addElement().)

Code

Problems 2 and 3 require writing Java programs. All the code for this assignment can be found in the Tables folder of ps9_programs in the CS230 download folder.

---

Problem 1: Diagramming Heaps

Recall that heapsort is a sorting algorithm with the following two stages:

1. Create a priority queue and enqueue all the elements to be sorted.
2. Repeatedly dequeue elements from the priority queue until it is empty. The order of the dequeued elements will be sorted from high to low according to the comparator of the priority queue.

The reason that the algorithm is called heapsort is that a priority queue is commonly implemented as a "heap" data structure. But the algorithm works for any implementation of priority queues, even ones that don't use the heap data structure.

In class, we studied two kinds of heaps: (1) complete heaps and (2) leftist heaps. The following parts ask you to show the sequence of intermediate heaps that would arise when running the heapsort algorithm with these two kinds of heaps on the following letters:

In both examples, you should assume that the Comparator for the heap treats letters later in the alphabet as being "greater" than ones earlier in the alphabet. Thus, sorting the above letters should yield:

Part a.

Show the intermediate heaps constructed when using a complete heap to perform heapsort on the letters:

You should show the state of the heap after each (1) enqueue operation and (2) dequeue operation. (You need not show intermediate heaps that arise during the middle of one of these operations.)

You should draw each heap as a complete binary tree whose nodes are letters. Remember that letters later in the alphabet should be on top.

Part b.

Show the intermediate heaps constructed when using leftist heaps to perform heapsort on the letters:

You should show the state of the heap after each (1) enqueue operation and (2) dequeue operation. (You need not show intermediate heaps that arise during the middle of one of these operations.)

You should draw each heap as a binary tree whose nodes contain (1) a letter and (2) the rank of the node. Recall that the rank of a node is the length of its right spine.

---

Problem 2: Implementing Tables as Mutable Binary Search Trees

In this problem you will implement a table as an object with the following three instance variables:

1. A MutableObjectTree bst containing a binary search tree in which values are instances of the TableEntry entry class ordered by their keys. Rather than pointing directly at the root of the tree, bst points a dummy header node whose left subtree is the root of the binary search tree (see the pictures below). The dummy header node simplifies many operations by guaranteeing that every node in the binary search tree (including the root) has a parent. The value and right subtree of the dummy header node are irrelevant and so can be arbitrary.
2. An integer size that holds the number of elements in the table. This variable is not strictly necessary, since it could be calculated as the number of nodes in the binary search tree. However, it is much more efficient to have the size stored as an instance variable than to calculate it every time it is neeed.
3. A Comparator comp that holds the comparator used for comparing keys in the table.

To illustrate the desired structure of the table, we consider a concrete example that is used as part of the test cases. Suppose that T is the result of new TableMutableBST. Then its object diagram is:

Executing T.insert("Emil", "3456") changes this to:

After T.insert("Viola", "5678"), this becomes:

After T.insert("Abby", "1234"), this becomes:

After T.insert("Bud", "2345"), this becomes:

After T.insert("Sam", "4567"), this becomes:

Finally, after insert("Emil", "6789"), this becomes:

The MutableObjectTree class is just like the ObjectTree class except that the components of a node can be mutated via the setValue, setLeft, and setRight methods. Here is a list of all the methods supported by the MutableObjectTree class:

public static MutableObjectTree leaf()
public static boolean isLeaf(MutableObjectTree t)
public static MutableObjectTree node(Object v, MutableObjectTree l, MutableObjectTree r)
public static Object value (MutableObjectTree t)
public static MutableObjectTree left (MutableObjectTree t)
public static MutableObjectTree right (MutableObjectTree t)
public static void setValue (MutableObjectTree t, Object newValue)
public static void setLeft (MutableObjectTree t, MutableObjectTree newLeft)
public static void setRight (MutableObjectTree t, MutableObjectTree newRight)

To do this problem, you should flesh out the skeleton in the file TableMutableBST in the Tables folder of the ps9_programs folder. You will need to implement the following seven table methods:

public void insertEntry (TableEntry entry)
Inserts the entry into this table. Any existing entry with entry.key as its key is effectively overwritten to have entry.value as its value. This method is equivalent to insert(entry.key, entry.value), where insert() is the two-argument insertion method presented in class.

public Object lookup (Object key)
Returns the value associated with key in this table, or null if there is no such value.

public void delete (Object key)
Removes the entry indexed by key from this table. Has no effect if the key is not in this table.

public int size()
Returns the number of key/value assocations in this table.

public void clear()
Removes all key/value pairs from this table.

public Object clone()
Returns a copy of this table. Operations on the copy should not affect this table, and vice versa.

public ObjectList toList()
Returns a list of the entries of this table in sorted order.

Additionally, it is very helpful to have an auxiliary method find() for finding the position of a key in a binary search tree. The insertEntry(), lookup(), and delete() methods can all be simplified using the find() method. The find() method returns a instance of the FindInfo class, which is defined as follows. (You have been provided with a definition of this class in the Table folder.)

public class FindInfo {
	
	public MutableObjectTree parent, child;
	public boolean isChildToLeft;
	
	public FindInfo (MutableObjectTree parent, 
	                  MutableObjectTree child, 
	                  boolean isChildToLeft) {
		this.parent = parent;
		this.child = child;
		this.isChildToLeft = isChildToLeft;
	}
	
}
	

Here is the contract for the find() method:

public FindInfo find (Object key,
                       MutableObjectTree parent, 
                       MutableObjectTree child, 
                       boolean isChildToLeft)

Assume that parent is the parent node of child and that isChildToLeft is true if child is the left subtree of parent and false if child is the right subtree of parent. Returns a findInfo instance describing result of looking for key in the mutable binary search tree child. Suppose that the resulting instance of findInfo is named result. Then the meaning of the components of result is as follows:

• result.child is either (1) the BST node whose value is a TableEntry with the given key (if the key was found in the table) or (2) the leaf where a TableEntry with the given key would be inserted (if the key was not found in the table.)
• result.parent is the parent of the child.
• result.isChildToLeft is true if result.child is the left subtree of result.parent, and false if result.child is the right subtree of result.parent.

As a simple test of your implementation, run the TestTable applet and select TableMutableBST. You may want to compare your output with that of the TableSortedVector implementation that is also provided in the table folder.

Notes:

• You have been provided with a class MutableObjectTreeOps class that implements the following handy tree operations, some of which you may find useful for this problem:
  public static int height (MutableObjectTree t)
  Returns the height of the tree t.

  public static ObjectList preOrderList (MutableObjectTree t)
  Returns a list of the elements of t in preorder traversal order.
  
  public static ObjectList inOrderList (MutableObjectTree t)
  Returns a list of the elements of t in inorder traversal order.
  
  public static ObjectList postOrderList (MutableObjectTree t)
  Returns a list of the elements of t in postorder traversal order.
  
  public static Object BSTMin (MutableObjectTree bst)
  Assume that bst is a non-empty binary search tree. Returns the minimum value in bst.
  
  public static Object BSTMax (MutableObjectTree bst)
  Assume that bst is a non-empty binary search tree. Returns the minimum value in bst.
  

• You can abbreviate the invocation MutableObjectTree.ZZZ() as MOT.ZZZ(); the invocation MutableObjectTreeOps.ZZZ() as MOTO.ZZZ(); the invocation ObjectList.ZZZ() as OL.ZZZ(); and the invocation ObjectListOps.ZZZ() as OLO.ZZZ().
• When implementing insertEntry(), search for the key in the binary search tree. If an entry with the key is found, replace it by the entry being inserted. If no entry with the key is found, insert a new node into the tree that replaces the leaf at which the search failed.
• When implementing delete(), recall that there are easy and hard cases for BST deletion. The easy case is when the node to be deleted (call it N) has a child that's a leaf. In this case, the pointer to N from its parent can be "rerouted" to point to its other child. The hard case is when neither child of N is a leaf. In this case, the predecessor of N (i.e., the maximum value of the nodes left subtree) should be deleted, and the value of the predecessor should be stored in the value slot of N. (Alternatively, the successor could be used.)
• When implementing clone(), be careful to copy all the table entries so that they are not shared between the original and the copy.

Submission Details: For your softcopy submission, turn in TableMutableBST.java.For your hardcopy submission, turn in TableMutableBST.java and a copy of the transcript of the test cases. If necessary, you should reformat the transcript so that all the information is visible on the printed version (i.e., no lines should fall off the right edge of the page).

 

---

Problem 3: Implementing Tables as Hash Tables

This problem is still under construction.