teaching machines

CS 245 Lecture 22 – Stacks and Binary Search Tree

April 17, 2014 by . Filed under cs245, lectures, spring 2014.

Agenda

TODO

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 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 would you use to facilitate this interaction?
  3. You have the finishing times from a large marathon. People are asking your application who the nth-place finisher was. What data structure would you use to facilitate this interaction?
  4. 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 would you use to achieve this effect?

Program This

You’ve got an expression in “postfix” form:

Devise a plan to parse and evaluate such expressions.

Code

BinarySearchTree.java

package lecture22;

public class BinarySearchTree<K, V> {
  private Node<K, V> root;
  private int size;

  public BinarySearchTree() {
    root = null;
    size = 0;
  }

  public int size() {
    return size(root);
  }

  private int size(Node<K, V> root) {
    if (root == null) {
      return 0;
    } else {
      return 1 + size(root.left) + size(root.right);
    }
  }

  public void add(K key,
                  V value) {
    Node<K, V> nodeToAdd = new Node<K, V>(key, value, null, null);
    if (root == null) {
      root = nodeToAdd;
    } else {
      root.add(nodeToAdd);
    }
    ++size;
  }

  public static class Node<K, V> {
    private K key;
    private V value;
    private Node<K, V> left;
    private 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 void add(Node nodeToAdd) {
      
    }
  }
}

Haiku

Some race to the top
Some wander left, back, then right
Who wins on a tree?