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

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 `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`

^{2}).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.