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:

• You should assume that the insertion process always colors the root of top-level tree black after each insertion.
• As in Part b, assume that deleting a node N with two non-empty subtrees replaces it by its predecessor. This case should proceed in two steps: (1) replace the value of N by the value of its predecessor P, leaving the color of N unchanged; (2) delete the node originally holding the predecessor, removing doubly-black nodes as discussed in lecture.
• Although not necessary, you may wish to show intermediate trees used in the process of removing red-red violations (for insertion) or removing doubly-black nodes (for deletion).

## 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:

• You need to prefix any method of the MutableObjectList class with "MOL." E.g., MOL.empty(), etc.
• The toList() method requires returning an (immutable) ObjectList, which is a completely separate class from MutableObjectList. You need to prefix any method of the ObjectList class with "OL." E.g., OL.empty(), etc. To simplify converting between immutable and mutable object lists, the following operations have been provided in the class MutableObjectListOps:
public static ObjectList mutableToImmutable (MutableObjectList L)
Returns an immutable list with the same elements as L. (They are shared with L.)

public static MutableObjectList immutableToMutable (ObjectList L)
Returns a mutable list with the same elements as L. (They are shared with L.)
• Introduce any auxiliary methods that you find helpful.
• In many of the methods, you need to treat the case where elts is the empty list specially.
• Because elts is a circular list, it is tricky to define size(), clone(), and toList(). When traversing elts in these methods, you must be sure to include an appropriate stopping condition. If you neglect to do this, you will get an infinite recursion, and Symantec Cafe will crash. The best way to debug an infinite recursion is to insert lots of System.out.printlns in your code, and use these to pinpoint which part of your code is causing the infinite recursion.

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.