查詢演算法之——二叉查詢樹（圖文分析）
摘要：
一、資料結構
二叉查詢樹基於二叉樹，每個節點儲存著鍵和值，以及指向左右子樹的連結，一顆二叉查詢樹代表了一組鍵值對的集合，類似於python中的字典（字典中的鍵值對儲存是無序的）。在這裡我們規定節點左子樹中的節點的鍵都小於它，右子樹中的節點都大於它，如果我們將所有節點向下投影到一條線上，可以...
一、資料結構
二叉查詢樹基於二叉樹，每個節點儲存著鍵和值，以及指向左右子樹的連結，一顆二叉查詢樹代表了一組鍵值對的集合，類似於python中的字典（字典中的鍵值對儲存是無序的）。在這裡我們規定節點左子樹中的節點的鍵都小於它，右子樹中的節點都大於它，如果我們將所有節點向下投影到一條線上，可以得到一條有序的序列。
二、主要方法（預設為遞迴實現）
部分方法的迭代實現在末尾展示
1、查詢和排序
在符號表中查詢一個鍵，從根節點開始，如果節點的鍵和被查詢的鍵相等，就返回節點的值，如果節點的值大於被查詢的鍵的值，就在節點的左子樹中查詢，反之在右子樹中查詢，直到節點為空或查詢命中。如果鍵在符號表中則查詢命中，返回鍵對應的值，如果 鍵不在符號表中則未命中，返回null（null為指向一個它可能會存在的空節點的連結）
在上一篇結尾處引入的方法有許多都用到了這個演算法：
1 public Value get(Key key) {// 通過鍵從符號表中獲取對應的值，返回鍵key對應的值
2return get(root, key);
3}
4
5private Value get(Node x, Key key) {// 遞迴
6if (key == null) {
7return null;
8}
9int cmp = key.compareTo(x.key);
10if (cmp < 0) {
11return get(x.left, key);
12} else if (cmp > 0) {
13return get(x.right, key);
14} else
15return x.val;
16}
17
18
19public void put(Key key, Value val) {//修改或新增節點
20root = put(root, key, val);
21}
22
23private Node put(Node x, Key key, Value val) {
24if (x == null) {// 建立新節點
25return new Node(key, val, 1);
26}
27int cmp = key.compareTo(x.key);
28if (cmp < 0) {
29x.left = put(x.left, key, val);
30} else if (cmp > 0) {
31x.right = put(x.right, key, val);
32} else {
33x.val = val;
34}
35x.N = size(x.left) + size(x.right) + 1;
36return x;// 在插入結束時返回（更新節點的相關資訊）
37}
其中的size（）方法表示以節點為根節點的子樹的節點數：
1public int size() {
2return size(root);
3}
4
5private int size(Node x) {
6if (x != null) {
7return x.N;
8} else {
9return 0;
10}
11}
size（）的遞迴實現需要理解其執行細節
由於是遞迴實現，程式碼第35將會從查詢經過的路徑由下至上，更新每個節點計數器的值。
在最壞情況下，一顆有n個節點的二叉樹到根節點的距離為n，最好情況下，每條空連結和根節點的距離都為lgN。大家可以想象一下這兩種情況下樹的樣子。
下面請讀者思考用遞迴的形式完成查詢最小鍵和在樹中查詢小於等於key的最大鍵兩個方法。
1public Key min() {
2return min(root).key;
3}
4public Node min(Node x) {
5if(x.left==null) {
6return x;
7}else {
8return min(x.left);
9}
10}
1public Key floor(Key key) {
2Node x== floor(root,key);
3if(x==null) {
4return null;
5}else {
6return x.key;
7}
8}
9
10public Node floor(Node x,key) {
11if (x == null) {
12return null;
13}
14int cmp=key.compareto(x.key);
15if(cmp<0) {
16return floor(x.left,key);
17}
18Node t=floor(x.right,key);
19if(t!=null) {
20return t;
21}else {
22return x;
23}
24}
與之相反的max和ceiling（返回大於等於key的最小鍵）方法，實現原理相同。請讀者當做練習實現，參考最後的程式碼展示。
2、排名
下面我們將要實現兩個重要的方法，rank和select，select方法的引數是一個整型，他將返回排名為這個整型的鍵，而rank和select相反，引數為一個鍵，返回的是這個鍵的排名。
select和rank是在size的基礎上實現的。
1public Key select(int k) {// 返回排名為k的鍵
2return select(root, k).key;
3}
4
5private Node select(Node x, int k) {// 返回排名為k的節點
6if (x == null) {
7return null;
8}
9int t = size(x.left);
10if (t > k) {
11return select(x.left, k);
12} else if (t < k) {
13return select(x.right, k - t - 1);
14} else {
15return x;
16}
17}
1 public int rank(Key key) {// 返回key的排名
2return rank(key, root);
3}
4
5private int rank(Key key, Node x) {
6if (key == null) {
7return 0;
8}
9int cmp = key.compareTo(x.key);
10if (cmp < 0) {
11return rank(key, x.left);
12} else if (cmp > 0) {
13return rank(key, x.right) + size(x.left) + 1;//注意體會這個+1
14} else {
15return size(x.left);
16}
17}
rank和put有點像，都是先不斷比較確定鍵的位置，不過rank返回的是下一次的遞迴加上已經確定的排名。
3、刪除
deleteMin為刪除最小節點，任何情況下，最小節點只可能有右子樹，所以在執行操作時只需將被最小節點的右節點代替最小節點即可。（刪除最大節點與此類似）
1 public void deleteMin() {
2root = deleteMin(root);
3}
4
5private Node deleteMin(Node x) {
6if (x.left == null) {
7return x.right;
8}
9x.left = deleteMin(x.left);
10x.N = size(x.left) + size(x.right) + 1;//由於刪除操作，所以需要更新路徑上節點的計數器
11return x;// 在刪除結束後返回節點的相關資訊
12}
請體會這裡第10、11行程式碼，理解執行細節
分析：返回和傳入相同，例如deleteMin（x），最後返回的將是x節點，但此時節點包含的資訊已經改變，因為要更新x.N，實際執行會從被刪除節點的上一個節點開始，由下至上進行更新，需要確定的是，刪除和返回操作都是在同一條路徑上進行的，沒經過的路徑將保持不變。
如果被刪除的節點左右節點都存在，操作將變得複雜，這裡給出一種經典的方案（但還不是最好）。
找到要刪除的節點，接著用節點右子樹的最小節點代替它，最後給新節點接上左右連結。
在這裡我們會用到min方法來找到右子樹的最小節點，再用deleteMin方法來刪除右子樹中的最小節點，同時把deleteMin方法的返回值傳給新節點的右連結。
結合圖中流程和程式碼更容易理解
1 public void delete(Key key) {
2root = delete(root, key);
3}
4
5private Node delete(Node x, Key key) {
6if (x == null) {
7return null;
8}
9int cmp = key.compareTo(x.key);
10if (cmp > 0) {
11x.right = delete(x.right, key);
12} else if (cmp < 0) {
13x.left = delete(x.left, key);
14} else {// 找到key
15if (x.right == null) {// 無右子樹 將左子樹接上
16return x.left;
17}
18if (x.left == null) {
19return x.right;
20}
21Node t = x;
22// **********************************************
23x = min(t.right); // *被刪除節點有左右子樹，用右子樹中的最小節點代替它
24x.left = t.left; // *替換後，左子樹保持不變
25x.right = deleteMin(t.right); // *右子樹刪除最小節點後再接入
26// **********************************************
27}
28x.N = size(x.left) + size(x.right) + 1;// 更新新節點和上一個節點的n
29return x;// 不一定會用到
30}
4、範圍查詢
範圍查詢即返回指定範圍內的所有鍵，這需要我們遍歷二叉樹，在這裡我們使用中序遍歷，將會得到一組由小到大的序列。
在這之前先來看看怎麼怎麼將二叉樹查詢樹中的所有鍵由小到大打印出來：
1private void print(Node x) {//x為樹的根節點
2if(x==null) {
3return;
4}
5print(x.left);
6System.out.println(x.key);
7print(x.right);;
8}
在範圍查詢中我們將傳入兩個引數lo和hi來確定範圍，並將範圍內的鍵存入佇列，最後返回佇列。
1public Iterable<Key> keys() {// 返回查詢二叉樹中的所有鍵
2return keys(min(), max());
3}
4public Iterable<Key> keys(Key lo, Key hi) {// 二叉樹的範圍查詢操作
5Queue<Key> queue = new Queue<Key>();
6keys(root, queue, lo, hi);
7return queue;
8}
9
10private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
11if (x == null) {
12return;
13}
14int cmplo = lo.compareTo(x.key);
15int cmphi = hi.compareTo(x.key);
16// 三個if類似於中序遍歷
17if (cmplo < 0) {
18keys(x.left, queue, lo, hi);
19}
20if (cmplo <= 0 && cmphi >= 0) {
21queue.enqueue(x.key);
22}
23if (cmphi > 0) {
24keys(x.right, queue, lo, hi);
25}
26}
對於遞迴和非遞迴，有人證實在一般情況下非遞迴的效率更高，如果樹不是平衡的，函式呼叫棧的深度可能會出現問題。遞迴形式能讓人更容易理解，通過實現再非遞迴理解程式碼的本質。
三、程式碼展示（包含所有程式碼及非遞迴實現）
1 package Unit3;
2
3 import java.util.Stack;
4
5 import edu.princeton.cs.algs4.Queue;
6
7 public class BST<Key extends Comparable<Key>, Value> {// 二叉查詢樹
8private Node root;// 查詢二叉樹的根節點
9
10private class Node {
11private Key key;// 鍵
12private Value val;// 值
13private Node left, right;// 指向子樹的連結
14private int N;// 以該節點為根節點的子樹中的總節點數
15
16public Node(Key key, Value val, int N) {
17this.key = key;
18this.val = val;
19this.N = N;
20}
21}
22
23public int size() {
24return size(root);
25}
26
27private int size(Node x) {
28if (x != null) {
29return x.N;
30} else {
31return 0;
32}
33}
34
35public Value get(Key key) {// 返回鍵key對應的值
36return get(root, key);
37}
38
39private Value get(Node x, Key key) {// 遞迴
40if (key == null) {
41return null;
42}
43int cmp = key.compareTo(x.key);
44if (cmp < 0) {
45return get(x.left, key);
46} else if (cmp > 0) {
47return get(x.right, key);
48} else
49return x.val;
50}
51
52/*
53* private Value getTwo(Node x, Key key) {// 非遞迴 if (key == null) { return null;
54* } int cmp; while (x != null) { cmp = key.compareTo(x.key); if (cmp < 0) { x =
55* x.left; } else if (cmp > 0) { x = x.right; } else return x.val; } return
56* null; }
57*/
58
59public void put(Key key, Value val) {
60root = put(root, key, val);
61}
62
63private Node put(Node x, Key key, Value val) {
64if (x == null) {// 建立新節點
65return new Node(key, val, 1);
66}
67int cmp = key.compareTo(x.key);
68if (cmp < 0) {
69x.left = put(x.left, key, val);
70} else if (cmp > 0) {
71x.right = put(x.right, key, val);
72} else {
73x.val = val;
74}
75x.N = size(x.left) + size(x.right) + 1;
76return x;// 在插入結束時返回（更新節點的相關資訊）
77}
78
79private Node putTwo(Node x, Key key, Value val) {// 在存在基本操作基礎上的非遞迴put（）
80if (get(key) != null) {
81select(root, rank(key)).val = val;
82}
83return x;
84}
85
86public Key min() {
87return min(root).key;
88}
89
90private Node min(Node x) {
91if (x.left == null) {
92return x;
93}
94return min(x.left);
95}
96
97public Key max() {
98return max(root).key;
99}
100
101private Node max(Node x) {
102if (x.right == null) {
103return x;
104}
105return min(x.right);
106}
107
108public Key floor(Key key) {
109Node x = floor(root, key);
110if (x == null) {
111return null;
112}
113return x.key;
114}
115
116// private Node floor(Node x, Key key) {//測試（個人思路
117// if(x==null) {
118// return null;
119// }
120// int cmp=key.compareTo(x.key);
121// if(cmp<0) {
122// return floor(x.left,key);
123// }else if(cmp>0) {
124// if(x.right==null) {
125// return x.right;
126// }
127// return floor(x.right,key);
128// }
129// else {
130// return x;
131// }
132// }
133
134private Node floor(Node x, Key key) {// 類似前序遍歷 找到後不再執行後續操作
135if (x == null) {
136return null;
137}
138int cmp = key.compareTo(x.key);
139if (cmp == 0) {
140return x;
141}
142if (cmp < 0) {
143return floor(x.left, key);
144}
145Node f = floor(x.right, key);
146if (f != null) {
147return f;
148} else {
149return x;
150}
151}
152
153public Key ceiling(Key key) {
154Node x = ceiling(root, key);
155if (x == null) {
156return null;
157}
158return x.key;
159}
160
161private Node ceiling(Node x, Key key) {
162if (x == null) {
163return null;
164}
165int cmp = key.compareTo(x.key);
166if (cmp == 0) {
167return x;
168}
169if (cmp > 0) {// 往大找
170return ceiling(x.right, key);
171}
172Node f = floor(x.left, key);
173if (f != null) {
174return f;
175} else {
176return x;
177}
178}
179
180public Key FOC(Key key, String s) {// 合併兩個方法（自創
181Node x = null;
182if (s.equals("floor")) {
183x = floor(root, key);
184} else if (s.equals("ceiling")) {
185x = ceiling(root, key);
186} else {
187System.out.println("輸入錯誤！將返回null");
188}
189if (x == null) {
190return null;
191}
192return x.key;
193}
194
195public Key select(int k) {// 返回排名為k的鍵
196return select(root, k).key;
197}
198
199public Node select(Node x, int k) {// 返回排名為k的節點
200if (x == null) {
201return null;
202}
203int t = size(x.left);
204if (t > k) {
205return select(x.left, k);
206} else if (t < k) {
207return select(x.right, k - t - 1);
208} else {
209return x;
210}
211}
212
213public Node selectTwo(Node x, int k) {
214if (x == null) {
215return null;
216}
217while (k != size(x.left)) {
218if (size(x.left) > k) {
219x = x.left;
220} else {
221x = x.right;
222k = k - size(x.left) - 1;
223}
224}
225return x;
226}
227
228public int rank(Key key) {// 返回key的排名
229return rank(key, root);
230}
231
232private int rank(Key key, Node x) {
233if (key == null) {
234return 0;
235}
236int cmp = key.compareTo(x.key);
237if (cmp < 0) {
238return rank(key, x.left);
239} else if (cmp > 0) {
240return rank(key, x.right) + size(x.left) + 1;
241} else {
242return size(x.left);
243}
244}
245
246public void deleteMin() {
247root = deleteMin(root);
248}
249
250private Node deleteMin(Node x) {
251if (x.left == null) {
252return x.right;
253}
254x.left = deleteMin(x.left);
255x.N = size(x.left) + size(x.right) + 1;
256return x;// 在刪除結束後返回節點的相關資訊
257}
258
259public void delete(Key key) {
260root = delete(root, key);
261}
262
263private Node delete(Node x, Key key) {
264if (x == null) {
265return null;
266}
267int cmp = key.compareTo(x.key);
268if (cmp > 0) {
269x.right = delete(x.right, key);
270} else if (cmp < 0) {
271x.left = delete(x.left, key);
272} else {// 找到key
273if (x.right == null) {// 無右子樹 將左子樹接上
274return x.left;
275}
276if (x.left == null) {
277return x.right;
278}
279Node t = x;
280// **********************************************
281x = min(t.right); // *被刪除節點有左右子樹，用右子樹中的最小節點代替它
282x.left = t.left; // *替換後，左子樹保持不變
283x.right = deleteMin(t.right); // *右子樹刪除最小節點後再接入
284// **********************************************
285}
286x.N = size(x.left) + size(x.right) + 1;// 更新新節點和上一個節點的n
287return x;// 不一定會用到
288}
289
290private void print(Node x) {//x為樹的根節點
291if(x==null) {
292return;
293}
294print(x.left);
295System.out.println(x.key);
296print(x.right);;
297}
298
299public Iterable<Key> keys() {// 返回查詢二叉樹中的所有鍵
300return keys(min(), max());
301}
302
303public Iterable<Key> keysTwo() {// 範圍查詢非遞迴方法
304Stack<Node> stack = new Stack();
305Queue<Key> queue = new Queue<Key>();
306Node x = root;
307while (x != null || !stack.isEmpty()) {// 中序遍歷非遞減
308if (x != null) {
309stack.add(x);
310x = x.left;
311} else {
312x = stack.pop();
313queue.enqueue(x.key);
314x = x.right;
315}
316}
317/*
318* while(x!=null||stack.isEmpty()) {// 中序遍歷非遞增 if(x!=null) { stack.add(x);
319* x=x.right; }else { x=stack.pop(); queue.enqueue(x.key); x=x.left; } }
320*/
321return queue;// 返回非降序佇列
322}
323
324public Iterable<Key> keysThree(int i) {// 範圍查詢非遞迴方法（包含前中序遍歷）
325Stack<Node> stack = new Stack();
326Queue<Key> queue1 = new Queue<Key>();// 儲存前序遍歷
327Queue<Key> queue2 = new Queue<Key>();// 儲存中序遍歷
328Node x = root;
329while (x != null || !stack.isEmpty()) {
330for (; x != null; x = x.left) {
331stack.add(x);
332queue1.enqueue(x.key);// 前序遍歷
333}
334for (; x == null && !stack.isEmpty(); x = x.right) {
335x = stack.pop();
336queue2.enqueue(x.key);// 中序遍歷
337}
338}
339if (i == 1) {
340return queue1;
341}
342return queue2;
343}
344
345public Iterable<Key> keysFour() {// 範圍查詢非遞迴方法（後序遍歷）
346Stack<Node> stackA = new Stack();
347Stack<Node> stackB = new Stack();
348Queue<Key> queue = new Queue<Key>();// 儲存後序遍歷
349Node x = root;
350while (x != null || !stackB.isEmpty()) {
351for (; x != null; x = x.right) {
352stackA.add(x);
353stackB.add(x);
354}
355for (; x == null && !stackB.isEmpty(); x = x.left) {
356x = stackB.pop();
357}
358}
359
360while (!stackA.isEmpty()) {
361queue.enqueue(stackA.pop().key);
362}
363return queue;
364}
365
366public Iterable<Key> keys(Key lo, Key hi) {// 二叉樹的範圍查詢操作
367Queue<Key> queue = new Queue<Key>();
368keys(root, queue, lo, hi);
369return queue;
370}
371
372private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
373if (x == null) {
374return;
375}
376int cmplo = lo.compareTo(x.key);
377int cmphi = hi.compareTo(x.key);
378// 三個if類似於中序遍歷
379if (cmplo < 0) {
380keys(x.left, queue, lo, hi);
381}
382if (cmplo <= 0 && cmphi >= 0) {
383queue.enqueue(x.key);
384}
385if (cmphi > 0) {
386keys(x.right, queue, lo, hi);
387}
388}
389
390public static void main(String[] args) {
391BST<Integer, String> bst = new BST<Integer, String>();
392bst.put(5, "one");
393bst.put(4, "two");
394bst.put(2, "one");
395bst.put(6, "two");
396bst.put(3, "one");
397for (Integer x : bst.keysFour()) {// 中序遍歷
398System.out.println(x + " " + bst.get(x));
399}
400// bst.delete(2);
401}
402 }
View Code