adapted to new storage location
[feisty_meow.git] / 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