這節學習一種特殊的二叉樹—二叉查找樹。它最大的特點是支持動態數據集合的快速插入、刪除、查找操作。但是散列表也是支持這些操作的，并且散列表的這些操作比二叉查找樹更高效，時間復雜度是 O(1)。

問題引入

既然有高效的散列表，二叉樹的地方是不是都可以替換成散列表呢？哪些地方是散列表做不了，必須要用二叉樹來做？

二叉查找樹（Binary Search Tree）是二叉樹中最常用的一種類型，也叫二叉搜索樹。它不僅支持快速查找一個數據，還支持快速插入、刪除一個數據。二叉查找樹要求在樹中的任意一個節點，其左子樹中的每個節點的值，都要小于這個節點的值，而右子樹節點的值都大于這個節點的值。二叉查找樹支持快速查找、插入、刪除操作，這三個操作是如何實現的。

1.二叉查找樹的查找操作

如何在二叉查找樹中查找一個節點。先取根節點，如果等于要查找的數據那就返回。如果要查找的數據比根節點的值小，那就在左子樹中遞歸查找；如果要查找的數據比根節點的值大，那就在右子樹中遞歸查找。查找的代碼實現

public class BinarySearchTree { ? private Node tree; ? public Node find(int data) { ??? Node p = tree; ??? while (p != null) { ????? if (data < p.data) p = p.left; ????? else if (data > p.data) p = p.right; ????? else return p; ??? } ??? return null; ? } ? public static class Node { ??? private int data; ??? private Node left; ??? private Node right; ? ??? public Node(int data) { ????? this.data = data; ??? } ? } }

2.二叉查找樹插入操作

插入過程有點類似查找。新插入數據一般都是在葉子節點上，從根節點開始依次比較要插入的數據和節點的大小關系。如果要插入的數據比節點的數據大，并且節點的右子樹為空，就將新數據直接插到右子節點的位置；如果不為空，就再遞歸遍歷右子樹，查找插入位置。同理，如果要插入的數據比節點數值小，類推。插入的代碼

