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