teaching machines

CS 245 Lecture 24 – Trees and Hello, Threads

April 24, 2014 by Chris Johnson. Filed under cs245, lectures, spring 2014.

Agenda

• what ?s
• think about this
• removing from a BST
• threads

TODO

• Read chapter 14 (Multithreading) through section 14.3 (Thread States). 1/4 sheet. (Probably the last.)

Think About This

• Watch Brian Harvey’s lecture.
• Write BinarySearchTree.insertKeysBetween:

  private void insertKeysBetween(K lo,
                                 K hi,
                                 ArrayList<K> tweeners,
                                 Node<K, V> root) {
    ...
  }

Code

BinarySearchTree.java

package lecture24;

import java.util.ArrayList;

public class BinarySearchTree<K extends Comparable<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 void traverse() {
    postOrderTraverse(root);
  }

  private void traverse(Node<K, V> root) {
    if (root == null) {
      return;
    }

    traverse(root.left);
    System.out.println(root.key + " -> " + root.value);
    traverse(root.right);
  }

  private void preOrderTraverse(Node<K, V> root) {
    if (root == null) {
      return;
    }

    System.out.println(root.key + " -> " + root.value);
    traverse(root.left);
    traverse(root.right);
  }

  private void postOrderTraverse(Node<K, V> root) {
    if (root == null) {
      return;
    }

    traverse(root.left);
    traverse(root.right);
    System.out.println(root.key + " -> " + root.value);
  }

  public ArrayList<K> getKeysBetween(K lo,
                                     K hi) {
    ArrayList<K> tweeners = new ArrayList<>();
    insertKeysBetween(lo, hi, tweeners, root);
    return tweeners;
  }

  private void insertKeysBetween(K lo,
                                 K hi,
                                 ArrayList<K> tweeners,
                                 Node<K, V> root) {
    
    if (root == null) {
      return;
    }
   
    if (lo.compareTo(root.key) <= 0 && root.key.compareTo(hi) <= 0) {
      // add root.key to list
      insertKeysBetween(lo, hi, tweeners, root.left);
      tweeners.add(root.key);
      insertKeysBetween(lo, hi, tweeners, root.right);
    } else if (root.key.compareTo(lo) < 0) {
      insertKeysBetween(lo, hi, tweeners, root.right);
    } else if (hi.compareTo(root.key) < 0) {
      insertKeysBetween(lo, hi, tweeners, root.left);
    }
    
  }

  private static class Node<K extends Comparable<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<K, V> nodeToAdd) {
      int order = key.compareTo(nodeToAdd.key);
      // if order < 0, then nodeToAdd > current
      // if order > 0, then nodeToAdd < current
      // if order == 0, then nodeToAdd == current

      // Someone is updating an existing node.
      if (order == 0) {
        value = nodeToAdd.value;
      } else if (order < 0) {
        if (right == null) {
          right = nodeToAdd;
        } else {
          right.add(nodeToAdd);
        }
      } else {
        if (left == null) {
          left = nodeToAdd;
        } else {
          left.add(nodeToAdd);
        }
      }
    }
  }
}

Harvey.java

package lecture24;

import java.util.ArrayList;

public class Harvey {
  public static void main(String[] args) {
    BinarySearchTree<Integer, Void> bst = new BinarySearchTree<>();
    int nums[] = {50, 17, 72, 12, 23, 54, 76, 9, 14, 19, 67};
    for (int num : nums) {
      bst.add(num, null);
    }
    
    ArrayList<Integer> tweeners = bst.getKeysBetween(20, 60);
    System.out.println(tweeners);
  }
}

Haiku