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}