001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
package algs33;
import stdlib.*;
import java.util.Iterator;
import java.util.NoSuchElementException;
import algs13.Stack;
/* ***********************************************************************
 *  Compilation:  javac RandomizedBST.java
 *  Execution:    java RandomizedBST
 *
 *  Symbol table (map) implemented with a randomized BST.
 *
 *
 *************************************************************************/

public class XRandomizedBST<K extends Comparable<? super K>, V> implements Iterable<K> {

  private Node<K,V> root;   // root of the BST

  // BST helper node data type
  private static class Node<K,V> {
    public K key;          // key
    public V val;          // associated data
    public Node<K,V> left, right;   // left and right subtrees
    public int N;              // node count of descendents

    public Node(K key, V val) {
      this.key = key;
      this.val = val;
      this.N   = 1;
    }
  }


  /* ***********************************************************************
   *  BST search
   *************************************************************************/

  public boolean contains(K key) {
    return (get(key) != null);
  }

  // return value associated with the given key
  // if no such value, return null
  // if multiple such values, return first one on path from root
  public V get(K key) {
    return get(root, key);
  }

  private V get(Node<K,V> x, K key) {
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if      (cmp == 0) return x.val;
    else if (cmp  < 0) return get(x.left,  key);
    else               return get(x.right, key);
  }


  /* ***********************************************************************
   *  randomized insertion
   *************************************************************************/
  public void put(K key, V val) {
    root = put(root, key, val);
  }

  // make new node the root with uniform probability
  private Node<K,V> put(Node<K,V> x, K key, V val) {
    if (x == null) return new Node<>(key, val);
    int cmp = key.compareTo(x.key);
    if (cmp == 0) { x.val = val; return x; }
    if (StdRandom.bernoulli(1.0 / (size(x) + 1.0))) return putRoot(x, key, val);
    if (cmp < 0) x.left  = put(x.left,  key, val);
    else         x.right = put(x.right, key, val);
    // (x.N)++;
    fix(x);
    return x;
  }


  private Node<K,V> putRoot(Node<K,V> x, K key, V val) {
    if (x == null) return new Node<>(key, val);
    int cmp = key.compareTo(x.key);
    if      (cmp == 0) { x.val = val; return x; }
    else if (cmp  < 0) { x.left  = putRoot(x.left,  key, val); x = rotR(x); }
    else               { x.right = putRoot(x.right, key, val); x = rotL(x); }
    return x;
  }



  /* ***********************************************************************
   *  deletion
   *************************************************************************/
  private Node<K,V> joinLR(Node<K,V> a, Node<K,V> b) {
    if (a == null) return b;
    if (b == null) return a;

    if (StdRandom.bernoulli((double) size(a) / (size(a) + size(b))))  {
      a.right = joinLR(a.right, b);
      fix(a);
      return a;
    }
    else {
      b.left = joinLR(a, b.left);
      fix(b);
      return b;
    }
  }

  private Node<K,V> remove(Node<K,V> x, K key) {
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if      (cmp == 0) x = joinLR(x.left, x.right);
    else if (cmp  < 0) x.left  = remove(x.left,  key);
    else               x.right = remove(x.right, key);
    fix(x);
    return x;
  }

  // remove and return value associated with given key; if no such key, return null
  public V remove(K key) {
    V val = get(key);
    root = remove(root, key);
    return val;
  }

  /* ***********************************************************************
   *  Selection
   *************************************************************************/

  // return the kth largest key
  public K select(int k) { Node<K,V> x = select(root, k); return x.key; }
  private Node<K,V> select(Node<K,V> x, int k) {
    if (x == null) return null;
    int t = size(x.left);
    if      (t > k) return select(x.left,  k);
    else if (t < k) return select(x.right, k-t-1);
    else            return x;
  }



  // return the smallest key
  public K min() {
    K key = null;
    for (Node<K,V> x = root; x != null; x = x.left)
      key = x.key;
    return key;
  }

  // return the largest key
  public K max() {
    K key = null;
    for (Node<K,V> x = root; x != null; x = x.right)
      key = x.key;
    return key;
  }

  // return the smallest key >= query key; if no such key return null
  public K ceil(K key) {
    Node<K,V> best = ceil(root, key, null);
    if (best == null) return null;
    return best.key;
  }
  private Node<K,V> ceil(Node<K,V> x, K key, Node<K,V> best) {
    if      (x == null)        return best;
    else if (eq(key, x.key))   return x;
    else if (less(key, x.key)) return ceil(x.left,  key, x);
    else                       return ceil(x.right, key, best);
  }

  // return the smallest key >= query key; if no such key return null
  public K ceil2(K key) {
    Node<K,V> best = null;
    Node<K,V> x = root;
    while (x != null) {
      int cmp = key.compareTo(x.key);
      if      (cmp < 0) { best = x; x = x.left; }
      else if (cmp > 0) { x = x.right;          }
      else              return x.key;
    }
    if (best == null) return null;
    return best.key;
  }


  /* *********************************************************************
   *  Iterate using inorder traversal using a stack.
   *  Iterating through N elements takes O(N) time.
   ***********************************************************************/
  public Iterator<K> iterator() { return new BSTIterator(root); }

  // an iterator
  private class BSTIterator implements Iterator<K> {
    private Stack<Node<K,V>> stack = new Stack<>();

    public BSTIterator(Node<K,V> x) {
      while (x != null) {
        stack.push(x);
        x = x.left;
      }
    }

