CS 245 Lecture 25 – Binary Search Tree Add, Traverse
Agenda
- what ?s
- schedule
- homework (* this week, 1 next week, 1 during finals)
- last lab tomorrow
- final: Friday at 1 PM
- hw3 demo
- adding nodes to a BST
- iterating through a BST
- deleting nodes from a BST
Code
KeyValueVisitor.java
package lecture25;
public interface KeyValueVisitor<K, V> {
public void visit(K key, V value, int level);
}
BinarySearchTree.java
package lecture25;
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);
}
}
}
public void add(K key,
V value) {
root = subtreeByAdding(root, key, value);
}
private Node<K, V> subtreeByAdding(Node<K, V> startingNode,
K key,
V value) {
Node<K, V> subtreeRoot;
// We hit paydirt!
if (startingNode == null) {
subtreeRoot = new Node<K, V>(key, value, null, null);
}
// The subtree we're trying to insert into is non-empty. A couple
// of things may be true. The new item might belong in one of this
// node's subtrees. Or it may match the node itself.
else {
int order = key.compareTo(startingNode.key);
subtreeRoot = startingNode;
// Thing to insert appears left of pivot point! Blam!
if (order < 0) {
startingNode.left = subtreeByAdding(startingNode.left, key, value);
}
// Thing to insert appears right of pivot point! Whap!
else if (order > 0) {
startingNode.right = subtreeByAdding(startingNode.right, key, value);
}
// The keys are the same. Oh oh oh.
else {
startingNode.value = value;
}
}
return subtreeRoot;
}
public void traversePreorder(KeyValueVisitor<K, V> visitor) {
traversePreorder(root, visitor, 0);
}
private void traversePreorder(Node<K, V> startingNode, KeyValueVisitor<K, V> visitor, int level) {
if (startingNode != null) {
visitor.visit(startingNode.key, startingNode.value, level);
traversePreorder(startingNode.left, visitor, level + 1);
traversePreorder(startingNode.right, visitor, level + 1);
}
}
private static class Node<K, V> {
K key;
V value;
Node<K, V> left;
Node<K, V> right;
public Node(K key,
V value,
Node<K, V> left,
Node<K, V> right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
public static void main(String[] args) throws FileNotFoundException {
BinarySearchTree<Integer, String> tree = new BinarySearchTree<Integer, String>();
tree.add(50, "root");
tree.add(25, "l");
tree.add(75, "r");
tree.add(12, "ll");
tree.add(37, "lr");
tree.add(62, "rl");
tree.add(87, "rr");
tree.traversePreorder(new KeyValueVisitor<Integer, String>() {
@Override
public void visit(Integer key,
String value,
int level) {
System.out.println(getSpace(level) + key + " -> " + value);
}
});
}
private static String getSpace(int nspaces) {
String s = "";
for (int i = 0; i < nspaces; ++i) {
s += " ";
}
return s;
}
}
Haiku
trade offs
Add in constant time!*
That’s fast. We’re data structSURE!
*Search linearly.
Add in constant time!*
That’s fast. We’re data structSURE!
*Search linearly.