In this lab, you'll create **BSTMap**, a BST-based implementation of the Map61B interface, which represents a basic map.

After you've completed your implementation, you'll compare the performance of your implementation to a list-based Map implementation `ULLMap`

as well as the built-in Java `TreeMap`

class (which also uses a BST).

# 1: BSTMap

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`

. Your implementation is required to implement all of the methods given in **Map61B** *except* for `remove`

, `iterator`

and `keyset`

. For these methods you should throw an `UnsupportedOperationException`

.

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

extend Comparable`public class BSTMap<K extends Comparable<K>, V> implements Map61B<K, V>`

.

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.- Lecture 21 slides.

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 find this helpful for testing your implementation!

You can test your implementation using the `TestBSTMap`

class in the `lab8tester`

package.

# 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, you can run the tests in IntelliJ.

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 `<String, Integer>`

key-value pairs are inserted in lexicographically-increasing order. If you observed anything interesting (hopefully you did), you should discuss it with your fellow students and/or TA.

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 week.

# 3: Optional Exercises

This will not be graded.

Implement the methods `iterator()`

, `keySet()`

, `remove(K key)`

, and `remove(K key, V value)`

, in your **BSTMap** class. Implementing `remove()`

is fairly challenging. For an extra challenge implement `keySet()`

and `iterator`

without using a second instance variable to store the set of keys.

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.

# 4: Lab Debrief and Submission

At the end of lab, your TA will go over the reference solution. This will be helpful if you haven't finished the lab, since we don't want you to be stuck working on lab too much outside of lab. (This is also an incentive for you to go to lab!)

To submit, make sure your BSTMap.java is in your lab8 package and submit through Gradescope.

# 5: Optional Asymptotics Problems

Given `B`

, a **BSTMap** with `N`

key-value pairs, and `(K, V)`

, a random key-value pair, answer the following questions.

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).

For questions 1-7, state whether the statement is true or false. For question 8, give a runtime bound.

`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); }`