teaching machines

CS 245 Lecture 25 – Binary Search Tree Add, Traverse

December 3, 2013 by Chris Johnson. Filed under cs245, fall 2013, lectures.

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