· 7 years ago · Sep 23, 2018, 06:20 AM
1import java.io.FileNotFoundException;
2import java.io.FileOutputStream;
3import java.io.PrintStream;
4import java.util.Random;
5import java.util.Vector;
6
7
8public class BSTSymbolTable<K extends Comparable<K>,V>
9 implements SymbolTable<K,V>{
10
11 /*
12 * By defining nodes as a private internal class,
13 * we prevent anyone else from being able to mess
14 * with them, so we don't need to worry too much
15 * about protecting the contents of the node itself
16 */
17 private class Node {
18 public K key;
19 public V val;
20 public Node left, right;
21 public int height;
22 public Node(K k, V v) {
23 key=k; val=v;
24 left = right = null;
25 }
26 }
27
28 // this is the root of our tree
29 private Node root;
30
31 private int height(Node n) { // handles empty tree return
32 if (n == null) {
33 return -1;
34 }
35 return n.height;
36 }
37
38 /*
39 * default constructor - this is invoked when we
40 * create a new BSTSymbolTable. All it needs to do
41 * is make sure the root node is empty
42 */
43 public BSTSymbolTable() {root = null;}
44
45
46 /*
47 * This is implementing the insert method SymbolTable
48 * requires us to provide. The @override is not strictly
49 * required, but putting it here means if we forgot
50 * to say "implements SymbolTable<K,V>" when we defined
51 * the class, Java would complain at us. Thus, it's
52 * a useful sanity check.
53 *
54 * Note that all that insert here does is invoke a
55 * recursive insert helper and then set the root node.
56 * (You could do the check for am empty tree here.
57 * Doing it this way will be helpful later, when the
58 * insert helper might need to change the root node.)
59 */
60 @Override
61 public void insert(K key, V val) {
62 root = insertHelper(root, key, val);
63 }
64
65 /*
66 * Recursively insert the given key and value into
67 * the (sub-)tree rooted at tree.
68 *
69 * In this case, if key is already present we replace
70 * the old (key, value) pair with the new ones.
71 * Why would we want to replace the key, too?
72 */
73 private Node insertHelper(Node tree, K key, V val) {
74 if (tree == null) {
75 // (sub-)tree is empty
76 return new Node(key, val);
77 }
78 int cmp = key.compareTo(tree.key);
79
80 if (cmp == 0) {
81 // we found the key
82 tree.key = key;
83 tree.val = val;
84 }
85 else if (cmp < 0) {
86 // key < tree.key
87 tree.left = insertHelper(tree.left, key, val);
88 if(height(tree.left)-height(tree.right)>=2)
89 if(cmp < tree.left.key.compareTo(key))
90 tree = rotateWithLeftChild(tree);
91 else {
92 tree = doubleWithLeftChild(tree);
93 }
94 } else {
95
96 // key > tree.key
97 tree.right = insertHelper(tree.right, key, val);
98 if(height(tree.right)-height(tree.left)>=2)
99 if(cmp > tree.right.key.compareTo(key));
100 tree = rotateWithRightChild(tree);
101
102 tree = doubleWithRightChild(tree);
103 }
104 tree.height = Math.max(height(tree.left),height(tree.right))+1;
105 return tree;
106 }
107
108 private Node rotateWithLeftChild(Node tree){
109 Node k2 = tree;
110 Node k1 = tree.left;
111 k2.left = k1.right;
112 k1.right = k2;
113 k2.height = Math.max(height(k2.left),height(k2.right))+1;
114 k1.height = Math.max(height(k1.right),k2.height)+1;
115 return k1;
116 }
117
118 private Node rotateWithRightChild(Node tree){
119 Node k1 = tree;
120 Node k2 = k1.right;
121 k1.right = k2.left;
122 k2.left = k1;
123 k1.height = Math.max(height(k1.left),height(k1.right))+1;
124 k2.height = Math.max(height(k2.right),k1.height)+1;
125 return k2;
126 }
127
128 //private int max(int leftheight, int rightheight) {
129 // TODO Auto-generated method stub
130 //return leftheight>rightheight ? leftheight: rightheight;
131 //}
132
133 private Node doubleWithLeftChild(Node tree){
134 Node k3 = tree;
135 k3.left = rotateWithRightChild(tree.left);
136
137 return rotateWithLeftChild(tree);
138 }
139
140 private Node doubleWithRightChild(Node tree){
141 Node k1 = tree;
142 k1.right = rotateWithLeftChild(tree.right);
143 return rotateWithRightChild(tree);
144
145 }
146
147 /*
148 * Implementation of the search method in the interface.
149 * Again, we just call a recursive helper.
150 */
151 @Override
152 public V search(K key) {
153 return searchHelper(root, key);
154 }
155
156 /*
157 * Recursively search tree rooted at tree for given key
158 * Returns the associated value, if it exists, or null
159 * if the key is not found.
160 *
161 * Note that as a result of the way this works, we can't
162 * have a key whose value is null
163 */
164 private V searchHelper(Node tree, K key) {
165 if (tree == null) {
166 // tree is empty or no more tree, so key isn't here
167 return null;
168 }
169 int cmp = key.compareTo(tree.key);
170 if (cmp == 0) {
171 // found the key, return its value
172 return tree.val;
173 }
174 /*
175 * the ? : is called the ternary operator. You provide
176 * a logical expression before the ?, the value to give back
177 * if it's true between ? and :, and the value for false
178 * after :. This is compact, but can be hard to read.
179 *
180 * An equivalent if/then would look something like this:
181 * V ret;
182 * if(cmp < 0) {
183 * ret = searchHelper(tree.left, key);
184 * }
185 * else {
186 * ret = searchHelper(tree.right, key);
187 * }
188 * return ret;
189 */
190 return (cmp < 0) ? searchHelper(tree.left, key) : searchHelper(tree.right, key);
191 }
192
193 /*
194 * Implementation of the remove method in the interface.
195 * The recursive helper will toss back the entire node,
196 * so we to extract the value from it to hand back.
197 */
198 @Override
199 public V remove(K key) {
200 Node removed = new Node(null, null);
201 root = removeHelper(root, key, removed);
202 return removed.val;
203 }
204
205
206
207 /*
208 * Recursively delete node with given key from the tree,
209 * and return the updated tree.
210 *
211 * If we found a key and therefore deleted its node,
212 * the key and value are copied into a user-provided
213 * 'removed' argument.
214 *
215 * If key is not found, tree is not altered, nor is
216 * removed, so if removed.val started out as null, it will
217 * only become non-null if we found the key.
218 */
219 private Node removeHelper(Node tree, K key, Node removed) {
220 if (tree == null) {
221 // no more tree, so key isn't here
222 return null;
223 }
224 int cmp = key.compareTo(tree.key);
225 if (cmp == 0) {
226 // found the key. stash payload in removed
227 // and then deal with removing the node
228 removed.key = tree.key;
229 removed.val = tree.val;
230 if (tree.left == null)
231 // no left child
232 return tree.right;
233 else if (tree.right == null)
234 // left child but no right
235 return tree.left;
236 else {
237
238 // both children
239 // find leftmode right child and place it here
240 /*Node node = new Node(null, null);
241 tree.right = removeMin(tree.right, node);
242 tree.key = node.key;
243 tree.val = node.val;
244 return tree;*/
245
246 Node old = tree;
247 tree = rotateMinToRoot(tree.right);
248 tree.left = old.left;
249
250 }
251 } else if (cmp < 0) {
252 // key < tree.key
253 tree.left = removeHelper(tree.left, key, removed);
254 } else {
255 // key > tree.key
256 tree.right = removeHelper(tree.right, key, removed);
257 }
258 return tree;
259 }
260
261 /*
262 * Helper to locate the smallest (leftmost) node
263 * in a tree and remove it, returning the updated tree.
264 * The key and value of the minimum node are passed back
265 * through a user-supplied 'min' argument.
266 *
267 * Note: requires tree != null
268 */
269 private Node rotateMinToRoot(Node tree) {
270 if (tree.left != null) {
271 // found the minimum
272 tree.left = rotateMinToRoot(tree.left);
273 tree = rotateWithLeftChild(tree);
274 }
275
276 return tree;
277 }
278
279 /*
280 * This method is not part of the symbol table interface
281 * Instead, it lets us convert the BSTSymbolTable into a
282 * form that's easy to hand off for display.
283 * This works by traversing the tree (with a helper) and
284 * shoving information about its nodes into a vector we
285 * can pass off later.
286 */
287 public Vector<String> serialize() {
288 Vector<String> vec = new Vector<>();
289 serializeHelper(root, vec);
290 return vec;
291 }
292
293 /*
294 * Perform a (recursive) pre-order traversal and
295 * store node information into a provided vector of strings.
296 * Note that we add ":black" to the end of the node's key.
297 * This is because the TreePrinter will happily work on
298 * Red-Black trees, where color is significant, so we fill
299 * in a default.
300 */
301 private void serializeHelper(Node tree, Vector<String> vec) {
302 if (tree == null)
303 vec.addElement(null);
304 else {
305 vec.addElement(tree.key.toString() + ":black");
306 serializeHelper(tree.left, vec);
307 serializeHelper(tree.right, vec);
308 }
309 }
310
311
312 /*
313 * This main provides a relatively simple test harness for
314 * the BSTSymbolTable, by randomly adding some nodes, removing
315 * a few, and then invoking the TreePrinter to get a picture
316 * of the tree.
317 */
318 public static void main(String args[]) {
319 /*
320 * Normally you'd probably want to use a SymbolTable on
321 * the left here, but because we want to use .serialize(),
322 * which is part of BSTSymbolTable but not SymbolTable, it's
323 * easier to just call it a BSTSymbolTable to begin with, rather
324 * than doing a cast.
325 */
326 BSTSymbolTable<Integer,Integer> symtab = new BSTSymbolTable<>();
327
328 /*
329 * This will insert 100 nodes with random values for us.
330 * We'll always get the same random sequence. If you want
331 * a different one, either remove the 1234, or replace it
332 * with something else.
333 */
334
335 Random RNG = new Random(1234);
336 for (int i = 0; i < 100; i++) {
337 int r = (int) (RNG.nextDouble()*100);
338 symtab.insert(r,r);
339 }
340
341 // removing nodes using the SymbolTable interface.
342 symtab.remove(64);
343 symtab.remove(26);
344 symtab.remove(64);
345
346 /*
347 * this block interacts with the TreePrinter for us.
348 * First, we generate a vector of strings containing the
349 * serialized tree. Once that's done, use it to create
350 * a TreePrinter object, and then open a file and have
351 * the TreePrinter throw a picture of the tree into the file.
352 *
353 * If you're using Eclipse, tree.svg will end up in the project
354 * directory in your workspace. So, figure out where the source
355 * files are stored, and go up one from there.
356 */
357 Vector<String> st = symtab.serialize();
358 TreePrinter treePrinter = new TreePrinter(st);
359 try {
360 FileOutputStream out = new FileOutputStream("tree.svg");
361 PrintStream ps = new PrintStream(out);
362 treePrinter.printSVG(ps);
363 } catch (FileNotFoundException e) {}
364
365
366 }
367
368}