Lab 07: BSTMap
after lab 4, a person who's doing this course on their own will continue with lab 7, since labs 5 and 6 involve working on Project 1
Last updated
after lab 4, a person who's doing this course on their own will continue with lab 7, since labs 5 and 6 involve working on Project 1
Last updated
Prerequisites to running the code.
Instructions: https://fa22.datastructur.es/materials/lab/lab07/
Solution: https://github.com/tomthestrom/cs61b/tree/master/lab07
The title says it all, I implemented a BSTMap in line with the specs and conventions - for every node X in the tree the following was true:
every key in the left subtree was less than X's key
every key in the right subtree was greater than X's key
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
.
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. We will not test the result of this method, but you will find this helpful for testing your implementation!
In your implementation you should assume that generic keys K
in BSTMap<K,V>
extend Comparable.
The BSTMap
is made of BSTNode
instances that store key
, value
pairs. BSTNode
is a nested class of BSTMap
. Since the key
of BSTNode
is a Comparable
, I used its compareTo method to determine where it belongs within the tree.
import java.util.Iterator;
import java.util.Set;
/**
* Implements a BSTMap as specified by MAP61B interface
* Core data structure is a binary search tree
*/
public class BSTMap<
Insert random speed test - my implementation of BSTMap holds up pretty well against Java's built-in data structures.
Insert in order test - my implementation is significantly slower than Java's built-in data structures and results in a stackoverflow at 50 000 inserts, I suppose the issue is with the fact that the tree is not self-balancing, so in case every new key is larger than the previous one, the tree is spindly and not a tree, but a linked list instead.
Please enter desired length of each string: 128
Enter # strings to insert into the maps: 1000
class bstmap.ULLMap: 0.01 sec
class bstmap.BSTMap: 0.00 sec
Java's Built-in TreeMap: 0.00 sec
Java's Built-in HashMap: 0.00 sec
Enter # strings to insert into the maps: 100000
--Stack Overflow -- couldn't add 100000 strings of length 128.
class bstmap.BSTMap: 0.20 sec
Java's Built-in TreeMap: 0.16 sec
Java's Built-in HashMap: 0.13 sec
Enter # strings to insert into the maps: 1000000
--Stack Overflow -- couldn't add 1000000 strings of length 128.
class bstmap.BSTMap: 2.00 sec
Java's Built-in TreeMap: 1.97 sec
Java's Built-in HashMap: 1.49 sec
Enter # strings to insert into the maps: 10000000
--Stack Overflow -- couldn't add 10000000 strings of length 128.
class bstmap.BSTMap: 26.70 sec
Java's Built-in TreeMap: 23.35 sec
Java's Built-in HashMap: 15.26 sec
Enter # strings to insert into the maps: 1000
class bstmap.ULLMap: 0.02 sec
class bstmap.BSTMap: 0.01 sec
Java's Built-in TreeMap: 0.00 sec
Java's Built-in HashMap: 0.00 sec
Enter # strings to insert into the maps: 10000
class bstmap.ULLMap: 0.76 sec
class bstmap.BSTMap: 0.80 sec
Java's Built-in TreeMap: 0.00 sec
Java's Built-in HashMap: 0.00 sec
Enter # strings to insert into the maps: 20000
class bstmap.ULLMap: 3.21 sec
class bstmap.BSTMap: 2.28 sec
Java's Built-in TreeMap: 0.01 sec
Java's Built-in HashMap: 0.00 sec
Enter # strings to insert into the maps: 50000
--Stack Overflow -- couldn't add 50000 strings.
--Stack Overflow -- couldn't add 50000 strings.
Java's Built-in TreeMap: 0.01 sec
Java's Built-in HashMap: 0.02 sec