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

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

BSTMap - Instructions

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.

Implementation

About

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.

Code

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<K extends Comparable, V> implements Map61B<K, V> {
    /**
     * The root of the tree
     */
    private BSTNode<K, V> root;

    /**
     * The nr of nodes in the tree
     */
    private int size;

    /**
     * Represents a node within the BST
     */
    private static class BSTNode<K extends Comparable, V> {
        /**
         * The key of the node
         */
        public K key;
        /**
         * The value of the node
         */
        public V value;

        /**
         * Reference to the left child
         */
        public BSTNode<K, V> left;
        /**
         * Reference to the right child
         */
        public BSTNode<K, V> right;

        public BSTNode(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    /**
     * Removes all items from the BST
     */
    @Override
    public void clear() {
        root = null;
        size = 0;
    }

    /**
     * Returns true if the BST contains the requested key
     */
    @Override
    public boolean containsKey(K key) {
        return containsKeyHelper(root, key);
    }

    /**
     * Recursively traverses the tree in search of the requested key, returns
     * true if found, false otherwise
     */
    private boolean containsKeyHelper(BSTNode node, K key) {
        if (node == null) {
            return false;
        }

        if (node.key.compareTo(key) == 0) {
            return true;
        }

        boolean searchLeft = node.key.compareTo(key) > 0;

        if (searchLeft) {
            return containsKeyHelper(node.left, key);
        } else {
            return containsKeyHelper(node.right, key);
        }
    }

    /**
     * Returns the value to which the specified key is mapped, or null if this
     * map contains no mapping for the key.
     */
    @Override
    public V get(K key) {
        return getHelper(root, key);
    }

    /**
     * Recursively traverses the tree in search of the requested key, returns its value
     */
    private V getHelper(BSTNode node, K key) {
        if (node == null) {
            return null;
        }

        if (node.key.compareTo(key) == 0) {
            return (V) node.value;
        }

        boolean searchLeft = node.key.compareTo(key) > 0;

        if (searchLeft) {
            return getHelper(node.left, key);
        } else {
            return getHelper(node.right, key);
        }

    }

    /**
     * Returns the nr. of stored items
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * Stores a key value pair
     */
    @Override
    public void put(K key, V value) {
        root = putHelper(root, key, value);
    }

    /**
     * Recursively traverses the nodes comparing the keys to find out where to insert the key, value pair
     */
    private BSTNode<K, V> putHelper(BSTNode<K, V> node, K key, V value) {
        if (node == null) {
            size++;
            return new BSTNode<>(key, value);
        }

        //in case the key already exists, we just assing a new value
        boolean insertHere = node.key.compareTo(key) == 0;

        if (insertHere) {
           node.value = value;
           return node;
        }

        boolean insertLeft = node.key.compareTo(key) > 0;

        if (insertLeft) {
            node.left = putHelper(node.left, key, value);
        } else {
            node.right = putHelper(node.right, key, value);
        }

        return node;
    }

    /**
     * Prints out the BSTMap in order of increasing Key
     */
    public void printInOrder() {
        printInOrderHelper(root);
        System.out.println();
    }

    /**
     * Recursively traverses the tree and prints its items
     * visiting the smallest (left) values first before printing the current value and
     * visitng the largerst (right) values
     */
    private void printInOrderHelper(BSTNode<K, V> node) {
        if (node == null) {
            return;
        }
        printInOrderHelper(node.left);
        System.out.print(node.key);
        printInOrderHelper(node.right);
    }

    /*
     * Unsupported Methods:
     * keySet
     * remove(key)
     * remove(key, value)
     * iterator()
     */

    @Override
    public Set<K> keySet() {
        throw new UnsupportedOperationException();
    }

    @Override
    public V remove(K key) {
        throw new UnsupportedOperationException();
    }

    @Override
    public V remove(K key, V value) {
        throw new UnsupportedOperationException();
    }

    @Override
    public Iterator<K> iterator() {
        throw new UnsupportedOperationException();
    }
}

So ... How Fast Is It?

About

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.

InsertRandomSpeedTest:

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

InsertInOrderSpeedTest

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