Homework 6: Asymptotics and BSTs

For this installment of Awesome Asymptotics, you'll create BSTMap, a BST-based implementation of the Map61B interface from HW5.

After you've completed your implementation, you'll compare the performance of your implementation to the ULLMap from HW5 as well as the built-in Java TreeMap class (which also uses a BST). Then we'll close out with some practice problems with asymptotics.

1: BSTMap - Map61B Round Two!

Create a class BSTMap that implements the Map61B interface using a BST (Binary Search Tree) as its core data structure. You must do this in a file named BSTMap.java. Just as in HW5, your implementation is required to implement all of the methods given in Map61B except for remove and keyset.

In your implementation you should assume that generic keys K in BSTMap<K,V> extend Comparable.

The following resources might prove useful:

BST code from pages 109 and 111 of Data Structures Into Java, from our course references page.
Pages 396-405 from our optional Algorithms textbook.
BST code from our optional textbook.
ULLMap.java (provided), a working unordered linked list based Map61B implementation.

Your BSTMap should also add an additional method printInOrder() (not given in the Map61B interface) that prints out your BSTMap in order of increasing Key. You will this helpful for testing your implementation!

2: So... How Fast Is It?

There are two interactive speed tests provided in InsertRandomSpeedTest.java and InsertInOrderSpeedTest.java. Do not attempt to run these tests before you've completed BSTMap. Once you're ready, compile with javac oneOfTheTests.java and run with java oneOfTheTests.

The InsertRandomSpeedTest class performs tests on element-insertion speed of your BSTMap, ULLMap (provided), and Java's built-in TreeMap. It works by asking the user for an input size N, then generates N Strings of length 10 and inserts them into the maps as pairs.

Try it out and see how your data structure scales with N compared to the naive and industrial-strength implementations. Record your results in a file named speedTestResults.txt. There is no standard format required for your results, and there is no required number of data points.

Now try running InsertInOrderSpeedTest, which behaves similarly to InsertRandomSpeedTest, except this time the Strings in key-value pairs are inserted in lexicographically-increasing order. If you observed anything interesting (hopefully you did), then you should explain this interesting thing along with your results in speedTestResults.txt.

Extra: Modify the testing classes so that they also compare the performance of your class to the built-in HashMap class, which uses an alternate technique for implementing maps (called hashing) that we'll develop next Wednesday.

3 Asymptotics: Put On Your Thinking Cap

Given B, a BSTMap with N key-value pairs, and (K, V), a random key-value pair, answer the following 8 questions in a file named trueFalse.txt in the following format: the question number, followed by a space, followed by your one-letter answer (T/F), followed by a space and your justification. Note that question 8 is not true/false and the answer should be of the form O(...).

Formatting example of trueFalse.txt (not the right answers):

    1 T easy problem 
    ...
    7 O(...) By my advanced analysis...
    8 F because i'm a genius. 
    ...
    171 T horse
    172 F horse

Unless otherwise stated, "big-Oh" bounds (e.g. O(N)) and "big-Theta" bounds (e.g. Θ(N)) refer to the number of comparisons in the given method call(s).

Questions:

B.put(K, V) ∈ O(log(N)).
B.put(K, V) ∈ Θ(log(N)).
B.put(K, V) ∈ Θ(N).
B.put(K, V) ∈ O(N).
B.put(K, V) ∈ O(N²).
On average, the total number of comparisons to complete N random calls to B.put(K, V) followed by B.containsKey(K) ∈ ∼2(ln(N))
```
Note: We write g(N)~f(N) to represent that ~g(N)/f(N) -> 1 as N gets large.
```
For key C != K, running both B.containsKey(K) and B.containsKey(C) ∈ Ω(log(N)).
Let BSTMap b be comprised of a root Node (Key, Value pair) and two BSTMap subtrees called left and right. Further, assume the method numberOfNodes(BSTMap b) returns the number of nodes of a BSTMap rooted in b.root and has a running time of Θ(n), where n is the number of Nodes in the BSTMap rooted in b. What is the running time (in big O notation) of mystery(b, z) for some positive integer z? Give the tightest bound you can assuming b has N nodes. Your answer should not contain any unnecessary multiplicative constants or additive factors.
```
public Key mystery(BSTMap b, int z) {
    if (z > numberOfNodes(b) || z <= 0) 
        return null;
    if (numberOfNodes(b.left) == z-1)
        return b.root.key;
    else if (numberOfNodes(b.left) > z)
        return mystery(b.left, z); 
    else 
        return mystery(b.right, z-numberOfNodes(b.left) - 1);
}
```

4: Mehrheit Für Die Mitleid

Note: Only do this optional part if you've finished the rest of the homework. Don't waste your time trying to figure out remove() unless you're in it for the pride, in which case go crazy Simba.

Implement the methods remove(K key), remove(K key, V value), and keySet() in your BSTMap class.

For remove, you should return null if the argument key does not exist in the BSTMap. Otherwise, delete the key-value pair (key,value) and return value.