| Pledge of Honor |
| 1 (30 pts) | 2a (10 pts) | 2b (15 pts) | 2c (10 pts) | 3 (35 pts) | Total (100) | |||
Consider the following binary tree:
A
|_B
| |_D
| | |_[]
| | |_[]
| |_E
| |_[]
| |_[]
|_C
|_F
| |_[]
| |_[]
|_G
|_[]
|_[]
We can put this tree into an array as such: [A, B, C, D, E, F, G]
This ordering technique has the following interesting properties:
Given an index of the parent (root) node, idxRoot,
- the index of the left subtree is idxLeft = 2*idxRoot + 1 (e.g. A->B, B->D, C->F)
- the index of the right subtree is idxRight = 2*idxRoot + 2 (e.g. A->C, B->E, C->G)
Convince yourself this is true for any element of the binary tree, no matter how big it is.
If the tree is not "full" then we simply leave nulls in the array:
becomesA |_B | |_[] | |_E | |_[] | |_[] |_C |_F | |_[] | |_[] |_[]
[A, B, C, null, E, F,null]
The array must therefore be sized for the worst case scenario: Given the maximum height of the binary tree, hMax, then the size of the array is (int)Math.pow(2, hMax)-1
Write an IVisitor called BRS2Array that returns a new array of Objects filled with the elements of the host BiTree where the elements are located in the above ordering scheme.
Notes:
The package java.util contains an interface named Iterator. The reason behind defining Iterator is to create a standard interface for objects whose job it is to enumerate the contents of a container, such as an IDictionary. An Iterator has three methods.
Why is an iterator an object? One reason is that it must maintain state about its progress. Specifically, it must remember which elements of the container have been returned by next() and which have not.
For this question, we ask you to write most of a class called IntegerBSTIterator that implements the Iterator interface. This class and its methods may assume that they are enumerating a binary search tree (BST) on Integer objects. The twist is that you may only use the BSTSplay visitor (from Lecture 32) and the public methods of the BiTree class in your implementation. You may assume that IntegerBSTIterator will be an inner class of DictBT (see lecture 25) and has access to the BST from the enclosing class. Here is the stub code for IntegerBSTIterator inside of the modified DictBT.
/**
* See lecture 25/code.
*/
public class DictBT implements IDictionary {
/*
* A binary tree of DictionaryPairs ordered by key
*/
private BiTree _bt = new BiTree();
/*
* A trivial comparator for use by the binary search tree (BST)
* visitors
*/
private Comparator _comparator = new Comparator() {
public int compare(Object x, Object y) {
return ((Comparable)x).compareTo(y);
}
};
/**
* For students to complete.
*/
private class IntegerBSTIterator implements java.util.Iterator {
/**
* Students to add appropriate fields, constructors and additional support methods.
*/
public boolean hasNext() {
return true; // NOT REQUIRED TO IMPLEMENT
}
public Object next() {
return null; // STUDENT TO COMPLETE
}
public void remove() {
// STUDENT TO COMPLETE
}
}
public Iterator bstIterator() {
return new IntegerBSTIterator(...); // NOT REQUIRED TO COMPLETE
}
/**
* The rest of the code for BiTree is the same as before and is
* elided to keep the text short.
*/
} a) Define the field(s) and the constructor for IntegerBSTIterator. (You must only define those fields that will be used by the constructor, next() and remove().) Provide a brief, one sentence comment describing each field's purpose. b) Write the method next(). This method should return the elements of the BST in order. Remember that you may only use BSTSplay and the methods of class BiTree in your solution. What is this method's worst case execution cost? Write your answer using ``Big-Oh'' notation. c) Write the method remove(). Note that if next() has not yet been called, this method should throw an IllegalStateException. For full credit, your solution's execution cost should be O(1).
Hint: Sometimes it is useful to perform BSTSplay on a BST specifying a key that is not necessarily expected to exist in the tree. For example, specifying the minimum possible integer as the key would have the effect of moving the smallest key that does exist in the BST to the root. This observation has application to both the constructor and the method next().
Suppose we define a number as a sequence of one or more digits, where digit is one of '0', '1', ...'9'. We can express such a definition in the following form (called "regular definition").
From the above definition, 0123, 123, 4 are numbers. Review the definition of the abstract token AToken and its concrete subclasses in lecture 30 and lab #11 in week #12. For all practical purpose, the concrete IntToken class can be used to represent the numbers defined in the above.
One common technique for implementing a lexical analyzer to recognize the above numbers is to realize it as finite state machine with the following state transition diagram.
Use the state design pattern to implement the above finite state machine as a class called Tokenizer Tokenizer has a Reader to scan the input and should have one public method
AToken getNextToken()
that is to return an concrete IntToken if the current input is a number and a NullToken otherwise.
You may define the states as anonymous inner classes of Tokenizer. Defining the states as external classes will require some form of communication between Tokenizer, the context, and its states.