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

  1. 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?
  2. 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?
  3. 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?
  4. 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?
  5. 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

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *