kona/src/org/feistymeow/algorithms/BinarySearchTree.java

   1 package org.feistymeow.algorithms;
   2
   3
   4 //hmmm: move to better folder path.
   5
   6 // inspired by http://pages.cs.wisc.edu/~cs367-1/readings/Binary-Search-Trees/
   7
   8 /**
   9  * The type of node held in our binary search tree.
  10  */
  11 class TreeNode<K, V>
  12 {
  13     private K key;
  14     private V value;
  15     private TreeNode<K, V> left, right;
  16
  17     public TreeNode(K key, V value, TreeNode<K, V> left, TreeNode<K, V> right) {
  18         this.key = key;
  19         this.value = value;
  20         this.left = left;
  21         this.right = right;
  22     }
  23
  24     public K getKey() { return key; }
  25     public V getValue() { return value; }
  26
  27
  28     public TreeNode<K, V> getLeft() { return left; }
  29     public TreeNode<K, V> getRight() { return right; }
  30
  31     public void setKey(K newK) { key = newK; }
  32     public void setLeft(TreeNode<K, V> newL) { left = newL; }
  33     public void setRight(TreeNode<K, V> newR) { right = newR; }
  34
  35     public void setValue(V newV) { value = newV; }
  36 }
  37
  38 class DuplicateException extends RuntimeException
  39 {
  40         private static final long serialVersionUID = 1L;
  41         DuplicateException() {}
  42 }
  43
  44 /**
  45  * A binary search tree implementation.
  46  *
  47  * Insert, Delete and Search are done in O(n log(n)) time.
  48  */
  49 public class BinarySearchTree<K extends Comparable<K>, V>
  50 {
  51     private TreeNode<K, V> root; // ptr to the root of the BinarySearchTree
  52
  53     public BinarySearchTree() { root = null; }
  54
  55
  56     // add key and associated value to this BinarySearchTree;
  57     // error if key is already there
  58     public void insert(K key, V value) throws DuplicateException {
  59         root = insert(root, value, key);
  60     }
  61
  62     private TreeNode<K, V> insert(TreeNode<K, V> n, V value, K key) throws DuplicateException {
  63         if (n == null) {
  64             return new TreeNode<K, V>(key, value, null, null);
  65         }
  66
  67         if (n.getKey().equals(key)) {
  68             throw new DuplicateException();
  69         }
  70
  71         if (key.compareTo(n.getKey()) < 0) {
  72             // add key to the left subtree
  73             n.setLeft( insert(n.getLeft(), value, key) );
  74             return n;
  75         }
  76
  77         else {
  78             // add key to the right subtree
  79             n.setRight( insert(n.getRight(), value, key) );
  80             return n;
  81         }
  82     }
  83
  84     // remove the node containing key from this BinarySearchTree if it is there;
  85     // otherwise, do nothing
  86     public void delete(K key) {
  87         root = delete(root, key);
  88     }
  89
  90
  91     private K smallest(TreeNode<K, V> n)
  92  // precondition: n is not null
  93  // postcondition: return the smallest value in the subtree rooted at n
  94
  95  {
  96      if (n.getLeft() == null) {
  97          return n.getKey();
  98      } else {
  99          return smallest(n.getLeft());
 100      }
 101  }
 102
 103     private TreeNode<K, V> delete(TreeNode<K, V> n, K key)
 104     {
 105         if (n == null) {
 106             return null;
 107         }
 108
 109         if (key.equals(n.getKey())) {
 110
 111                 if (n.getLeft() == null && n.getRight() == null) {
 112                 return null;
 113             }
 114             if (n.getLeft() == null) {
 115                 return n.getRight();
 116             }
 117             if (n.getRight() == null) {
 118                 return n.getLeft();
 119             }
 120
 121             // if we get here, then n has 2 children
 122             K smallVal = smallest(n.getRight());
 123             n.setKey(smallVal);
 124             n.setRight( delete(n.getRight(), smallVal) );
 125             return n;
 126         }
 127
 128         else if (key.compareTo(n.getKey()) < 0) {
 129             n.setLeft( delete(n.getLeft(), key) );
 130             return n;
 131         }
 132
 133         else {
 134             n.setRight( delete(n.getRight(), key) );
 135             return n;
 136         }
 137     }
 138
 139
 140     // if key is in this BinarySearchTree, return its associated value; otherwise, return null
 141     public boolean lookup(K key) {
 142         return lookup(root, key);
 143     }
 144
 145     private boolean lookup(TreeNode<K, V> n, K key) {
 146         if (n == null) {
 147             return false;
 148         }
 149
 150         if (n.getKey().equals(key)) {
 151             return true;
 152         }
 153
 154         if (key.compareTo(n.getKey()) < 0) {
 155             // key < this node's key; look in left subtree
 156             return lookup(n.getLeft(), key);
 157         }
 158
 159         else {
 160             // key > this node's key; look in right subtree
 161             return lookup(n.getRight(), key);
 162         }
 163     }
 164
 165 //    // print the values in this BinarySearchTree in sorted order (to p)
 166 //    public void print(PrintStream p) {
 167 //
 168 //    }
 169 }
 170