public void insert(int data) { ? if (tree == null) { ??? tree = new Node(data); ??? return; ? } ? Node p = tree; ? while (p != null) { ??? if (data > p.data) { ????? if (p.right == null) { ??????? p.right = new Node(data); ??????? return; ????? } ????? p = p.right; ??? } else { // data < p.data ????? if (p.left == null) { ??????? p.left = new Node(data); ??????? return; ????? } ????? p = p.left; ??? } ? } }

3. 二叉查找樹刪除操作

刪除操作就比較復雜，針對要刪除節點的子節點個數不同需要分三種情況來處理。

第一種情況是，如果要刪除的節點沒有子節點，只需要直接將父節點中，指向要刪除節點的指針置為 null。比如圖中的刪除節點 55。

第二種情況是，如果要刪除的節點只有一個子節點（只有左子節點或者右子節點），只需要更新父節點中指向要刪除節點的指針，讓它指向要刪除節點的子節點就可以了。比如圖中的刪除節點 13。

第三種情況是，如果要刪除的節點有兩個子節點。需要找到這個節點的右子樹中的最小節點，把它替換到要刪除的節點上。然后再刪除掉這個最小節點，因為最小節點肯定沒有左子節點（如果有左子結點，那就不是最小節點了），所以可以應用上面兩條規則來刪除這個最小節點。比如圖中的刪除節點 18。

public void delete(int data) { ? Node p = tree; // p指向要刪除的節點，初始化指向根節點 ? Node pp = null; // pp記錄的是p的父節點 ? while (p != null && p.data != data) { ??? pp = p; ??? if (data > p.data) p = p.right; ??? else p = p.left; ? } ? if (p == null) return; // 沒有找到 ? ? // 要刪除的節點有兩個子節點 ? if (p.left != null && p.right != null) { // 查找右子樹中最小節點 ??? Node minP = p.right; ??? Node minPP = p; // minPP表示minP的父節點 ??? while (minP.left != null) { ????? minPP = minP; ????? minP = minP.left; ??? } ??? p.data = minP.data; // 將minP的數據替換到p中 ??? p = minP; // 下面就變成了刪除minP了 ??? pp = minPP; ? } ? ? // 刪除節點是葉子節點或者僅有一個子節點 ? Node child; // p的子節點 ? if (p.left != null) child = p.left; ? else if (p.right != null) child = p.right; ? else child = null; ? ? if (pp == null) tree = child; // 刪除的是根節點 ? else if (pp.left == p) pp.left = child; ? else pp.right = child; }

關于二叉查找樹的刪除操作，還有個非常簡單、取巧的方法，就是單純將要刪除的節點標記為“已刪除”，但是并不真正從樹中將這個節點去掉。這樣原本刪除的節點還需要存儲在內存中，比較浪費內存空間，但是刪除操作就變得簡單了很多。而且，這種處理方法也并沒有增加插入、查找操作代碼實現的難度

4.二叉查找樹的其他操作

除了插入、刪除、查找操作之外，二叉查找樹中還可以支持快速地查找最大節點和最小節點、前驅節點和后繼節點。二叉查找樹除了支持上面幾個操作之外，還有一個重要的特性，就是中序遍歷二叉查找樹，可以輸出有序的數據序列，時間復雜度是 O(n)，非常高效。因此，二叉查找樹也叫作二叉排序樹。

5.支持重復數據的二叉查找樹

二叉查找樹除了存儲數字外，在實際的軟件開發中存儲的，是一個包含很多字段的對象。我們利用對象的某個字段作為鍵值（key）來構建二叉查找樹。把對象中的其他字段叫作衛星數據。前面的二叉查找樹的操作，針對的都是不存在鍵值相同的情況。那如果存儲的兩個對象鍵值相同，這種情況該怎么處理呢？

有兩種解決方法。第一種方法比較容易。二叉查找樹中每一個節點不僅會存儲一個數據，因此我們通過鏈表和支持動態擴容的數組等數據結構，把值相同的數據都存儲在同一個節點上。第二種方法比較不好理解，不過更加優雅。每個節點仍然只存儲一個數據。在查找插入位置的過程中，如果碰到一個節點的值，與要插入數據的值相同，我們就將這個要插入的數據放到這個節點的右子樹，也就是說，把這個新插入的數據當作大于這個節點的值來處理。

當要查找數據的時候，遇到值相同的節點，我們并不停止查找操作，而是繼續在右子樹中查找，直到遇到葉子節點，才停止。這樣就可以把鍵值等于要查找值的所有節點都找出來。

對于刪除操作，也需要先查找到每個要刪除的節點，然后再按前面講的刪除操作的方法，依次刪除。

6.二叉查找樹的時間復雜度分析

二叉查找樹的插入、刪除、查找操作的時間復雜度。

如何求一棵包含 n 個節點的完全二叉樹的高度？樹的高度就等于最大層數減一，為了方便計算，我們轉換成層來表示。包含 n 個節點的完全二叉樹中，第一層包含 1 個節點，第二層包含 2 個節點，第 K 層包含的節點個數就是 2^(K-1)。對于完全二叉樹來說，最后一層的節點個數在 1 個到 2^(L-1) 個之間（我們假設最大層數是 L）。如果我們把每一層的節點個數加起來就是總的節點個數 n。也就是說，如果節點的個數是 n，那么 n 滿足這樣一個關系：n >= 1+2+4+8+...+2^(L-2)+1n <= 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) 快。加上哈希函數的耗時，也不一定就比平衡二叉查找樹的效率高。

散列表的構造比二叉查找樹要復雜，需要考慮的東西很多。比如散列函數的設計、沖突解決辦法、擴容、縮容等。平衡二叉查找樹只需要考慮平衡性這一個問題，而且這個問題的解決方案比較成熟、固定。

為了避免過多的散列沖突，散列表裝載因子不能太大，特別是基于開放尋址法解決沖突的散列表，不然會浪費一定的存儲空間。

綜合這幾點，平衡二叉查找樹在某些方面還是優于散列表的，這兩者的存在并不沖突。需要結合具體的需求來選擇使用哪一個。

總結

以上是生活随笔為你收集整理的24 | 二叉树基础（下）：有了如此高效的散列表，为什么还需要二叉树？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。