Implementing Stack Data Structure, Converting Doubly Linked List to Binary Search Tree, Exercise 12.

Variant of Stack Data Structure with MAX Primitive

1. [20%] Implement a variant of the stack data structure, so that on top of the three primitives, PUSH, POP, and TOP, there is now a new primitive, MAX.

• MAX(S): returns the maximum key currently in the stack S.

It is assumed that the data type of the keys supports comparisons (i.e., “?”). Other than that, we do not know anything about the data type of the keys. Your solution is evaluated by how competitive its performance (running time) is.

2. [20%] Design a linear-time algorithm that converts a sorted, doubly linked list into a balanced binary search tree. The only thing we know about the data type of the keys is that they are comparable (i.e., “?”). You may further assume that the keys in the linked list are distinct. It is okay for the algorithm to be destructive (meaning it modifies the original linked list or even distroys it). It is also okay to use additional space (so long as the amount is reasonable).

3. [20%] Exercise 12.3-5 on page 299 of CLRS.

4. [40%] Implement a red-black tree class in Java.

(a) The keys are of type int.

(b) Your class shall be named as follows: 

ca.ucalgary.cpsc331.RedBlackTree

(c) Your class shall implement the following Java interface:
package ca.ucalgary.cpsc331;
public interface Dictionary {
boolean empty();
void insert(int key);
void delete(int key);
boolean member(int key);
}

(d) Your implementation shall raise an appropriate run-time exception when the user attempts to delete from an empty tree. 

 

(e) The class shall provide a constructor that does not take any arguments. This constructor initializes the tree to an empty one.

(f) The class shall override the toString() method. Your implementation of to String() shall return a String in the following format:
• The string consists of as many “lines” as there are internal nodes (i.e., a node that is not a leaf/NIL). If there are ten internal nodes, then there are ten lines. An empty tree is represented by an empty string.
• Each “line” is terminated by a newline character. No line shall contain leading or trailing whitespaces.
• Each line is a representation of an internal node. The order of the lines corresponds to a preorder tree walk.
• A line has the following format:

address:color:key
– key is the key stored in the node.
– color is either red or black, representing the color of the node.
– address is the tree address of the node, a concept explained below.
• The tree address of an internal node is defined inductively:
– The tree address of the root is the string "*".
– If the tree address of an internal node n is the string s, then the tree addresses of the left and right children are respectively s + "L" and s + "R". Here, + is the string concatenation operator.
For example, the left child of the right child of the root has the following tree address:
*RL