<![CDATA[
::::::::::::::
KeyValue.java
::::::::::::::
// Gary Yngve 10/30/2005
public class KeyValue {
private int key; // simple integer key to avoid the complexities
// of compareTo or a comparator
public Object value;
public KeyValue(int key, Object value) {
this.key = key;
this.value = value;
}
public int getKey() { // don't want other folks changing the key
return key;
}
public String toString() {
return "(" + key + "," + value + ")";
}
}
::::::::::::::
BinarySearchTree.java
::::::::::::::
// Gary Yngve 10/30/2005
public class BinarySearchTree {
// minimalistic TreeNode -- just left & right children -- no parent
private static class TreeNode {
KeyValue data;
TreeNode left;
TreeNode right;
TreeNode(KeyValue data) {
this(data,null,null);
}
TreeNode(KeyValue data, TreeNode left, TreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}
// can only return one thing, so we need to wrap the two things we want
// to return into a single class
private static class ReturnWrap {
KeyValue data;
TreeNode node;
ReturnWrap(KeyValue data, TreeNode node) {
this.data = data;
this.node = node;
}
}
private TreeNode root; // base of the whole tree -- the public methods
// call helper methods with root passed
private int size; // number of elements in the tree
public BinarySearchTree() {
root = null;
size = 0;
}
// pre: none
// post: returns value if the key is found, null otherwise
public Object get(int key) {
return get(root,key);
}
// pre: none (though null value highly discouraged)
// post: if key is found in tree, replaces old value with new value
// and returns old value
// if not found, adds to tree in proper place and returns null
public Object put(int key, Object value) {
ReturnWrap ret = put(root,new KeyValue(key,value));
root = ret.node;
return ret.data;
}
// pre: none
// post: if key is found in tree, removes that node.
// returns the value removed
public Object remove(int key) {
ReturnWrap ret = remove(root,key);
root = ret.node;
return ret.data;
}
public void printInfix() {
printInfix(root);
}
public int size() {
return size;
}
public boolean isEmpty() {
return size() == 0;
}
// pre: none
// post: returns value if the key is found, null otherwise
private Object get(TreeNode root, int key) {
if (root == null) // key not found
return null;
else if (key == root.data.getKey()) // key is here
return root.data.value;
else if (key < root.data.getKey()) // search left
return get(root.left,key);
else // if (key > root.data.getKey()) // search right
return get(root.right,key);
}
// pre: pair nonnull
// post: if key is found in tree, replaces old value with new value
// and returns old value along with root of tree.
// if not found, adds to tree in proper place and returns null
// along with root of tree.
private ReturnWrap put(TreeNode root, KeyValue pair) {
if (root == null) { // key not found; add new entry
size++;
return new ReturnWrap(null,new TreeNode(pair));
}
else if (pair.getKey() == root.data.getKey()) { // replace entry
ReturnWrap ret = new ReturnWrap(root.data,root); // return old data
root.data = pair;
return ret;
}
else if (pair.getKey() < root.data.getKey()) { // search left
ReturnWrap ret = put(root.left,pair);
root.left = ret.node;
ret.node = root;
return ret;
}
else { // if (pair.getKey() > root.data.getKey()) // search right
ReturnWrap ret = put(root.right,pair);
root.right = ret.node;
ret.node = root;
return ret;
}
}
// pre: none
// post: if key is found in tree, removes that node.
// returns new root and the value removed
private ReturnWrap remove(TreeNode root, int key) {
if (root == null) // key not found
return new ReturnWrap(null, null);
else if (root.data.getKey() == key) { // key is here
size--;
ReturnWrap ret = new ReturnWrap(root.data,removeHere(root));
return ret;
} else if (key < root.data.getKey()) { // search left
ReturnWrap ret = remove(root.left,key);
root.left = ret.node;
ret.node = root;
return ret;
} else { // key > root.data.getKey() // search right
ReturnWrap ret = remove(root.right,key);
root.right = ret.node;
ret.node = root;
return ret;
}
}
// pre: node1, node2 are nonnull
// post: node1 and node2 have their .data swapped
private void swapData(TreeNode node1, TreeNode node2) {
KeyValue tmp = node1.data;
node1.data = node2.data;
node2.data = tmp;
}
// pre: root is to be removed from the tree
// post: tree is restructured with root eliminated and still a BST,
// and the new root is returned
private TreeNode removeHere(TreeNode root) {
if (root.left == null) // left not internal; easy
return root.right;
else if (root.right == null) // right not internal; easy
return root.left;
else {
TreeNode node = root.right;
if (node.left == null) { // next larger node is a right-child
swapData(root,node);
root.right = removeHere(root.right); // reduce to easy remove
return root;
}
TreeNode parent;
do { // next larger node is the leftmost descendent of right-child
parent = node;
node = node.left;
} while(node.left != null);
swapData(root,node);
parent.left = removeHere(parent.left); // reduce to an easy remove
return root;
}
}
// pre: none
// post: prints tree specified by root using an inorder traversal
private void printInfix(TreeNode root) {
if (root != null) {
printInfix(root.left);
System.out.println(root.data +
"; L = " + (root.left==null?"null":root.left.data.toString()) +
"; R = " + (root.right==null?"null":root.right.data.toString()));
printInfix(root.right);
}
}
}
::::::::::::::
BSTTest.java
::::::::::::::
// Gary Yngve 10/30/2005
public class BSTTest {
public static void main(String[] arg) {
BinarySearchTree bst = new BinarySearchTree();
bst.put(4,"dog");
bst.put(2,"bat");
bst.put(6,"fox");
bst.put(1,"ape");
bst.put(3,"cow");
bst.put(5,"elk");
bst.put(8,"hog");
bst.put(7,"goat");
bst.printInfix();
bst.remove(4);
bst.printInfix();
}
}
]]>