CS 245 Lecture 24 – Binary Search Trees
Agenda
- what ?s
- design this
- isKitten
- binary search tree vs. sorted array
- implementing a BST
- Node
- isEmpty
- size
- get
- add
- delete
- a problem with BSTs: balance
Design This
- You are building a 2-D memory/matching game. When the user clicks on the screen, the clicked-upon card is flipped. What data structure(s) would you use to facilitate this interaction?
- You are writing an application that provides a command-line interface to applications on the computer. When the user types “ls”, the application stored at /usr/bin/ls is run. When the user types “octave”, the application stored at /usr/local/bin/octave is run. What data structure(s) would you use to facilitate this interaction?
- You are designing a model for a web page. Web pages contain a head and a body. In the body, you may have many div sections, which may contain further div sections, which may contain further div sections, etc. What data structure(s) would you use to support this model?
- You have the finishing times from a large marathon. People are asking your application who the nth-place finisher was. What data structure(s) would you use to facilitate this interaction?
- You are writing a web browser and want to know if a URL has been visited before. If so, you can color it differently. What data structure(s) would you use to achieve this effect?
Code
HashEg.java
package lecture24;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;
public class HashEg {
public static void main(String[] args) {
HashMap<String, String> symbolsToNames = new HashMap<String, String>();
symbolsToNames.put("U", "Uranium");
symbolsToNames.put("Ti", "Titanium");
symbolsToNames.put("Unun", "Pentium");
for (Entry<String, String> keyValuePair : symbolsToNames.entrySet()) {
System.out.println(keyValuePair.getKey() + " -> " + keyValuePair.getValue());
}
// HashSet<E>
}
}
BinarySearchTree.java
package lecture24;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.NoSuchElementException;
import java.util.Scanner;
public class BinarySearchTree<K extends Comparable<K>, V> {
private Node<K, V> root;
public BinarySearchTree() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
public int size() {
return size(root);
}
private int size(Node<K, V> startingNode) {
// Base case: when startingNode is null
if (startingNode == null) {
return 0;
}
// General case: when startingNode is not null
else {
return 1 + size(startingNode.left) + size(startingNode.right);
}
}
public V get(K key) {
return get(key, root);
}
private V get(K key, Node<K, V> startingNode) {
if (startingNode == null) {
throw new NoSuchElementException("No value for key " + key);
} else {
int order = key.compareTo(startingNode.key);
if (order == 0) {
return startingNode.value;
} else if (order < 0) {
return get(key, startingNode.left);
} else {
return get(key, startingNode.right);
}
}
}
private static class Node<K, V> {
K key;
V value;
Node<K, V> left;
Node<K, V> right;
}
public static void main(String[] args) throws FileNotFoundException {
Scanner in = new Scanner(new File("/Users/johnch/checkouts/teaching/cs245/history/2013C/here.txt"));
BinarySearchTree<String, String> idToName = new BinarySearchTree<String, String>();
while (in.hasNextLine()) {
String line = in.nextLine();
String[] parts = line.split(",");
String firstName = parts[0].split(" ")[0];
String id = parts[1];
idToName.add(id, firstName);
}
in.close();
// System.out.print("ID: ");
// in = new Scanner(System.in);
// while (in.hasNext()) {
// String id = in.next();
// System.out.println(idToName.get(id));
// System.out.print("ID: ");
// }
}
}
Haiku
Trees have it easy
I have more than two paths
Good tangles with bad
I have more than two paths
Good tangles with bad