加關注可以第一時間接收數據結構系列文章，覺得不錯可以轉發和點贊，謝謝支持
上一節我們學習了樹、二叉樹以及二叉樹的遍歷，今天我們再來學習一種特殊的的二叉樹，二叉查找樹。二叉查找樹最大的特點就是，支持動態數據集合的快速插入、刪除、查找操作。
我們之前說過，散列表也是支持這些操作的，並且散列表的這些操作比二叉查找樹更高效，時間複雜度是 O(1)。既然有了這麼高效的散列表，使用二叉樹的地方是不是都可以替換成散列表呢？有沒有哪些地方是散列表做不了，必須要用二叉樹來做的呢？
帶著這些問題，我們就來學習今天的內容，二叉查找樹！
二叉查找樹（Binary Search Tree）
二叉查找樹是二叉樹中最常用的一種類型，也叫二叉搜索樹。顧名思義，二叉查找樹是為了實現快速查找而生的。不過，它不僅僅支持快速查找一個數據，還支持快速插入、刪除一個數據。它是怎麼做到這些的呢？
這些都依賴於二叉查找樹的特殊結構。二叉查找樹要求，在樹中的任意一個節點，其左子樹中的每個節點的值，都要小於這個節點的值，而右子樹節點的值都大於這個節點的值。我畫了幾個二叉查找樹的例子，你一看應該就清楚了。
前面我們講到，二叉查找樹支持快速查找、插入、刪除操作，現在我們就依次來看下，這三個操作是如何實現的。
1. 二叉查找樹的查找操作
首先，我們看如何在二叉查找樹中查找一個節點。我們先取根節點，如果它等於我們要查找的數據，那就返回。如果要查找的數據比根節點的值小，那就在左子樹中遞歸查找；如果要查找的數據比根節點的值大，那就在右子樹中遞歸查找。
這裡我把查找的代碼實現了一下，貼在下面了，結合代碼，理解起來會更加容易。
1
public class BinarySearchTree {
2
private Node tree;
3
4
public Node find(int data) {
5
Node p = tree;
6
while (p != null) {
7
if (data p.data) p = p.left;
8
else if (data p.data) p = p.right;
9
else return p;
10
}
11
return null;
12
}
13
14
public static class Node {
15
private int data;
16
private Node left;
17
private Node right;
18
19
public Node(int data) {
20
this.data = data;
21
}
22
}
23
}
2. 二叉查找樹的插入操作
二叉查找樹的插入過程有點類似查找操作。新插入的數據一般都是在葉子節點上，所以我們只需要從根節點開始，依次比較要插入的數據和節點的大小關係。
如果要插入的數據比節點的數據大，並且節點的右子樹為空，就將新數據直接插到右子節點的位置；如果不為空，就再遞歸遍歷右子樹，查找插入位置。同理，如果要插入的數據比節點數值小，並且節點的左子樹為空，就將新數據插入到左子節點的位置；如果不為空，就再遞歸遍歷左子樹，查找插入位置。
同樣，插入的代碼我也實現了一下，貼在下面，你可以看看。
1
public void insert(int data) {
2
if (tree == null) {
3
tree = new Node(data);
4
return;
5
}
6
7
Node p = tree;
8
while (p != null) {
9
if (data p.data) {
10
if (p.right == null) {
11
p.right = new Node(data);
12
return;
13
}
14
p = p.right;
15
} else { // data p.data
16
if (p.left == null) {
17
p.left = new Node(data);
18
return;
19
}
20
p = p.left;
21
}
22
}
23
}
3. 二叉查找樹的刪除操作
二叉查找樹的查找、插入操作都比較簡單易懂，但是它的刪除操作就比較複雜了 。針對要刪除節點的子節點個數的不同，我們需要分三種情況來處理。
第一種情況是，如果要刪除的節點沒有子節點，我們只需要直接將父節點中，指向要刪除節點的指針置為 null。比如圖中的刪除節點 55。
第二種情況是，如果要刪除的節點只有一個子節點（只有左子節點或者右子節點），我們只需要更新父節點中，指向要刪除節點的指針，讓它指向要刪除節點的子節點就可以了。比如圖中的刪除節點 13。
第三種情況是，如果要刪除的節點有兩個子節點，這就比較複雜了。我們需要找到這個節點的右子樹中的最小節點，把它替換到要刪除的節點上。然後再刪除掉這個最小節點，因為最小節點肯定沒有左子節點（如果有左子結點，那就不是最小節點了），所以，我們可以應用上面兩條規則來刪除這個最小節點。比如圖中的刪除節點 18。
老規矩，我還是把刪除的代碼貼在這裡。
1
public void delete(int data) {
2
Node p = tree; // p 指向要刪除的節點，初始化指向根節點
3
Node pp = null; // pp 記錄的是 p 的父節點
4
while (p != null p.data != data) {
5
pp = p;
6
if (data p.data) p = p.right;
7
else p = p.left;
8
}
9
if (p == null) return; // 沒有找到
10
11
// 要刪除的節點有兩個子節點
12
if (p.left != null p.right != null) { // 查找右子樹中最小節點
13
Node minP = p.right;
14
Node minPP = p; // minPP 表示 minP 的父節點
15
while (minP.left != null) {
16
minPP = minP;
17
minP = minP.left;
18
}
19
p.data = minP.data; // 將 minP 的數據替換到 p 中
20
p = minP; // 下面就變成了刪除 minP 了
21
pp = minPP;
22
}
23
24
// 刪除節點是葉子節點或者僅有一個子節點
25
Node child; // p 的子節點
26
if (p.left != null) child = p.left;
27
else if (p.right != null) child = p.right;
28
else child = null;
29
30
if (pp == null) tree = child; // 刪除的是根節點
31
else if (pp.left == p) pp.left = child;
32
else pp.right = child;
33
}
實際上，關於二叉查找樹的刪除操作，還有個非常簡單、取巧的方法，就是單純將要刪除的節點標記為“已刪除”，但是並不真正從樹中將這個節點去掉。這樣原本刪除的節點還需要存儲在內存中，比較浪費內存空間，但是刪除操作就變得簡單了很多。而且，這種處理方法也並沒有增加插入、查找操作代碼實現的難度。
4. 二叉查找樹的其他操作
除了插入、刪除、查找操作之外，二叉查找樹中還可以支持快速地查找最大節點和最小節點、前驅節點和後繼節點。這些操作我就不一一展示了。我會將相應的代碼放到 GitHub 上，你可以自己先實現一下，然後再去上面看。
二叉查找樹除了支持上面幾個操作之外，還有一個重要的特性，就是中序遍歷二叉查找樹，可以輸出有序的數據序列，時間複雜度是 O(n)，非常高效。因此，二叉查找樹也叫作二叉排序樹。
支持重複數據的二叉查找樹
前面講二叉查找樹的時候，我們默認樹中節點存儲的都是數字。很多時候，在實際的軟件開發中，我們在二叉查找樹中存儲的，是一個包含很多字段的對象。我們利用對象的某個字段作為鍵值（key）來構建二叉查找樹。我們把對象中的其他字段叫作衛星數據。
前面我們講的二叉查找樹的操作，針對的都是不存在鍵值相同的情況。那如果存儲的兩個對象鍵值相同，這種情況該怎麼處理呢？我這裡有兩種解決方法。
第一種方法比較容易。二叉查找樹中每一個節點不僅會存儲一個數據，因此我們通過鏈表和支持動態擴容的數組等數據結構，把值相同的數據都存儲在同一個節點上。
第二種方法比較不好理解，不過更加優雅。
每個節點仍然只存儲一個數據。在查找插入位置的過程中，如果碰到一個節點的值，與要插入數據的值相同，我們就將這個要插入的數據放到這個節點的右子樹，也就是說，把這個新插入的數據當作大於這個節點的值來處理。
當要查找數據的時候，遇到值相同的節點，我們並不停止查找操作，而是繼續在右子樹中查找，直到遇到葉子節點，才停止。這樣就可以把鍵值等於要查找值的所有節點都找出來。
對於刪除操作，我們也需要先查找到每個要刪除的節點，然後再按前面講的刪除操作的方法，依次刪除。
二叉查找樹的時間複雜度分析
好了，對於二叉查找樹常用操作的實現方式，你應該掌握得差不多了。現在，我們來分析一下，二叉查找樹的插入、刪除、查找操作的時間複雜度。
實際上，二叉查找樹的形態各式各樣。比如這個圖中，對於同一組數據，我們構造了三種二叉查找樹。它們的查找、插入、刪除操作的執行效率都是不一樣的。圖中第一種二叉查找樹，根節點的左右子樹極度不平衡，已經退化成了鏈表，所以查找的時間複雜度就變成了 O(n)。
我剛剛其實分析了一種最糟糕的情況，我們現在來分析一個最理想的情況，二叉查找樹是一棵完全二叉樹（或滿二叉樹）。這個時候，插入、刪除、查找的時間複雜度是多少呢？
從我前面的例子、圖，以及還有代碼來看，不管操作是插入、刪除還是查找，時間複雜度其實都跟樹的高度成正比，也就是 O(height)。既然這樣，現在問題就轉變成另外一個了，也就是，如何求一棵包含 n 個節點的完全二叉樹的高度？
樹的高度就等於最大層數減一，為了方便計算，我們轉換成層來表示。從圖中可以看出，包含 n 個節點的完全二叉樹中，第一層包含 1 個節點，第二層包含 2 個節點，第三層包含 4 個節點，依次類推，下面一層節點個數是上一層的 2 倍，第 K 層包含的節點個數就是 2^(K-1)。
不過，對於完全二叉樹來說，最後一層的節點個數有點兒不遵守上面的規律了。它包含的節點個數在 1 個到 2^(L-1) 個之間（我們假設最大層數是 L）。如果我們把每一層的節點個數加起來就是總的節點個數 n。也就是說，如果節點的個數是 n，那麼 n 滿足這樣一個關係：
1
n = 1+2+4+8+...+2^(L-2)+1
2
n = 1+2+4+8+...+2^(L-2)+2^(L-1)
藉助等比數列的求和公式，我們可以計算出，L 的範圍是 [log2(n+1), log2n +1]。完全二叉樹的層數小於等於 log2n +1，也就是說，完全二叉樹的高度小於等於 log2n。
顯然，極度不平衡的二叉查找樹，它的查找性能肯定不能滿足我們的需求。我們需要構建一種不管怎麼刪除、插入數據，在任何時候，都能保持任意節點左右子樹都比較平衡的二叉查找樹，這就是我們下一節課要詳細講的，一種特殊的二叉查找樹，平衡二叉查找樹。平衡二叉查找樹的高度接近 logn，所以插入、刪除、查找操作的時間複雜度也比較穩定，是 O(logn)。
解答開篇
我們在散列表那節中講過，散列表的插入、刪除、查找操作的時間複雜度可以做到常量級的 O(1)，非常高效。而二叉查找樹在比較平衡的情況下，插入、刪除、查找操作時間複雜度才是 O(logn)，相對散列表，好像並沒有什麼優勢，那我們為什麼還要用二叉查找樹呢？
我認為有下面幾個原因：
第一，散列表中的數據是無序存儲的，如果要輸出有序的數據，需要先進行排序。而對於二叉查找樹來說，我們只需要中序遍歷，就可以在 O(n) 的時間複雜度內，輸出有序的數據序列。
第二，散列表擴容耗時很多，而且當遇到散列衝突時，性能不穩定，儘管二叉查找樹的性能不穩定，但是在工程中，我們最常用的平衡二叉查找樹的性能非常穩定，時間複雜度穩定在 O(logn)。
第三，籠統地來說，儘管散列表的查找等操作的時間複雜度是常量級的，但因為哈希衝突的存在，這個常量不一定比 logn 小，所以實際的查找速度可能不一定比 O(logn) 快。加上哈希函數的耗時，也不一定就比平衡二叉查找樹的效率高。
第四，散列表的構造比二叉查找樹要複雜，需要考慮的東西很多。比如散列函數的設計、衝突解決辦法、擴容、縮容等。平衡二叉查找樹只需要考慮平衡性這一個問題，而且這個問題的解決方案比較成熟、固定。
最後，為了避免過多的散列衝突，散列表裝載因子不能太大，特別是基於開放尋址法解決衝突的散列表，不然會浪費一定的存儲空間。
綜合這幾點，平衡二叉查找樹在某些方面還是優於散列表的，所以，這兩者的存在並不衝突。我們在實際的開發過程中，需要結合具體的需求來選擇使用哪一個。
內容小結
今天我們學習了一種特殊的二叉樹，二叉查找樹。它支持快速地查找、插入、刪除操作。
二叉查找樹中，每個節點的值都大於左子樹節點的值，小於右子樹節點的值。不過，這只是針對沒有重複數據的情況。對於存在重複數據的二叉查找樹，我介紹了兩種構建方法，一種是讓每個節點存儲多個值相同的數據；另一種是，每個節點中存儲一個數據。針對這種情況，我們只需要稍加改造原來的插入、刪除、查找操作即可。
在二叉查找樹中，查找、插入、刪除等很多操作的時間複雜度都跟樹的高度成正比。兩個極端情況的時間複雜度分別是 O(n) 和 O(logn)，分別對應二叉樹退化成鏈表的情況和完全二叉樹。
為了避免時間複雜度的退化，針對二叉查找樹，我們又設計了一種更加複雜的樹，平衡二叉查找樹，時間複雜度可以做到穩定的 O(logn)，下一節我們具體來講。
閱讀更多 xiuxiuing 的文章
