1 package 查找;
  2 
  3 import edu.princeton.cs.algs4.Queue;
  4 import edu.princeton.cs.algs4.StdOut;
  5 
  6 public class BST<Key extends Comparable<Key>, Value> {
  7     private class Node {
  8         private Key key; // 键
  9         private Value value;// 值
 10         private Node left, right; // 指向子树的链接
 11         private int n; // 以该节点为根的子树中的节点总数
 12 
 13         public Node(Key key, Value val, int n) {
 14             this.key = key;
 15             this.value =http://www.mamicode.com/ val;
 16             this.n = n;
 17         }
 18     }
 19 
 20     private Node root;
 21 
 22     public int size() {
 23         return size(root);
 24     }
 25 
 26     private int size(Node x) {
 27         if (x == null)
 28             return 0;
 29         else
 30             return x.n;
 31     }
 32 
 33     /**
 34      * 如果树是空的，则查找未命中 如果被查找的键小于根节点，则在左子树中继续查找 如果被查找的键大于根节点，则在右子树中继续查找
 35      * 如果被查找的键和根节点的键相等，查找命中
 36      * 
 37      * @param key
 38      * @return
 39      */
 40     public Value get(Key key) {
 41         return get(root, key);
 42     }
 43 
 44     private Value get(Node x, Key key) {
 45         if (x == null)
 46             return null;
 47         int cmp = key.compareTo(x.key);
 48         if (cmp < 0)
 49             return get(x.left, key);
 50         else if (cmp > 0)
 51             return get(x.right, key);
 52         else
 53             return x.value;
 54     }
 55 
 56     /**
 57      * 二叉查找树的一个很重要的特性就是插入的实现难度和查找差不多。 当查找到一个不存在与树中的节点（null）时，new 新节点，并将上一路径指向该节点
 58      * 
 59      * @param key
 60      * @param val
 61      */
 62     public void put(Key key, Value val) {
 63         root = put(root, key, val);
 64     }
 65 
 66     private Node put(Node x, Key key, Value val) {
 67         if (x == null)
 68             return new Node(key, val, 1);
 69         int cmp = key.compareTo(x.key);
 70         if (cmp < 0)
 71             x.left = put(x.left, key, val);
 72         else if (cmp > 0)
 73             x.right = put(x.right, key, val);
 74         else
 75             x.value =http://www.mamicode.com/ val;
 76         x.n = size(x.left) + size(x.right); // 要及时更新节点的子树数量
 77         return x;
 78     }
 79 
 80     public Key min() {
 81         return min(root).key;
 82     }
 83 
 84     private Node min(Node x) {
 85         if (x.left == null)
 86             return x;
 87         return min(x.left);
 88     }
 89 
 90     public Key max() {
 91         return max(root).key;
 92     }
 93 
 94     private Node max(Node x) {
 95         if (x.right == null)
 96             return x;
 97         return min(x.right);
 98     }
 99 
100     /**
101      * 向下取整：找出小于等于该键的最大键
102      * 
103      * @param key
104      * @return
105      */
106     public Key floor(Key key) {
107         Node x = floor(root, key);
108         if (x == null)
109             return null;
110         else
111             return x.key;
112     }
113 
114     /**
115      * 如果给定的键key小于二叉查找树的根节点的键，那么小于等于key的最大键一定出现在根节点的左子树中
116      * 如果给定的键key大于二叉查找树的根节点，那么只有当根节点右子树中存在大于等于key的节点时，
117      * 小于等于key的最大键才会出现在右子树中，否则根节点就是小于等于key的最大键
118      * 
119      * @param x
120      * @param key
121      * @return
122      */
123     private Node floor(Node x, Key key) {
124         if (x == null)
125             return null;
126         int cmp = key.compareTo(x.key);
127         if (cmp == 0)
128             return x;
129         else if (cmp < 0)
130             return floor(x.left, key);
131         else {
132             Node t = floor(x.right, key);
133             if (t == null)
134                 return x;
135             else
136                 return t;
137         }
138     }
139 
140     /**
141      * 向上取整：找出大于等于该键的最小键
142      * 
143      * @param key
144      * @return
145      */
146     public Key ceiling(Key key) {
147         Node x = ceiling(root, key);
148         if (x == null)
149             return null;
150         else
151             return x.key;
152     }
153 
154     /**
155      * 如果给定的键key大于二叉查找树的根节点的键，那么大于等于key的最小键一定出现在根节点的右子树中
156      * 如果给定的键key小于二叉查找树的根节点，那么只有当根节点左子树中存在大于等于key的节点时，
157      * 大于等于key的最小键才会出现在左子树中，否则根节点就是大于等于key的最小键
158      * 
159      * @param x
160      * @param key
161      * @return
162      */
163     private Node ceiling(Node x, Key key) {
164         if (x == null)
165             return null;
166         int cmp = key.compareTo(x.key);
167         if (cmp == 0)
168             return x;
169         else if (cmp > 0) {
170             return ceiling(x.right, key);
171         } else {
172             Node t = floor(x.left, key);
173             if (t == null)
174                 return x;
175             else
176                 return t;
177         }
178     }
179 
180     /**
181      * 选择排名为k的节点
182      * 
183      * @param k
184      * @return
185      */
186     public Key select(int k) {
187         return select(root, k).key;
188     }
189 
190     private Node select(Node x, int k) {
191         if (x == null)
192             return null;
193         int t = size(x.left);
194         if (t > k)
195             return select(x.left, k);
196         else if (t < k)
197             return select(x.right, k - t - 1);// 根节点也要排除掉
198         else
199             return x;
200     }
201 
202     /**
203      * 查找给定键值的排名
204      * 
205      * @param key
206      * @return
207      */
208     public int rank(Key key) {
209         return rank(key, root);
210     }
211 
212     private int rank(Key key, Node x) {
213         if (x == null)
214             return 0;
215         int cmp = key.compareTo(x.key);
216         if (cmp < 0)
217             return rank(key, x.left);
218         else if (cmp > 0)
219             return 1 + size(x.left) + rank(key, x.right);
220         else
221             return size(x.left);
222     }
223     /**
224      * 删除最小键值对
225      */
226     public void deleteMin(){
227         root = deleteMin(root);
228     }
229     /**
230      * 不断深入根节点的左子树直到遇见一个空链接，然后将指向该节点的链接指向该结点的右子树
231      * 此时已经没有任何链接指向要被删除的结点，因此它会被垃圾收集器清理掉
232      * @param x
233      * @return
234      */
235     private Node deleteMin(Node x){
236         if(x.left == null) return x.right;
237         x.left = deleteMin(x.left);
238         x.n = size(x.left)+size(x.right) + 1;
239         return x;
240     }
241     
242     public void deleteMax(){
243         root = deleteMax(root);
244     }
245     private Node deleteMax(Node x){
246         if(x.right == null ) return x.left;
247         x.right = deleteMax(x.right);
248         x.n = size(x.left)+size(x.right) + 1;
249         return x;
250     }
251     
252     public void delete(Key key){
253         root = delete(root,key);
254     }
255     private Node delete(Node x, Key key){
256         if(x == null) return null;
257         int cmp = key.compareTo(x.key);
258         if(cmp < 0) x.left = delete(x.left,key);
259         else if(cmp > 0) x.right = delete(x.right,key);
260         else{
261             if(x.right == null) return x.left;
262             if(x.left == null ) return x.right;
263             /**
264              * 如果被删除节点有两个子树，将被删除节点暂记为t
265              * 从t的右子树中选取最小的节点x，将这个节点x的左子树设为t的左子树
266              * 这个节点x的右子树设为t的右子树中删除了最小节点的子树，这样就成功替换了t的位置
267              */
268             Node t = x;
269             x = min(t.right);
270             x.left = t.left;
271             x.right = deleteMin(t.right);
272         }
273         x.n = size(x.left) + size(x.right) +1;
274         return x;
275     }
276     
277     public void print(){
278         print(root);
279     }
280     private void print(Node x){
281         if(x == null ) return;
282         print(x.left);
283         StdOut.println(x.key);
284         print(x.right);
285     }
286     
287     public Iterable<Key> keys(){
288         return keys(min(),max());
289     }
290     public Iterable<Key> keys(Key lo, Key hi){
291         Queue<Key> queue = new Queue<Key>();
292         keys(root, queue, lo, hi);
293         return queue;
294     }
295     private void keys(Node x, Queue<Key> queue, Key lo, Key hi){
296         if(x == null) return;
297         int cmplo = lo.compareTo(x.key);
298         int cmphi = lo.compareTo(x.key);
299         if(cmplo < 0 ) keys(x.left,queue,lo,hi);
300         if(cmplo <= 0 && cmphi >= 0) queue.enqueue(x.key);
301         if(cmphi > 0 ) keys(x.right,queue,lo,hi);
302     }
303 }