二叉查找树(BST)的实现

 1 public class BSTNode<K, V> {
 2     public K key;
 3     public V value;
 4     public BSTNode<K, V> left;
 5     public BSTNode<K, V> right;
 6     public BSTNode<K, V> parent;
 7     public boolean isLeftChild;
 8     public int height;
 9     public int num;
10     public boolean isRed = true;  // 后面才学习的红黑树
11 
12     public BSTNode() {
13     }
14 
15     public BSTNode(K key, V value, BSTNode<K, V> left, BSTNode<K, V> right, BSTNode<K, V> parent) {
16         super();
17         this.key = key;
18         this.value = value;
19         this.left = left;
20         this.right = right;
21         this.parent = parent;
22     }
23 
24     public boolean isLeft() {
25         return isLeftChild;
26     }
27 
28     public boolean isRight() {
29         return !isLeftChild;
30     }
31 
32     @Override
33     public String toString() {
34         return (isRed ? "红色" : "黑色") + " [" + key + "]<-" + (parent == null ? "" : parent.key);
35     }
36 }

 1 import java.util.List;
 2 import java.util.function.Consumer;
 3 
 4 public interface IBinarySearchTree<K, V> {
 5     /**
 6      * 新增节点
 7      * @param k 关键字
 8      * @param v 值
 9      */
10     BSTNode<K, V> insert(K k, V v);
11 
12     /**
13      * 中序遍历
14      * @param con 处理中序遍历的每个元素的函数
15      */
16     void inorder(Consumer<K> con);
17 
18     /**
19      * 查找元素
20      * @param key
21      * @return
22      */
23     V lookupValue(K key);
24 
25     /**
26      * 获取最小关键字
27      * @return
28      */
29     K min();
30 
31     /**
32      * 获取最大关键字
33      * @return
34      */
35     K max();
36 
37     /**
38      * 移除关键字对应的节点
39      * @param key
40      */
41     void remove(K key);
42 
43     /**
44      * x的后继——比x大的第一个元素 1、是其右子树的最小值
45      * 2、没有右子树，则向上追溯，直到某个祖先节点是左孩子，返回这个祖先节点的父节点，它就是x的后继
46      * 
47      * @param x
48      * @return
49      */
50     K successor(K x);
51 
52     /**
53      * 前驱
54      * @param x 关键字
55      * @return
56      */
57     K predecessor(K x);
58 
59     boolean isBalance();
60 
61     /**
62      * 返回节点数
63      * @return
64      */
65     int getSize();
66 
67     /**
68      * 高度
69      * @return
70      */
71     int getHeight();
72 
73     List<List<BSTNode<K, V>>> levelOrder();
74 }

  1 import java.util.ArrayList;
  2 import java.util.Comparator;
  3 import java.util.LinkedList;
  4 import java.util.List;
  5 import java.util.Queue;
  6 import java.util.Stack;
  7 import java.util.function.Consumer;
  8 
  9 /**
 10  * 二叉搜索树
 11  *
 12  */
 13 public class BinarySearchTree<K, V> implements IBinarySearchTree<K, V> {
 14   /**
 15    * 根节点
 16    */
 17   protected BSTNode root;
 18   /**
 19    * 元素个数
 20    */
 21   protected int size;
 22   private Comparator comparator;
 23 
 24   public BinarySearchTree() {
 25   }
 26 
 27   public BinarySearchTree(Comparator comparator) {
 28     this.comparator = comparator;
 29   }
 30 
 31 
 32   // parent curr 双指针
 33   @Override
 34   public BSTNode<K, V> insert(K key, V value) {
 35     if (!(key instanceof Comparable)) {
 36       throw new ClassCastException();
 37     }
 38 
 39     BSTNode<K, V> parent = null;
 40     BSTNode<K, V> curr = root;
 41     while (curr != null) {
 42       parent = curr;
 43       if (compare(key, curr.key) < 0) {
 44         curr = curr.left;
 45       } else if (compare(key, curr.key) > 0) {
 46         curr = curr.right;
 47       } else {
 48         curr.value = value;
 49         return curr;
 50       }
 51     }
 52     curr = new BSTNode(key, value, null, null, null);
 53     //link current to parent
 54     curr.parent = parent;
 55     if (parent == null) {
 56       root = curr;
 57     } else if (compare(key, parent.key) < 0) {
 58       parent.left = curr;
 59       curr.isLeftChild = true;
 60     } else {
 61       parent.right = curr;
 62       curr.isLeftChild = false;
 63     }
 64 
 65     size++;
 66     updateHeight(curr);
 67     return curr;
 68   }
 69 
 70   private void updateHeight(BSTNode<K, V> curr) {
 71     if (curr.parent == null) return;//util root
 72 
 73     BSTNode<K, V> p = curr.parent;
 74     if (p.height == curr.height) {
 75       p.height++;
 76       updateHeight(p);//递归
 77     }
 78   }
 79 
 80   @SuppressWarnings({"unchecked", "rawtypes"})
 81   private int compare(K key1, K key2) {
 82     if (null == comparator) {
 83       return ((Comparable) key1).compareTo((Comparable) key2);
 84     } else {
 85       return comparator.compare(key1, key2);
 86     }
 87   }
 88 
 89   /**
 90    * 中序遍历
 91    * @param con 处理中序遍历的每个元素的函数
 92    */
 93   @Override
 94   public void inorder(Consumer<K> con) {
 95     if (root != null)
 96       // inorder2(root, con);
 97       inorder(root, con);
 98   }
 99 
100   /* 递归形式 */
101   private void inorder(BSTNode<K, V> p, Consumer<K> con) {
102     if (p != null) {
103       inorder(p.left, con);
104       con.accept(p.key);
105       inorder(p.right, con);
106     }
107   }
108 
109   /*迭代形式*/
110   private void inorder2(BSTNode<K, V> p, Consumer<K> con) {
111     Stack<BSTNode<K, V>> stack = new Stack<>();
112     BSTNode<K, V> curr = p;
113     //curr不为空或者栈不为空，都可以继续处理
114     while (curr != null || !stack.isEmpty()) {//没有生产也没有消费，就退出循环了
115       //沿左支线一撸到底，全部入栈
116       while (curr != null) {
117         stack.push(curr);
118         curr = curr.left;
119       }
120       //处理栈顶
121       if (!stack.isEmpty()) {
122         BSTNode<K, V> pop = stack.pop();
123         con.accept(pop.key);
124         //  curr指向pop的右子树，继续外层循环
125         curr = pop.right;//有可能为空，为空，只消费栈中内容，不为空，就要向栈中生产若干内容
126       }
127     }
128   }
129   
130   // 二叉查找树查找之所以快 每次丢弃一半  lgn
131   @Override
132   public V lookupValue(K key) {
133     BSTNode<K, V> lookupNode = lookupNode(key);
134     return lookupNode == null ? null : lookupNode.value;
135   }
136 
137   protected BSTNode<K, V> lookupNode(K key) {
138     BSTNode<K, V> p = root;
139     //只要p不为空，并且没找到
140     while (p != null && compare(key, p.key) != 0) {
141       if (compare(key, p.key) < 0)
142         p = p.left;
143       else
144         p = p.right;
145     }
146     return p;
147   }
148 
149   // 最左边的结点
150   @Override
151   public K min() {
152     return minNode(root).key;
153   }
154 
155   protected BSTNode<K, V> minNode(BSTNode p) {
156     while (p.left != null) {
157       p = p.left;
158     }
159     return p;
160   }
161 
162   // 最右边的结点
163   @Override
164   public K max() {
165     return maxNode(root).key;
166   }
167 
168   protected BSTNode<K, V> maxNode(BSTNode p) {
169     while (p.right != null) {
170       p = p.right;
171     }
172     return p;
173   }
174 
175   /*右单旋
176   *   p
177   *   q
178   *   */
179   protected void rightRotate(BSTNode p, BSTNode q) {
180     boolean pIsLeft = p.isLeft();
181     BSTNode pp = p.parent;
182 
183     BSTNode x = q.right;
184     p.left = x;
185     if (x != null) {
186       x.parent = p;
187       x.isLeftChild = true;
188     }
189     q.right = p;
190     p.parent = q;
191     p.isLeftChild = false;
192 
193 
194     //设定p和gg的关系
195     q.parent = pp;
196     if (pp == null) {
197       root = q;
198       return;
199     }
200     if (pIsLeft) {
201       pp.left = q;
202       q.isLeftChild = true;
203     } else {
204       pp.right = q;
205       q.isLeftChild = false;
206     }
207   }
208 
209   /*左单旋*/
210   protected void leftRotate(BSTNode p, BSTNode q) {
211     boolean pIsLeft = p.isLeft();
212     BSTNode pp = p.parent;
213     //p和q的左子——B的关系
214     BSTNode B = q.left;
215     p.right = B;
216     if (B != null) {
217       B.parent = p;
218       B.isLeftChild = false;
219     }
220 
221     //p，q的关系
222     q.left = p;
223     p.parent = q;
224     p.isLeftChild = true;
225 
226     //p和pp的关系
227     q.parent = pp;
228     //p是根节点
229     if (pp == null) {
230       root = q;
231       return;
232     }
233 
234     if (pIsLeft) {
235       pp.left = q;
236       q.isLeftChild = true;
237     } else {
238       pp.right = q;
239       q.isLeftChild = false;
240     }
241   }
242 
243   @Override
244   public void remove(K key) {
245     removeNode(lookupNode(key));
246     size--;// 记得减少元素个数
247   }
248 
249   protected void removeNode(BSTNode<K, V> x) {
250     if (x != null) {
251       if (x.left == null && x.right == null) {// leaf node.  第一种情况 没有子节点
252         if (x.parent == null) {
253           root = null;
254           return;
255         }
256         if (x.isLeftChild) {
257           x.parent.left = null;
258         } else {
259           x.parent.right = null;
260         }
261         x.parent = null;
262         x = null;
263       } else if (x.left == null) {// 第二种情况 有子节点,但左子为空,有右孩子
264         if (x.isLeftChild) {
265           BSTNode<K, V> c = x.right;
266           BSTNode<K, V> parent = x.parent;
267           parent.left = c;
268           c.isLeftChild = true;
269           c.parent = parent;
270         } else {
271           if (x.parent != null) {
272             x.parent.right = x.right;
273             x.right.parent = x.parent;
274           } else {// 根节点
275             root = x.right;
276           }
277         }
278         x = null;
279       } else if (x.right == null) {// 第三种情况 有子节点,但右子为空，有左孩子
280         if (x.isLeftChild) {
281           x.parent.left = x.left;
282           x.left.parent = x.parent;
283         } else {
284           if (x.parent != null) {
285             x.parent.right = x.left;
286             x.left.isLeftChild = false;
287             x.left.parent = x.parent;
288           } else { // 根节点
289             root = x.left;
290           }
291         }
292         x = null;
293       } else {                // 第四种情况 都不为空
294         BSTNode<K, V> minOfRight = minNode(x.right);
295         x.key = minOfRight.key;// 更换x的内容
296         removeNode(minOfRight); // 删掉右子树种最小的元素
297       }
298     }
299   }
300 
301 
302   // 有右子树 ，则后继为右子树最小
303   // 否则往上回溯，找到一个是左结点的祖先，则后继是该结点的父亲
304   @Override
305   public K successor(K x) {
306     BSTNode<K, V> xNode = lookupNode(x);
307     if (xNode == null) {
308       return null;
309     }
310     BSTNode<K, V> yNode = successor(xNode);
311     return yNode == null ? null : yNode.key;
312 
313   }
314 
315   protected BSTNode<K, V> successor(BSTNode<K, V> xNode) {
316     if (xNode == null) {
317       return null;
318     }
319     if (xNode.right != null) {
320       return minNode(xNode.right);
321     }
322     BSTNode<K, V> yNode = xNode.parent;
323     while (yNode != null && xNode == yNode.right) {
324       xNode = yNode;
325       yNode = yNode.parent;
326     }
327     return yNode;
328   }
329 
330   // 与找后继结点对称
331   @Override
332   public K predecessor(K x) {
333     BSTNode<K, V> xNode = lookupNode(x);
334     if (xNode == null) {
335       return null;
336     }
337     if (xNode.left != null) {
338       return maxNode(xNode.left).key;
339     }
340     BSTNode<K, V> yNode = xNode.parent;
341     while (yNode != null && xNode.isLeftChild) {
342       xNode = yNode;
343       yNode = yNode.parent;
344     }
345     return yNode == null ? null : yNode.key;
346   }
347 
348   @Override
349   public boolean isBalance() {
350     return !unBalance(root);
351   }
352 
353   protected boolean unBalance(BSTNode g) {
354     if (g == null) return false;
355     int minus = getHeight(g.left) - getHeight(g.right);
356     return Math.abs(minus) > 1
357         || unBalance(g.right)
358         || unBalance(g.left);
359   }
360 
361 
362 
363   /**
364    * 获取树的节点数
365    * @return
366    */
367   @Override
368   public int getSize() {
369     return size;
370   }
371 
372   @Override
373   public int getHeight() {
374     return getHeight(root);
375   }
376 
377   protected int getHeight(BSTNode node) {
378     if (node == null) return 0;
379     int l = getHeight(node.left);
380     int r = getHeight(node.right);
381     return 1 + Math.max(l, r);
382   }
383 
384 
385   public List<List<BSTNode<K, V>>> levelOrder(BSTNode<K, V> x) {
386     // int num=x.num;//累进的编号
387     List<List<BSTNode<K, V>>> res = new ArrayList<>();
388     Queue<BSTNode<K, V>> q = new LinkedList<>();
389     q.add(x);
390     BSTNode<K, V> last = x;
391     BSTNode<K, V> nLast = null;
392     List<BSTNode<K, V>> l = new ArrayList<>();
393     res.add(l);
394     while (!q.isEmpty()) {
395       BSTNode<K, V> peek = q.peek();
396       //把即将弹出的节点的子节点加入队列
397       if (peek.left != null) {
398         peek.left.num = peek.num * 2;
399         q.add(peek.left);
400         nLast = peek.left;
401       }
402       if (peek.right != null) {
403         peek.right.num = peek.num * 2 + 1;
404         q.add(peek.right);
405         nLast = peek.right;
406       }
407 
408       l.add(q.poll());//弹出,加入到当前层列表
409       if (peek == last && !q.isEmpty()) {//如果现在弹出的节点是之前标记的最后节点，就要换列表
410         l = new ArrayList<>();
411         res.add(l);
412         last = nLast;
413       }
414     }
415     return res;
416   }
417 
418 
419   // 层次遍历
420   @Override
421   public List<List<BSTNode<K, V>>> levelOrder() {
422     root.num = 1;
423     return levelOrder(root);
424   }
425 
426   // 按照格式打印
427   @Override
428   public String toString() {
429     StringBuilder res = new StringBuilder();
430     List<List<BSTNode<K, V>>> lists = levelOrder();
431     int level = 1;
432     int height = getHeight();
433     for (List<BSTNode<K, V>> l :
434         lists) {
435       int gap = ex(2, height - level) - 1;//gap
436       // printGap(gap);//打印左边margin
437       int beginNum = ex(2, level - 1);
438       for (BSTNode<K, V> node : l) {
439         while (beginNum != node.num) {
440           //打印gap
441           for (int i = 0; i < 2 * gap; i++) {
442             res.append(" ");
443           }
444           res.append("**");
445           //打印gap
446           for (int i = 0; i < 2 * gap; i++) {
447             res.append(" ");
448           }
449           res.append("  ");
450           beginNum++;
451         }
452         //打印gap
453         for (int i = 0; i < 2 * gap; i++) {
454           res.append(" ");
455         }
456         res.append(node.key);
457         //打印gap
458         for (int i = 0; i < 2 * gap; i++) {
459           res.append(" ");
460         }
461         res.append("  ");
462 
463         beginNum++;
464       }
465       level++;
466       res.append("
");
467     }
468     return res.toString();
469   }
470 
471   private void printGap(int margin) {
472     for (int i = 0; i < margin; i++) {
473       System.out.print(" ");
474     }
475   }
476 
477   private void printGap(int gap, String s, int gap1) {
478     for (int i = 0; i < gap; i++) {
479       System.out.print(" ");
480     }
481     System.out.printf("%2s", s);
482     for (int i = 0; i < gap; i++) {
483       System.out.print(" ");
484     }
485 
486   }
487 
488     public static int ex(int a, int n) {
489         if (n == 0)
490             return 1;
491         if (n == 1)
492             return a;
493         int temp = a; // a 的 1 次方
494         int res = 1;
495         int exponent = 1;
496         while ((exponent << 1) < n) {
497             temp = temp * temp;
498             exponent = exponent << 1;
499         }
500 
501         res *= ex(a, n - exponent);
502 
503         return res * temp;
504     }
505 }