import java.util.ArrayList; /** * A map built on a binary search tree, following the BST from lecture. * * Lecture's tree stores one int key in each node. This tree stores a key AND * a value in each node, and the key can be any type that can compare itself * with compareTo, such as String or Integer. * * Every method below that you write starts with a "throw" line. It is a * placeholder: it lets this file compile and tells the tester the method is not * written yet. Delete that line when you write the method. */ public class BSTMap, V> implements MapSet { /** One node of the tree: lecture's Node, plus a value. */ private class Node { K key; V value; Node left; Node right; Node(K key, V value) { this.key = key; this.value = value; // left and right start as null } } private Node root; // null when the map is empty private int size; // the number of keys in the map public BSTMap() { root = null; size = 0; } // ------------------------------------------------------------------ // Task 2: put, using lecture's search and insert // ------------------------------------------------------------------ /** Stores value under key. Provided: read it, then write find and insert. */ public V put(K key, V value) { if (value == null) { return null; // a map never stores null } Node found = find(root, key); // lecture's search if (found != null) { // the key is already here: V old = found.value; // replace its value and found.value = value; // return the old one return old; } root = insert(root, key, value); // lecture's insert size++; return null; } /** Returns the node in this subtree that holds key, or null if there is none. */ private Node find(Node cur, K key) { // TODO Task 2: lecture's search_Recursive, comparing with compareTo. throw new UnsupportedOperationException("find is not written yet (Task 2)"); } /** Adds a new node for key below cur, and returns the root of this subtree. */ private Node insert(Node cur, K key, V value) { // TODO Task 2: lecture's insert_Recursive, comparing with compareTo. throw new UnsupportedOperationException("insert is not written yet (Task 2)"); } // ------------------------------------------------------------------ // Task 4: get, containsKey, size, clear // ------------------------------------------------------------------ public V get(K key) { // TODO Task 4 throw new UnsupportedOperationException("get is not written yet (Task 4)"); } public boolean containsKey(K key) { // TODO Task 4 throw new UnsupportedOperationException("containsKey is not written yet (Task 4)"); } public int size() { // TODO Task 4 throw new UnsupportedOperationException("size is not written yet (Task 4)"); } public void clear() { // TODO Task 4 throw new UnsupportedOperationException("clear is not written yet (Task 4)"); } // ------------------------------------------------------------------ // Task 5: keySet and values, in sorted order // ------------------------------------------------------------------ public ArrayList keySet() { // TODO Task 5 throw new UnsupportedOperationException("keySet is not written yet (Task 5)"); } public ArrayList values() { // TODO Task 5 throw new UnsupportedOperationException("values is not written yet (Task 5)"); } // ------------------------------------------------------------------ // Task 6: maxDepth // ------------------------------------------------------------------ public int maxDepth() { // TODO Task 6 throw new UnsupportedOperationException("maxDepth is not written yet (Task 6)"); } // ------------------------------------------------------------------ // Project 06: remove // ------------------------------------------------------------------ public V remove(K key) { throw new UnsupportedOperationException("remove is written in Project 06"); } // ------------------------------------------------------------------ // Provided: print the tree level by level, for your own tests // ------------------------------------------------------------------ /** Returns the keys level by level, for example "level 0: 15\nlevel 1: 8 17\n". */ public String toString() { if (root == null) { return "(empty tree)"; } String result = ""; int level = 0; String line = keysAtLevel(root, level); while (!line.isEmpty()) { result += "level " + level + ":" + line + "\n"; level++; line = keysAtLevel(root, level); } return result; } /** The keys exactly `level` steps below cur, left to right. */ private String keysAtLevel(Node cur, int level) { if (cur == null) { return ""; } if (level == 0) { return " " + cur.key; } return keysAtLevel(cur.left, level - 1) + keysAtLevel(cur.right, level - 1); } }