In your introductory course you used a Python dictionary. A dictionary stores key–value pairs: you look up a key, such as a word, and get back the value stored with it, such as how many times that word appeared. The general name for this structure is an associative array, because it associates each key with a value. In Java it is called a map, and this week you will build one.

In lecture, each node of the binary search tree stored a single key. Today each node will also store a value, so the tree holds ⟨key, value⟩ pairs. The tree is still ordered by key, so lecture's insert, search, and traversals work just as before: they find the right node by its key, then use the value stored beside it.

Python dictionaryOur Java map (BSTMap)
counts = {}BSTMap<String, Integer> counts = new BSTMap<String, Integer>();
counts["the"] = 5counts.put("the", 5);
counts.get("the")counts.get("the") (null if "the" is not a key)
"the" in countscounts.containsKey("the")
len(counts)counts.size()
sorted(counts.keys())counts.keySet() (already in sorted order: it's a search tree)

In this lab and in Project 06, the keys are always words (String) and the values are always whole numbers (Integer): a BSTMap<String, Integer>. In the project, each word's value is how many times it appears in a text.

Setup

Create Projects/Project06 in your personal Google Drive folder and download the three files below. BSTMap.java is the class you will complete. It already has the Node class, the fields, and a placeholder for every method.

Download now:

Keep the field names in BSTMap.java (root, and key, value, left, right in Node). The tester and the display look inside your tree through those names.

Task 1 — Meet BSTMap READ

Open BSTMap.java next to your lecture notes. It is lecture's BST class with three changes: each node holds a value as well as a key, the map counts its keys in size, and keys are compared with compareTo instead of < and ==.

In lectureSlidesIn BSTMapTask
public class Node: int key; Node left, right;L23 6–12private class Node: K key; V value; Node left; Node right; (provided). In this lab K is String and V is Integer1
Node root;L23 13Node root; and int size; (provided)1
key < root.keyL23 34–39key.compareTo(cur.key) < 02
key > root.keyL23 34–39key.compareTo(cur.key) > 02
root.key == keyL23 90key.compareTo(cur.key) == 02
insert(key), the driverL23 20put(key, value) (provided)2
insert_Recursive(root, key)L23 20–47insert(cur, key, value)2
search_Recursive(root, key)L23 88–92find(cur, key)2
search(key), returns true or falseL23 85–87containsKey(key); and get(key), which returns the value4
(not in lecture)size(), clear()4
in-order traversalL24 4keySet(), values()5
height of the root (counts edges)L22 4, 44–45maxDepth() (counts levels: height + 1)6
minValue, deleteKey, delete_RecursiveL24 54–111remove(key)Project 06

One name changes everywhere: lecture's recursive methods call their node parameter root. Ours call it cur (the current node), because the class already has a field named root, and two different things with the same name is a classic source of bugs. Wherever lecture code says root inside a recursive method, read cur.

Every method you write starts with a throw line, such as throw new UnsupportedOperationException("get is not written yet (Task 4)");. It is a placeholder: it lets the file compile and tells the tester the method isn't written yet. Delete that line when you write the method.

Compile and run the tester now. Every section after Task 1 should say SKIP.

javac *.java
java Lab06Tester

Task 2 — put: search, then insert REUSE

A map differs from lecture's tree in one way. When a key is already there, put replaces its value instead of ignoring it, and returns the old value. Read the provided put: it first searches for the key with find. If find returns a node, put replaces that node's value. If not, put inserts a new node with insert, exactly as lecture's insert does, and adds one to size.

root = insert(root, key, value);    // the same line as lecture's insert driver

Write the two recursive methods put uses. Each is a lecture method with a few words changed.

2a. find: lecture's search_Recursive (L23, slides 88–92)

// Lecture 23, slide 92
private Node search_Recursive(Node root, int key) {
    // Base Cases: root is null or key is present at root
    if (root==null || root.key==key)
        return root;
    // val is greater than root's key
    if (root.key > key)
        return search_Recursive(root.left, key);
    // val is less than root's key
    return search_Recursive(root.right, key);
}
LectureBSTMap's find
search_Recursive(Node root, int key)find(Node cur, K key): write cur wherever lecture writes root
root.key==keykey.compareTo(cur.key) == 0
root.key > key (the node's key is bigger)key.compareTo(cur.key) < 0 (our key is smaller). Careful: lecture puts the node's key first, and we put our key first, so the sign flips.
search_Recursive(root.left, key)find(cur.left, key), and the same on the right

Lecture's first line works for us too: Java checks cur == null first and stops there if it's true, so compareTo is never called on a missing node.

2b. insert: lecture's insert_Recursive (L23, slides 20–47)

// Lecture 23, slide 47
private Node insert_Recursive(Node root, int key) {
    //tree is empty
    if (root == null) {
        return new Node(key);
    }
    //traverse the tree
    if (key < root.key) //insert in the left subtree
        root.left = insert_Recursive(root.left, key);
    else if (key > root.key) //insert in the right subtree
        root.right = insert_Recursive(root.right, key);
    // return pointer
    return root;
}
LectureBSTMap's insert
insert_Recursive(Node root, int key)insert(Node cur, K key, V value): write cur wherever lecture writes root
new Node(key)new Node(key, value)
key < root.key and key > root.keykey.compareTo(cur.key) < 0 and key.compareTo(cur.key) > 0 (same order, so no sign flip here)
insert_Recursive(root.left, key)insert(cur.left, key, value), and the same on the right
no case for an equal key (a duplicate is ignored)the same: put already handled an equal key before calling insert

Lecture's driver, root = insert_Recursive(root, key); on slide 20, is the line root = insert(root, key, value); in the provided put. To see insert run step by step, lecture traces inserting 15 on slides 41–56 and 17 on slides 57–81.

Ask Yourself — why reassign the link?

  1. insert writes cur.left = insert(cur.left, key, value);, not just insert(cur.left, key, value);. Trace putting "ant" into a tree that holds only "dog". What does the call return, and where would the new node go without the assignment?
  2. For a node that already has a left child, the call returns that same child. Why is it safe to assign it back?
  3. Why does put search before it inserts? What would happen to size if it inserted first?

Copy, paste, and complete: Paste this test into a new public static void main(String[] args) at the end of BSTMap.java, and complete the TODOs. System.out.print(map) uses the provided toString, which prints the keys level by level.

// Task 2: Paste INSIDE a main method at the end of BSTMap.java.
BSTMap<String, Integer> map = new BSTMap<String, Integer>();
map.put("dog", 15);
map.put("bee", 8);
map.put("fox", 17);
System.out.print(map);   // expected:  level 0: dog   then  level 1: bee fox
System.out.println("put(\"ant\", 3) adds a NEW word, so there is no old value to return.");
System.out.println("    expected null, got " + map.put("ant", 3));
System.out.println("put(\"bee\", 80) replaces bee's value, so it returns the OLD value, 8.");
System.out.println("    expected 8, got " + map.put("bee", 80));
// TODO: Put "cat" (10) and "eel" (16), then print the map. Draw the tree first:
//       on which level is each word, and is it a left or a right child?
// TODO: Put "dog" again with a new value. Print what put returns, and print
//       the map to check that no new node was added.

Run javac *.java and java BSTMap, then java Lab06Tester. The Task 2 section should pass.

Task 3 — Watch the tree grow READ AND EXPERIMENT

Download now:

BSTDisplay draws your tree in a window, one row per level, with the level numbers on the left and the number of nodes in each level on the right. After each put, it outlines the path from the root to the new key. You don't need to read BSTDisplay.java. BSTDemo uses your put to build two trees, one step each time you press Enter.

javac *.java
java BSTDemo
  1. Lecture's tree, in words: dog, bee, fox, ant, cat, eel, gnu. This is the tree of 15, 8, 17, 3, 10, 16, 20 from L22, slides 21–39. Before each Enter, say where the word will go. The outlined path is the comparisons put made on the way down.
  2. The same seven words in alphabetical order: ant, bee, cat, dog, eel, fox, gnu. Predict the shape before you press Enter. Compare it with lecture's "Is this a binary search tree?" example (L22, slides 41–45): the same chain, going the other way, where search becomes O(n).

Ask Yourself — shape decides speed

  1. How many nodes does a search visit to find "gnu" in the first tree? In the second? Both trees hold the same 7 words.
  2. Lecture asked you to draw the 5 possible shapes for the keys 1, 2, 3 (L22, slides 65–66). Which insertion order gives each shape? Which orders give the balanced one?
  3. A book is not written in alphabetical order. Would you expect the words of a book to build a tree more like the first one or the second?

Task 4 — get, containsKey, size, and clear REUSE

These four are short, because find does the work.

  • containsKey(K key): lecture's search driver (L23, slides 85–87) with a new name. Call find(root, key) and return true if it found a node.
  • get(K key): the same driver, but it returns the found node's value instead of true, and null instead of false.
  • size(): return the field. put already keeps it up to date.
  • clear(): set root to null and size to 0. As lecture said about deleting a node, Java reclaims nodes that nothing refers to any more.

Add expected-versus-got lines to your main: get a key that is present, a key that is missing, and a key on an empty map. Then run the tester; the Task 4 section should pass.

Task 5 — keySet and values, in sorted order DESIGN

Lecture 24 (slide 4) traced four orders through its tree of 15, 8, 17, 3, 16, 20. In-order (left subtree, node, right subtree) visits the keys from smallest to largest:

TraversalLecture's tree
Preorder (node, left, right)15, 8, 3, 17, 16, 20
In-order (left, node, right)3, 8, 15, 16, 17, 20
Postorder (left, right, node)3, 8, 16, 20, 17, 15
Breadth first (level by level)15, 8, 17, 3, 16, 20

keySet() returns an ArrayList of every key, in sorted order. Use a driver and a recursive method, the same pattern as lecture's insert and search drivers:

public ArrayList<K> keySet() {
    ArrayList<K> keys = new ArrayList<K>();
    keySet(root, keys);      // the recursive method fills the list
    return keys;
}

private void keySet(Node cur, ArrayList<K> keys) {
    // TODO: if cur is null, return.
    //       Visit the left subtree, add cur.key, visit the right subtree.
}

For our word version of lecture's tree, keySet gives [ant, bee, cat, dog, eel, fox, gnu]. Write values() the same way, adding cur.value; for that tree it gives [3, 8, 10, 15, 16, 17, 20], lecture's numbers back in order. Because both visit the nodes in the same order, values().get(i) is the value for keySet().get(i).

Download now: two small word files. tiny.txt is the 60-word opening of A Tale of Two Cities. sorted.txt holds the same 20 different words, once each, in alphabetical order.

java BSTDemo tiny.txt

BSTDemo counts the words with your put and get, then lists each word and its count using your keySet and values. Before you run it, predict: which words appear more than once, and which word comes first in the list?

Task 6 — maxDepth: how many levels? CONNECT

A full binary tree drawn in levels 0, 1, 2, 3, holding 1, 2, 4, and 8 nodes

maxDepth() returns the number of levels in the tree: the most nodes get may have to look at to find one key. The part of the tree in the picture has four levels, 0 to 3, so its maxDepth is 4. Lecture measured trees by their height, which counts edges instead of nodes (L22, slide 4: "What's the height of the root? 4" for a tree with 5 levels), so the height of the tree in the picture is 3. Lecture also showed that search time is the height of the tree (L22, slides 44–45), which is why we measure it. The two always differ by one:

TreeLecture's height (edges)maxDepth (levels)
emptynone0
one node01
lecture's 7-node tree (dog at the root)23
the seven words in alphabetical order67

Write it with a driver and a recursive method. An empty subtree has 0 levels. A node's subtree has 1 level for the node itself, plus the levels of its deeper child. Math.max(a, b) returns the larger of two ints.

Then compare the two word files. They hold the same 20 different words:

java BSTDemo tiny.txt
java BSTDemo sorted.txt

Ask Yourself — the worst case

  1. How many levels does each tree have? Count the nodes in each level of the window. How do they compare with the 1, 2, 4, 8 of a full tree?
  2. How many nodes would get look at, at most, to find a word in each tree? Which tree behaves like a linked list?
  3. A full tree with 20 levels could hold about a million keys. How many keys does the sorted tree hold in its 20 levels?

Run the basic checks

javac *.java
java Lab06Tester

Lab06Tester runs every check, keeps going after a failure, and ends with a summary. Each line says what the tester did and what should happen, for example put("cat", 99): cat is already in the map, so put returns cat's OLD value, 10. When a check fails, it shows what the answer should be and what yours gave. Its sections follow the tasks:

SectionWhat it checks
Task 1: the provided BSTMapthe tester can find root and look inside your tree
Task 2: putdog, bee, fox, ant, cat, eel, gnu give lecture's tree, level by level; put's return values; replacing a value adds no node; the same word in a different String object; alphabetical order makes a chain; 300 random keys stay in search-tree order
Task 4: get, containsKey, size, clearpresent and missing keys, an empty map, size after replacing, and using the map again after clear
Task 5: keySet and valuesalphabetical order, values lined up with their keys, word counts
Task 6: maxDepth0, 1, 3, and 7 levels, and a random tree

Lab checkpoint

The checkpoint comes after Task 4: show a TA or instructor your Lab06Tester summary with the Task 2 and Task 4 sections passing, and the two trees from java BSTDemo. Tasks 5 and 6 are short and use the same recursion. Finish them after the checkpoint, in lab or on your own, before you start Project 06; the project uses keySet and values, and its checklist asks for every Lab06Tester section to pass.

This is a required graded lab. After your checkpoint you may work on the project until the individual closed-book quiz; remain for the quiz. Make sure your code is in Projects/Project06 before the lab ends.

Begin Project 06 →