001package algs32; 002import stdlib.*; 003import algs13.Queue; 004/* *********************************************************************** 005 * Compilation: javac BSTWithStaticNode.java 006 * Execution: java BSTWithStaticNode 007 * Dependencies: StdIn.java StdOut.java 008 * Data files: http://algs4.cs.princeton.edu/32bst/tinyST.txt 009 * 010 * A symbol table implemented with a binary search tree. 011 * 012 * % more tinyST.txt 013 * S E A R C H E X A M P L E 014 * 015 * % java BSTWithStaticNode < tinyST.txt 016 * A 8 017 * C 4 018 * E 12 019 * H 5 020 * L 11 021 * M 9 022 * P 10 023 * R 3 024 * S 0 025 * X 7 026 * 027 *************************************************************************/ 028 029public class XBSTWithNonStaticNode<K extends Comparable<? super K>, V> { 030 private Node root; // root of XBSTWithStaticNode 031 032 private class Node { 033 public final K key; // sorted by key 034 public V val; // associated data 035 public Node left, right; // left and right subtrees 036 public int N; // number of nodes in subtree 037 038 public Node(K key, V val, int N) { 039 this.key = key; 040 this.val = val; 041 this.N = N; 042 } 043 } 044 045 // is the symbol table empty? 046 public boolean isEmpty() { return size() == 0; } 047 048 // return number of key-value pairs in XBSTWithStaticNode 049 public int size() { return size(root); } 050 051 // return number of key-value pairs in XBSTWithStaticNode rooted at x 052 private int size(Node x) { 053 if (x == null) return 0; 054 else return x.N; 055 } 056 057 /* ********************************************************************* 058 * Search XBSTWithStaticNode for given key, and return associated value if found, 059 * return null if not found 060 ***********************************************************************/ 061 // does there exist a key-value pair with given key? 062 public boolean contains(K key) { return get(key) != null; } 063 064 // return value associated with the given key, or null if no such key exists 065 public V get(K key) { return get(root, key); } 066 067 private V get(Node x, K key) { 068 if (x == null) return null; 069 int cmp = key.compareTo(x.key); 070 if (cmp < 0) return get(x.left, key); 071 else if (cmp > 0) return get(x.right, key); 072 else return x.val; 073 } 074 075 /* ********************************************************************* 076 * Insert key-value pair into XBSTWithStaticNode 077 * If key already exists, update with new value 078 ***********************************************************************/ 079 public void put(K key, V val) { 080 if (val == null) { delete(key); return; } 081 root = put(root, key, val); 082 //assert check(); 083 } 084 085 private Node put(Node x, K key, V val) { 086 if (x == null) return new Node(key, val, 1); 087 int cmp = key.compareTo(x.key); 088 if (cmp < 0) x.left = put(x.left, key, val); 089 else if (cmp > 0) x.right = put(x.right, key, val); 090 else x.val = val; 091 x.N = 1 + size(x.left) + size(x.right); 092 return x; 093 } 094 095 /* ********************************************************************* 096 * Delete 097 ***********************************************************************/ 098 099 public void deleteMin() { 100 if (isEmpty()) throw new Error("Symbol table underflow"); 101 root = deleteMin(root); 102 //assert check(); 103 } 104 105 private Node deleteMin(Node x) { 106 if (x.left == null) return x.right; 107 x.left = deleteMin(x.left); 108 x.N = size(x.left) + size(x.right) + 1; 109 return x; 110 } 111 112 public void deleteMax() { 113 if (isEmpty()) throw new Error("Symbol table underflow"); 114 root = deleteMax(root); 115 //assert check(); 116 } 117 118 private Node deleteMax(Node x) { 119 if (x.right == null) return x.left; 120 x.right = deleteMax(x.right); 121 x.N = size(x.left) + size(x.right) + 1; 122 return x; 123 } 124 125 public void delete(K key) { 126 root = delete(root, key); 127 //assert check(); 128 } 129 130 private Node delete(Node x, K key) { 131 if (x == null) return null; 132 int cmp = key.compareTo(x.key); 133 if (cmp < 0) x.left = delete(x.left, key); 134 else if (cmp > 0) x.right = delete(x.right, key); 135 else { 136 if (x.right == null) return x.left; 137 if (x.left == null) return x.right; 138 Node t = x; 139 x = min(t.right); 140 x.right = deleteMin(t.right); 141 x.left = t.left; 142 } 143 x.N = size(x.left) + size(x.right) + 1; 144 return x; 145 } 146 147 148 /* ********************************************************************* 149 * Min, max, floor, and ceiling 150 ***********************************************************************/ 151 public K min() { 152 if (isEmpty()) return null; 153 return min(root).key; 154 } 155 156 private Node min(Node x) { 157 if (x.left == null) return x; 158 else return min(x.left); 159 } 160 161 public K max() { 162 if (isEmpty()) return null; 163 return max(root).key; 164 } 165 166 private Node max(Node x) { 167 if (x.right == null) return x; 168 else return max(x.right); 169 } 170 171 public K floor(K key) { 172 Node x = floor(root, key); 173 if (x == null) return null; 174 else return x.key; 175 } 176 177 private Node floor(Node x, K key) { 178 if (x == null) return null; 179 int cmp = key.compareTo(x.key); 180 if (cmp == 0) return x; 181 if (cmp < 0) return floor(x.left, key); 182 Node t = floor(x.right, key); 183 if (t != null) return t; 184 else return x; 185 } 186 187 public K ceiling(K key) { 188 Node x = ceiling(root, key); 189 if (x == null) return null; 190 else return x.key; 191 } 192 193 private Node ceiling(Node x, K key) { 194 if (x == null) return null; 195 int cmp = key.compareTo(x.key); 196 if (cmp == 0) return x; 197 if (cmp < 0) { 198 Node t = ceiling(x.left, key); 199 if (t != null) return t; 200 else return x; 201 } 202 return ceiling(x.right, key); 203 } 204 205 /* ********************************************************************* 206 * Rank and selection 207 ***********************************************************************/ 208 public K select(int k) { 209 if (k < 0 || k >= size()) return null; 210 Node x = select(root, k); 211 return x.key; 212 } 213 214 // Return key of rank k. 215 private Node select(Node x, int k) { 216 if (x == null) return null; 217 int t = size(x.left); 218 if (t > k) return select(x.left, k); 219 else if (t < k) return select(x.right, k-t-1); 220 else return x; 221 } 222 223 public int rank(K key) { 224 return rank(key, root); 225 } 226 227 // Number of keys in the subtree less than x.key. 228 private int rank(K key, Node x) { 229 if (x == null) return 0; 230 int cmp = key.compareTo(x.key); 231 if (cmp < 0) return rank(key, x.left); 232 else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right); 233 else return size(x.left); 234 } 235 236 /* ********************************************************************* 237 * Range count and range search. 238 ***********************************************************************/ 239 public Iterable<K> keys() { 240 return keys(min(), max()); 241 } 242 243 public Iterable<K> keys(K lo, K hi) { 244 Queue<K> queue = new Queue<>(); 245 keys(root, queue, lo, hi); 246 return queue; 247 } 248 249 private void keys(Node x, Queue<K> queue, K lo, K hi) { 250 if (x == null) return; 251 int cmplo = lo.compareTo(x.key); 252 int cmphi = hi.compareTo(x.key); 253 if (cmplo < 0) keys(x.left, queue, lo, hi); 254 if (cmplo <= 0 && cmphi >= 0) queue.enqueue(x.key); 255 if (cmphi > 0) keys(x.right, queue, lo, hi); 256 } 257 258 public int size(K lo, K hi) { 259 if (lo.compareTo(hi) > 0) return 0; 260 if (contains(hi)) return rank(hi) - rank(lo) + 1; 261 else return rank(hi) - rank(lo); 262 } 263 264 265 // height of this XBSTWithStaticNode (one-node tree has height 0) 266 public int height() { return height(root); } 267 private int height(Node x) { 268 if (x == null) return -1; 269 return 1 + Math.max(height(x.left), height(x.right)); 270 } 271 272 /* *********************************************************************** 273 * Check integrity of XBSTWithStaticNode data structure 274 *************************************************************************/ 275 private boolean check() { 276 if (!isBST()) StdOut.println("Not in symmetric order"); 277 if (!isSizeConsistent()) StdOut.println("Subtree counts not consistent"); 278 if (!isRankConsistent()) StdOut.println("Ranks not consistent"); 279 return isBST() && isSizeConsistent() && isRankConsistent(); 280 } 281 282 // does this binary tree satisfy symmetric order? 283 // Note: this test also ensures that data structure is a binary tree since order is strict 284 private boolean isBST() { 285 return isBST(root, null, null); 286 } 287 288 // is the tree rooted at x a XBSTWithStaticNode with all keys strictly between min and max 289 // (if min or max is null, treat as empty constraint) 290 // Credit: Bob Dondero's elegant solution 291 private boolean isBST(Node x, K min, K max) { 292 if (x == null) return true; 293 if (min != null && x.key.compareTo(min) <= 0) return false; 294 if (max != null && x.key.compareTo(max) >= 0) return false; 295 return isBST(x.left, min, x.key) && isBST(x.right, x.key, max); 296 } 297 298 // are the size fields correct? 299 private boolean isSizeConsistent() { return isSizeConsistent(root); } 300 private boolean isSizeConsistent(Node x) { 301 if (x == null) return true; 302 if (x.N != size(x.left) + size(x.right) + 1) return false; 303 return isSizeConsistent(x.left) && isSizeConsistent(x.right); 304 } 305 306 // check that ranks are consistent 307 private boolean isRankConsistent() { 308 for (int i = 0; i < size(); i++) 309 if (i != rank(select(i))) return false; 310 for (K key : keys()) 311 if (key.compareTo(select(rank(key))) != 0) return false; 312 return true; 313 } 314 315 316 /* *************************************************************************** 317 * Test client 318 *****************************************************************************/ 319 public static void main(String[] args) { 320 XBSTWithNonStaticNode<String, Integer> st = new XBSTWithNonStaticNode<>(); 321 for (int i = 0; !StdIn.isEmpty(); i++) { 322 String key = StdIn.readString(); 323 st.put(key, i); 324 } 325 for (String s : st.keys()) 326 StdOut.println(s + " " + st.get(s)); 327 } 328}