· 4 years ago · Jun 03, 2021, 03:58 PM
1/******************************************************************************
2 * Compilation: javac RedBlackBST.java
3 * Execution: java RedBlackBST < input.txt
4 * Data files: https://algs4.cs.princeton.edu/33balanced/tinyST.txt
5 *
6 * A symbol table implemented using a left-leaning red-black BST.
7 * This is the 2-3 version.
8 *
9 * Note: commented out assertions because DrJava now enables assertions
10 * by default.
11 *
12 * % more tinyST.txt
13 * S E A R C H E X A M P L E
14 *
15 * % java RedBlackBST < tinyST.txt
16 * 10
17 * A
18 * C
19 * E
20 * H
21 * L
22 * M
23 * P
24 * R
25 * S
26 * X
27 *
28 ******************************************************************************/
29
30import java.util.*;
31
32/**
33 * The {@code BST} class represents an ordered symbol table of generic
34 * key-value pairs.
35 * It supports the usual <em>put</em>, <em>get</em>, <em>contains</em>,
36 * <em>delete</em>, <em>size</em>, and <em>is-empty</em> methods.
37 * It also provides ordered methods for finding the <em>minimum</em>,
38 * <em>maximum</em>, <em>floor</em>, and <em>ceiling</em>.
39 * It also provides a <em>keys</em> method for iterating over all of the keys.
40 * A symbol table implements the <em>associative array</em> abstraction:
41 * when associating a value with a key that is already in the symbol table,
42 * the convention is to replace the old value with the new value.
43 * Unlike {@link java.util.Map}, this class uses the convention that
44 * values cannot be {@code null}—setting the
45 * value associated with a key to {@code null} is equivalent to deleting the key
46 * from the symbol table.
47 * <p>
48 * It requires that
49 * the key type implements the {@code Comparable} interface and calls the
50 * {@code compareTo()} and method to compare two keys. It does not call either
51 * {@code equals()} or {@code hashCode()}.
52 * <p>
53 * This implementation uses a <em>left-leaning red-black BST</em>.
54 * The <em>put</em>, <em>get</em>, <em>contains</em>, <em>remove</em>,
55 * <em>minimum</em>, <em>maximum</em>, <em>ceiling</em>, <em>floor</em>,
56 * <em>rank</em>, and <em>select</em> operations each take
57 * Θ(log <em>n</em>) time in the worst case, where <em>n</em> is the
58 * number of key-value pairs in the symbol table.
59 * The <em>size</em>, and <em>is-empty</em> operations take Θ(1) time.
60 * The <em>keys</em> methods take
61 * <em>O</em>(log <em>n</em> + <em>m</em>) time, where <em>m</em> is
62 * the number of keys returned by the iterator.
63 * Construction takes Θ(1) time.
64 * <p>
65 * For alternative implementations of the symbol table API, see {@link ST},
66 * {@link BinarySearchST}, {@link SequentialSearchST}, {@link BST},
67 * {@link SeparateChainingHashST}, {@link LinearProbingHashST}, and
68 * {@link AVLTreeST}.
69 * For additional documentation, see
70 * <a href="https://algs4.cs.princeton.edu/33balanced">Section 3.3</a> of
71 * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
72 *
73 * @author Robert Sedgewick
74 * @author Kevin Wayne
75 */
76
77public class RedBlackBST<Key extends Comparable<Key>, Value> {
78
79 private static final boolean RED = true;
80 private static final boolean BLACK = false;
81
82 private Node root; // root of the BST
83
84 // BST helper node data type
85 private class Node {
86 private Key key; // key
87 private Value val; // associated data
88 private Node left, right; // links to left and right subtrees
89 private boolean color; // color of parent link
90 private int size; // subtree count
91
92 public Node(Key key, Value val, boolean color, int size) {
93 this.key = key;
94 this.val = val;
95 this.color = color;
96 this.size = size;
97 }
98 }
99
100 /**
101 * Initializes an empty symbol table.
102 */
103 public RedBlackBST() {
104 }
105
106 /***************************************************************************
107 * Node helper methods.
108 ***************************************************************************/
109 // is node x red; false if x is null ?
110 private boolean isRed(Node x) {
111 if (x == null) return false;
112 return x.color == RED;
113 }
114
115 // number of node in subtree rooted at x; 0 if x is null
116 private int size(Node x) {
117 if (x == null) return 0;
118 return x.size;
119 }
120
121
122 /**
123 * Returns the number of key-value pairs in this symbol table.
124 * @return the number of key-value pairs in this symbol table
125 */
126 public int size() {
127 return size(root);
128 }
129
130 /**
131 * Is this symbol table empty?
132 * @return {@code true} if this symbol table is empty and {@code false} otherwise
133 */
134 public boolean isEmpty() {
135 return root == null;
136 }
137
138
139 /***************************************************************************
140 * Standard BST search.
141 ***************************************************************************/
142
143 /**
144 * Returns the value associated with the given key.
145 * @param key the key
146 * @return the value associated with the given key if the key is in the symbol table
147 * and {@code null} if the key is not in the symbol table
148 * @throws IllegalArgumentException if {@code key} is {@code null}
149 */
150 public Value get(Key key) {
151 if (key == null) throw new IllegalArgumentException("argument to get() is null");
152 return get(root, key);
153 }
154
155 // value associated with the given key in subtree rooted at x; null if no such key
156 private Value get(Node x, Key key) {
157 while (x != null) {
158 int cmp = key.compareTo(x.key);
159 if (cmp < 0) x = x.left;
160 else if (cmp > 0) x = x.right;
161 else return x.val;
162 }
163 return null;
164 }
165
166 /**
167 * Does this symbol table contain the given key?
168 * @param key the key
169 * @return {@code true} if this symbol table contains {@code key} and
170 * {@code false} otherwise
171 * @throws IllegalArgumentException if {@code key} is {@code null}
172 */
173 public boolean contains(Key key) {
174 return get(key) != null;
175 }
176
177 /***************************************************************************
178 * Red-black tree insertion.
179 ***************************************************************************/
180
181 /**
182 * Inserts the specified key-value pair into the symbol table, overwriting the old
183 * value with the new value if the symbol table already contains the specified key.
184 * Deletes the specified key (and its associated value) from this symbol table
185 * if the specified value is {@code null}.
186 *
187 * @param key the key
188 * @param val the value
189 * @throws IllegalArgumentException if {@code key} is {@code null}
190 */
191 public void put(Key key, Value val) {
192 if (key == null) throw new IllegalArgumentException("first argument to put() is null");
193 if (val == null) {
194 delete(key);
195 return;
196 }
197
198 root = put(root, key, val);
199 root.color = BLACK;
200 // assert check();
201 }
202
203 // insert the key-value pair in the subtree rooted at h
204 private Node put(Node h, Key key, Value val) {
205 if (h == null) return new Node(key, val, RED, 1);
206
207 int cmp = key.compareTo(h.key);
208 if (cmp < 0) h.left = put(h.left, key, val);
209 else if (cmp > 0) h.right = put(h.right, key, val);
210 else h.val = val;
211
212 // fix-up any right-leaning links
213 if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
214 if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
215 if (isRed(h.left) && isRed(h.right)) flipColors(h);
216 h.size = size(h.left) + size(h.right) + 1;
217
218 return h;
219 }
220
221 /***************************************************************************
222 * Red-black tree deletion.
223 ***************************************************************************/
224
225 /**
226 * Removes the smallest key and associated value from the symbol table.
227 * @throws NoSuchElementException if the symbol table is empty
228 */
229 public void deleteMin() {
230 if (isEmpty()) throw new NoSuchElementException("BST underflow");
231
232 // if both children of root are black, set root to red
233 if (!isRed(root.left) && !isRed(root.right))
234 root.color = RED;
235
236 root = deleteMin(root);
237 if (!isEmpty()) root.color = BLACK;
238 // assert check();
239 }
240
241 // delete the key-value pair with the minimum key rooted at h
242 private Node deleteMin(Node h) {
243 if (h.left == null)
244 return null;
245
246 if (!isRed(h.left) && !isRed(h.left.left))
247 h = moveRedLeft(h);
248
249 h.left = deleteMin(h.left);
250 return balance(h);
251 }
252
253
254 /**
255 * Removes the largest key and associated value from the symbol table.
256 * @throws NoSuchElementException if the symbol table is empty
257 */
258 public void deleteMax() {
259 if (isEmpty()) throw new NoSuchElementException("BST underflow");
260
261 // if both children of root are black, set root to red
262 if (!isRed(root.left) && !isRed(root.right))
263 root.color = RED;
264
265 root = deleteMax(root);
266 if (!isEmpty()) root.color = BLACK;
267 // assert check();
268 }
269
270 // delete the key-value pair with the maximum key rooted at h
271 private Node deleteMax(Node h) {
272 if (isRed(h.left))
273 h = rotateRight(h);
274
275 if (h.right == null)
276 return null;
277
278 if (!isRed(h.right) && !isRed(h.right.left))
279 h = moveRedRight(h);
280
281 h.right = deleteMax(h.right);
282
283 return balance(h);
284 }
285
286 /**
287 * Removes the specified key and its associated value from this symbol table
288 * (if the key is in this symbol table).
289 *
290 * @param key the key
291 * @throws IllegalArgumentException if {@code key} is {@code null}
292 */
293 public void delete(Key key) {
294 if (key == null) throw new IllegalArgumentException("argument to delete() is null");
295 if (!contains(key)) return;
296
297 // if both children of root are black, set root to red
298 if (!isRed(root.left) && !isRed(root.right))
299 root.color = RED;
300
301 root = delete(root, key);
302 if (!isEmpty()) root.color = BLACK;
303 // assert check();
304 }
305
306 // delete the key-value pair with the given key rooted at h
307 private Node delete(Node h, Key key) {
308 // assert get(h, key) != null;
309
310 if (key.compareTo(h.key) < 0) {
311 if (!isRed(h.left) && !isRed(h.left.left))
312 h = moveRedLeft(h);
313 h.left = delete(h.left, key);
314 }
315 else {
316 if (isRed(h.left))
317 h = rotateRight(h);
318 if (key.compareTo(h.key) == 0 && (h.right == null))
319 return null;
320 if (!isRed(h.right) && !isRed(h.right.left))
321 h = moveRedRight(h);
322 if (key.compareTo(h.key) == 0) {
323 Node x = min(h.right);
324 h.key = x.key;
325 h.val = x.val;
326 // h.val = get(h.right, min(h.right).key);
327 // h.key = min(h.right).key;
328 h.right = deleteMin(h.right);
329 }
330 else h.right = delete(h.right, key);
331 }
332 return balance(h);
333 }
334
335 /***************************************************************************
336 * Red-black tree helper functions.
337 ***************************************************************************/
338
339 // make a left-leaning link lean to the right
340 private Node rotateRight(Node h) {
341 assert (h != null) && isRed(h.left);
342 // assert (h != null) && isRed(h.left) && !isRed(h.right); // for insertion only
343 Node x = h.left;
344 h.left = x.right;
345 x.right = h;
346 x.color = x.right.color;
347 x.right.color = RED;
348 x.size = h.size;
349 h.size = size(h.left) + size(h.right) + 1;
350 return x;
351 }
352
353 // make a right-leaning link lean to the left
354 private Node rotateLeft(Node h) {
355 assert (h != null) && isRed(h.right);
356 // assert (h != null) && isRed(h.right) && !isRed(h.left); // for insertion only
357 Node x = h.right;
358 h.right = x.left;
359 x.left = h;
360 x.color = x.left.color;
361 x.left.color = RED;
362 x.size = h.size;
363 h.size = size(h.left) + size(h.right) + 1;
364 return x;
365 }
366
367 // flip the colors of a node and its two children
368 private void flipColors(Node h) {
369 // h must have opposite color of its two children
370 // assert (h != null) && (h.left != null) && (h.right != null);
371 // assert (!isRed(h) && isRed(h.left) && isRed(h.right))
372 // || (isRed(h) && !isRed(h.left) && !isRed(h.right));
373 h.color = !h.color;
374 h.left.color = !h.left.color;
375 h.right.color = !h.right.color;
376 }
377
378 // Assuming that h is red and both h.left and h.left.left
379 // are black, make h.left or one of its children red.
380 private Node moveRedLeft(Node h) {
381 // assert (h != null);
382 // assert isRed(h) && !isRed(h.left) && !isRed(h.left.left);
383
384 flipColors(h);
385 if (isRed(h.right.left)) {
386 h.right = rotateRight(h.right);
387 h = rotateLeft(h);
388 flipColors(h);
389 }
390 return h;
391 }
392
393 // Assuming that h is red and both h.right and h.right.left
394 // are black, make h.right or one of its children red.
395 private Node moveRedRight(Node h) {
396 // assert (h != null);
397 // assert isRed(h) && !isRed(h.right) && !isRed(h.right.left);
398 flipColors(h);
399 if (isRed(h.left.left)) {
400 h = rotateRight(h);
401 flipColors(h);
402 }
403 return h;
404 }
405
406 // restore red-black tree invariant
407 private Node balance(Node h) {
408 // assert (h != null);
409
410 if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
411 if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
412 if (isRed(h.left) && isRed(h.right)) flipColors(h);
413
414 h.size = size(h.left) + size(h.right) + 1;
415 return h;
416 }
417
418
419 /***************************************************************************
420 * Utility functions.
421 ***************************************************************************/
422
423 /**
424 * Returns the height of the BST (for debugging).
425 * @return the height of the BST (a 1-node tree has height 0)
426 */
427 public int height() {
428 return height(root);
429 }
430 private int height(Node x) {
431 if (x == null) return -1;
432 return 1 + Math.max(height(x.left), height(x.right));
433 }
434
435 /***************************************************************************
436 * Ordered symbol table methods.
437 ***************************************************************************/
438
439 /**
440 * Returns the smallest key in the symbol table.
441 * @return the smallest key in the symbol table
442 * @throws NoSuchElementException if the symbol table is empty
443 */
444 public Key min() {
445 if (isEmpty()) throw new NoSuchElementException("calls min() with empty symbol table");
446 return min(root).key;
447 }
448
449 // the smallest key in subtree rooted at x; null if no such key
450 private Node min(Node x) {
451 // assert x != null;
452 if (x.left == null) return x;
453 else return min(x.left);
454 }
455
456 /**
457 * Returns the largest key in the symbol table.
458 * @return the largest key in the symbol table
459 * @throws NoSuchElementException if the symbol table is empty
460 */
461 public Key max() {
462 if (isEmpty()) throw new NoSuchElementException("calls max() with empty symbol table");
463 return max(root).key;
464 }
465
466 // the largest key in the subtree rooted at x; null if no such key
467 private Node max(Node x) {
468 // assert x != null;
469 if (x.right == null) return x;
470 else return max(x.right);
471 }
472
473
474 /**
475 * Returns the largest key in the symbol table less than or equal to {@code key}.
476 * @param key the key
477 * @return the largest key in the symbol table less than or equal to {@code key}
478 * @throws NoSuchElementException if there is no such key
479 * @throws IllegalArgumentException if {@code key} is {@code null}
480 */
481 public Key floor(Key key) {
482 if (key == null) throw new IllegalArgumentException("argument to floor() is null");
483 if (isEmpty()) throw new NoSuchElementException("calls floor() with empty symbol table");
484 Node x = floor(root, key);
485 if (x == null) throw new NoSuchElementException("argument to floor() is too small");
486 else return x.key;
487 }
488
489 // the largest key in the subtree rooted at x less than or equal to the given key
490 private Node floor(Node x, Key key) {
491 if (x == null) return null;
492 int cmp = key.compareTo(x.key);
493 if (cmp == 0) return x;
494 if (cmp < 0) return floor(x.left, key);
495 Node t = floor(x.right, key);
496 if (t != null) return t;
497 else return x;
498 }
499
500 /**
501 * Returns the smallest key in the symbol table greater than or equal to {@code key}.
502 * @param key the key
503 * @return the smallest key in the symbol table greater than or equal to {@code key}
504 * @throws NoSuchElementException if there is no such key
505 * @throws IllegalArgumentException if {@code key} is {@code null}
506 */
507 public Key ceiling(Key key) {
508 if (key == null) throw new IllegalArgumentException("argument to ceiling() is null");
509 if (isEmpty()) throw new NoSuchElementException("calls ceiling() with empty symbol table");
510 Node x = ceiling(root, key);
511 if (x == null) throw new NoSuchElementException("argument to ceiling() is too small");
512 else return x.key;
513 }
514
515 // the smallest key in the subtree rooted at x greater than or equal to the given key
516 private Node ceiling(Node x, Key key) {
517 if (x == null) return null;
518 int cmp = key.compareTo(x.key);
519 if (cmp == 0) return x;
520 if (cmp > 0) return ceiling(x.right, key);
521 Node t = ceiling(x.left, key);
522 if (t != null) return t;
523 else return x;
524 }
525
526 /**
527 * Return the key in the symbol table of a given {@code rank}.
528 * This key has the property that there are {@code rank} keys in
529 * the symbol table that are smaller. In other words, this key is the
530 * ({@code rank}+1)st smallest key in the symbol table.
531 *
532 * @param rank the order statistic
533 * @return the key in the symbol table of given {@code rank}
534 * @throws IllegalArgumentException unless {@code rank} is between 0 and
535 * <em>n</em>–1
536 */
537 public Key select(int rank) {
538 if (rank < 0 || rank >= size()) {
539 throw new IllegalArgumentException("argument to select() is invalid: " + rank);
540 }
541 return select(root, rank);
542 }
543
544 // Return key in BST rooted at x of given rank.
545 // Precondition: rank is in legal range.
546 private Key select(Node x, int rank) {
547 if (x == null) return null;
548 int leftSize = size(x.left);
549 if (leftSize > rank) return select(x.left, rank);
550 else if (leftSize < rank) return select(x.right, rank - leftSize - 1);
551 else return x.key;
552 }
553
554 /**
555 * Return the number of keys in the symbol table strictly less than {@code key}.
556 * @param key the key
557 * @return the number of keys in the symbol table strictly less than {@code key}
558 * @throws IllegalArgumentException if {@code key} is {@code null}
559 */
560 public int rank(Key key) {
561 if (key == null) throw new IllegalArgumentException("argument to rank() is null");
562 return rank(key, root);
563 }
564
565 // number of keys less than key in the subtree rooted at x
566 private int rank(Key key, Node x) {
567 if (x == null) return 0;
568 int cmp = key.compareTo(x.key);
569 if (cmp < 0) return rank(key, x.left);
570 else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right);
571 else return size(x.left);
572 }
573
574 /***************************************************************************
575 * Range count and range search.
576 ***************************************************************************/
577
578 /**
579 * Returns all keys in the symbol table as an {@code Iterable}.
580 * To iterate over all of the keys in the symbol table named {@code st},
581 * use the foreach notation: {@code for (Key key : st.keys())}.
582 * @return all keys in the symbol table as an {@code Iterable}
583 */
584 public Iterable<Key> keys() {
585 if (isEmpty()) return new ArrayDeque<Key>();
586 return keys(min(), max());
587 }
588
589 /**
590 * Returns all keys in the symbol table in the given range,
591 * as an {@code Iterable}.
592 *
593 * @param lo minimum endpoint
594 * @param hi maximum endpoint
595 * @return all keys in the symbol table between {@code lo}
596 * (inclusive) and {@code hi} (inclusive) as an {@code Iterable}
597 * @throws IllegalArgumentException if either {@code lo} or {@code hi}
598 * is {@code null}
599 */
600 public Iterable<Key> keys(Key lo, Key hi) {
601 if (lo == null) throw new IllegalArgumentException("first argument to keys() is null");
602 if (hi == null) throw new IllegalArgumentException("second argument to keys() is null");
603
604 Queue<Key> queue = new ArrayDeque<Key>();
605 // if (isEmpty() || lo.compareTo(hi) > 0) return queue;
606 keys(root, queue, lo, hi);
607 return queue;
608 }
609
610 // add the keys between lo and hi in the subtree rooted at x
611 // to the queue
612 private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
613 if (x == null) return;
614 int cmplo = lo.compareTo(x.key);
615 int cmphi = hi.compareTo(x.key);
616 if (cmplo < 0) keys(x.left, queue, lo, hi);
617 if (cmplo <= 0 && cmphi >= 0) queue.add(x.key);
618 if (cmphi > 0) keys(x.right, queue, lo, hi);
619 }
620
621 /**
622 * Returns the number of keys in the symbol table in the given range.
623 *
624 * @param lo minimum endpoint
625 * @param hi maximum endpoint
626 * @return the number of keys in the symbol table between {@code lo}
627 * (inclusive) and {@code hi} (inclusive)
628 * @throws IllegalArgumentException if either {@code lo} or {@code hi}
629 * is {@code null}
630 */
631 public int size(Key lo, Key hi) {
632 if (lo == null) throw new IllegalArgumentException("first argument to size() is null");
633 if (hi == null) throw new IllegalArgumentException("second argument to size() is null");
634
635 if (lo.compareTo(hi) > 0) return 0;
636 if (contains(hi)) return rank(hi) - rank(lo) + 1;
637 else return rank(hi) - rank(lo);
638 }
639
640
641 /***************************************************************************
642 * Check integrity of red-black tree data structure.
643 ***************************************************************************/
644 private boolean check() {
645 if (!isBST()) System.out.println("Not in symmetric order");
646 if (!isSizeConsistent()) System.out.println("Subtree counts not consistent");
647 if (!isRankConsistent()) System.out.println("Ranks not consistent");
648 if (!is23()) System.out.println("Not a 2-3 tree");
649 if (!isBalanced()) System.out.println("Not balanced");
650 return isBST() && isSizeConsistent() && isRankConsistent() && is23() && isBalanced();
651 }
652
653 // does this binary tree satisfy symmetric order?
654 // Note: this test also ensures that data structure is a binary tree since order is strict
655 private boolean isBST() {
656 return isBST(root, null, null);
657 }
658
659 // is the tree rooted at x a BST with all keys strictly between min and max
660 // (if min or max is null, treat as empty constraint)
661 // Credit: Bob Dondero's elegant solution
662 private boolean isBST(Node x, Key min, Key max) {
663 if (x == null) return true;
664 if (min != null && x.key.compareTo(min) <= 0) return false;
665 if (max != null && x.key.compareTo(max) >= 0) return false;
666 return isBST(x.left, min, x.key) && isBST(x.right, x.key, max);
667 }
668
669 // are the size fields correct?
670 private boolean isSizeConsistent() { return isSizeConsistent(root); }
671 private boolean isSizeConsistent(Node x) {
672 if (x == null) return true;
673 if (x.size != size(x.left) + size(x.right) + 1) return false;
674 return isSizeConsistent(x.left) && isSizeConsistent(x.right);
675 }
676
677 // check that ranks are consistent
678 private boolean isRankConsistent() {
679 for (int i = 0; i < size(); i++)
680 if (i != rank(select(i))) return false;
681 for (Key key : keys())
682 if (key.compareTo(select(rank(key))) != 0) return false;
683 return true;
684 }
685
686 // Does the tree have no red right links, and at most one (left)
687 // red links in a row on any path?
688 private boolean is23() { return is23(root); }
689 private boolean is23(Node x) {
690 if (x == null) return true;
691 if (isRed(x.right)) return false;
692 if (x != root && isRed(x) && isRed(x.left))
693 return false;
694 return is23(x.left) && is23(x.right);
695 }
696
697 // do all paths from root to leaf have same number of black edges?
698 private boolean isBalanced() {
699 int black = 0; // number of black links on path from root to min
700 Node x = root;
701 while (x != null) {
702 if (!isRed(x)) black++;
703 x = x.left;
704 }
705 return isBalanced(root, black);
706 }
707
708 // does every path from the root to a leaf have the given number of black links?
709 private boolean isBalanced(Node x, int black) {
710 if (x == null) return black == 0;
711 if (!isRed(x)) black--;
712 return isBalanced(x.left, black) && isBalanced(x.right, black);
713 }
714
715
716 /**
717 * Unit tests the {@code RedBlackBST} data type.
718 *
719 * @param args the command-line arguments
720 */
721 public static void main(String[] args) {
722 RedBlackBST<String, Integer> st = new RedBlackBST<String, Integer>();
723 var in = new Scanner(System.in);
724 int n = Integer.parseInt(in.nextLine());
725 for (int i = 0; i < n; i++) {
726 String key = in.nextLine();
727 st.put(key, i);
728 }
729 in.close();
730 System.out.println();
731 for (String s : st.keys())
732 System.out.println(s + " " + st.get(s));
733 System.out.println();
734 }
735}