CS 245 Lecture 24 – Trees and Hello, Threads
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
Proposal checklist
□ level up □ save □ buy ring □ ask
If you lose, reset
□ level up □ save □ buy ring □ ask
If you lose, reset