    public boolean hasNext()  { return !stack.isEmpty();                    }

    // it's optional and we don't want to support it
    public void remove()      { throw new UnsupportedOperationException();  }

    public K next() {
      if (!hasNext()) throw new NoSuchElementException();
      Node<K,V> x = stack.pop();
      K key = x.key;
      x = x.right;
      while (x != null) {
        stack.push(x);
        x = x.left;
      }
      return key;
    }
  }




  /* ***********************************************************************
   *  Utility functions.
   *************************************************************************/

  // return number of nodes in subtree rooted at x
  public int size() { return size(root); }
  private int size(Node<K,V> x) {
    if (x == null) return 0;
    else           return x.N;
  }

  // height of tree (empty tree height = 0)
  public int height() { return height(root); }
  private int height(Node<K,V> x) {
    if (x == null) return 0;
    return 1 + Math.max(height(x.left), height(x.right));
  }


  /* ***********************************************************************
   *  helper BST functions
   *************************************************************************/

  // fix subtree count field
  private void fix(Node<K,V> x) {
    if (x == null) return;
    x.N = 1 + size(x.left) + size(x.right);
  }

  // right rotate
  private Node<K,V> rotR(Node<K,V> h) {
    Node<K,V> x = h.left;
    h.left = x.right;
    x.right = h;
    fix(h);
    fix(x);
    return x;
  }

  // left rotate
  private Node<K,V> rotL(Node<K,V> h) {
    Node<K,V> x = h.right;
    h.right = x.left;
    x.left = h;
    fix(h);
    fix(x);
    return x;
  }


  /* ***********************************************************************
   *  Debugging functions that test the integrity of the tree
   *************************************************************************/

  // check integrity of subtree count fields
  public boolean check() { return checkCount() && isBST(); }

  // check integrity of count fields
  private boolean checkCount() { return checkCount(root); }
  private boolean checkCount(Node<K,V> x) {
    if (x == null) return true;
    return checkCount(x.left) && checkCount(x.right) && (x.N == 1 + size(x.left) + size(x.right));
  }


  // does this tree satisfy the BST property?
  private boolean isBST() { return isBST(root, min(), max()); }

  // are all the values in the BST rooted at x between min and max, and recursively?
  private boolean isBST(Node<K,V> x, K min, K max) {
    if (x == null) return true;
    if (less(x.key, min) || less(max, x.key)) return false;
    return isBST(x.left, min, x.key) && isBST(x.right, x.key, max);
  }



  /* ***********************************************************************
   *  helper comparison functions
   *************************************************************************/

  private boolean less(K k1, K k2) {
    return k1.compareTo(k2) < 0;
  }

  private boolean eq(K k1, K k2) {
    return k1.compareTo(k2) == 0;
  }



  /* ***********************************************************************
   *  test client
   *************************************************************************/
  public static void main(String[] args) {
    XRandomizedBST<String, String> st = new XRandomizedBST<>();

    // insert some key-value pairs
    st.put("www.cs.princeton.edu",   "128.112.136.11");
    st.put("www.cs.princeton.edu",   "128.112.136.35");    // overwrite old value
    st.put("www.princeton.edu",      "128.112.130.211");
    st.put("www.math.princeton.edu", "128.112.18.11");
    st.put("www.yale.edu",           "130.132.51.8");
    st.put("www.amazon.com",         "207.171.163.90");
    st.put("www.simpsons.com",       "209.123.16.34");
    st.put("www.stanford.edu",       "171.67.16.120");
    st.put("www.google.com",         "64.233.161.99");
    st.put("www.ibm.com",            "129.42.16.99");
    st.put("www.apple.com",          "17.254.0.91");
    st.put("www.slashdot.com",       "66.35.250.150");
    st.put("www.whitehouse.gov",     "204.153.49.136");
    st.put("www.espn.com",           "199.181.132.250");
    st.put("www.snopes.com",         "66.165.133.65");
    st.put("www.movies.com",         "199.181.132.250");
    st.put("www.cnn.com",            "64.236.16.20");
    st.put("www.iitb.ac.in",         "202.68.145.210");


    StdOut.println(st.get("www.cs.princeton.edu"));
    StdOut.println(st.get("www.harvardsucks.com"));
    StdOut.println(st.get("www.simpsons.com"));
    StdOut.println();

    StdOut.println("integrity check: " + st.check());
    StdOut.println();

    StdOut.println("ceil(www.simpsonr.com) = " + st.ceil("www.simpsonr.com"));
    StdOut.println("ceil(www.simpsons.com) = " + st.ceil("www.simpsons.com"));
    StdOut.println("ceil(www.simpsont.com) = " + st.ceil("www.simpsont.com"));

    StdOut.println("ceil(www.simpsonr.com) = " + st.ceil2("www.simpsonr.com"));
    StdOut.println("ceil(www.simpsons.com) = " + st.ceil2("www.simpsons.com"));
    StdOut.println("ceil(www.simpsont.com) = " + st.ceil2("www.simpsont.com"));
    StdOut.println();

    for (int i = 0; i < st.size(); i++) {
      StdOut.println(i + "th: key  " + st.select(i));
    }
    StdOut.println();

    StdOut.println("min key: " + st.min());
    StdOut.println("max key: " + st.max());
    StdOut.println("size:    " + st.size());
    StdOut.println("height:  " + st.height());
    StdOut.println();
  }

}