teaching machines

CS 245 Lecture 24 – Binary Search Trees

November 26, 2013 by Chris Johnson. Filed under cs245, fall 2013, lectures.

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

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