CS230 Data Structures, Wellesley College, Fall 1999

Problem Set 8

Due on Saturday, December 4

[CS230 Home Page] [Assignments] [Documentation] [Software Installation] [FAQ] [CS Dept.] [CWIS]


Problem 1: Diagramming Destruction

Suppose that the following statements are executed in sequence within a subclass of MutableObjectList. For each statement, draw the box-and-pointer diagram that describes the state of the variables after that command.

MutableObjectList p = prepend("a", prepend("b", empty()));
MutableObjectList q = prepend("c", prepend("d", prepend("e", empty())));
MutableObjectList r = p;
setHead(tail(r), "f");
r = tail(q);
setTail(q, prepend("g", tail(p)));
setTail(tail(r), tail(p));
setTail(tail(p), r)
setHead(tail(tail(tail(r))), "h");


Problem 2: Diagramming BSTs

Part a.

Draw the sequence of binary search trees that would be obtained by starting with the empty binary search tree and inserting the following eight letters in order:

R E D B L A C K

You only need to show the result of each insertion, and do not need to show any sharing with the previous trees. Your final tree should have eight nodes.

Part b.

Let T be the name of the final tree from Part a. Draw the sequence of binary search trees that would be obtained by starting with T and deleting the following eight letters in order:

R E D B L A C K

In the case where the node to be deleted has two non-empty subtrees, assume that the node is replaced by its predecessor, that is, the maximum value of its left subtree. (The successor would also work, but we want the deletion process to be unambiguous.)

You only need to show the result of each deletion, and do not need to show any sharing with the previous trees.

Parts c and d.

Repeat Parts a and b, except perform the insertions and deletions using red-black trees. Notes:


Problem 3: Circular Queues

In class, we saw that a queue could be efficiently represented as a mutable list as long as we maintained pointers to both the front node of the list (where elements are dequeued) and to the last node of the list (where elements are enqueued). In this problem, we shall see that it is possible to get by with just a single pointer if we represent the queue as a circular list -- i.e., a list that wraps back on itself.

For instance, in this representation, enqueuing "A", "B", and "C" in order onto an initially empty queue would lead to a sequence structures depicted by the following box-and-pointer diagrams:

In the diagrams, the nodes have been annotated with labels that indicate the identity of the nodes. These labels underscore the fact that, in this representation, the head of a node never changes. However, the tails of nodes are rewired to give the depicted structure.

In all but the empty queue case, the queue variable holds a pointer to the back node of the queue (the one most recently enqueued). This facilitates enqueueing a new back node as well as dequeuing the front node (least recently enqueued) node, which is always the tail of the back node.

In this problem, you will implement queues in terms of the circular list representation sketched above. Using the static methods of MutableObjectLists (empty(), isEmpty(), prepend(), head(), tail(), setHead(), and setTail()), implement the following queue operations in the destructive interface to queues:

Constructor Method:

public QueueCircular ();

Instance Methods:

public boolean isEmpty();
public void enq (Object x);
public Object deq ();
public Object first();
public int size(); 
public void clear();
public Object clone();
public ObjectList toList();

The file QueueCircular.java in the Object Collections folder of the ps8-programs folder contains code skeletons for these methods that you should flesh out. You can test your implementation by double-clicking on QueueCircular when running the CollectionsTest.html applet.

Notes:

Submission Details: For your softcopy submission, turn in QueueCircular.java.For your hardcopy submission, turn in QueueCircular.java and a copy of the transcript of the test cases.