一文徹底掌握二叉查找樹（多組動圖）(史上最全總結）

2020 年 7 月 2 日
筆記

這是查找演算法系列文章的第二篇，助你徹底掌握二叉查找樹

在數據結構中，二叉查找樹無疑是極為重要的，但是初學者理解起來卻有些吃力，網上的文章講得也不太全面。本文希望結合多組動圖、圖片以及詳細的程式碼實現，力爭讓大家完全掌握二叉查找樹（BST）的各種概念和操作。 相信你看完肯定會有收穫。

先看一下本文的目錄吧！每個操作都配有動圖和詳細實現程式碼（Java）二十五張圖

首先，如果你對樹和二叉樹的定義不是很了解的話，建議先去看一下這個系列的第一篇文章一文入門二叉樹,力求對樹有一個基本的認識，再來學習!

背景和必要性

背景

現代電腦和網路使我們能夠接觸和訪問海量的資訊，所以高效的檢索這些資訊將是一個巨大的挑戰。這包括資訊的存儲、處理和查找。這一問題促使我們去研究經典查找演算法，即如何高效的存儲和查找數據？

目標

實現一個符號表，我們將資訊（鍵-值）儲存在符號表裡，根據相應的鍵去查找它所對應的值。你可以把它想像成一個字典，我們在字典中存儲了大量的詞語的釋義，我們應該能夠根據詞語（索引）去查找這個詞語對應的意思。

如下圖所示，就是一個很簡單的符號表，我們可以很輕鬆的通過鍵來查找值，但是，基於數組或者鏈表的這種數據結構並不高效，而且不能較好的維持一定的性質（比如我用數組存儲了很多數據，你讓我找到最大的那個，我該怎麼辦呢？先在內部排序再輸出，但是，不高效！你是不是會想有沒有一種數據結構天然就滿足這種性質？）

總結一下，我們希望實現一個高效的符號表，它支援插入、查找、求最大鍵和最小鍵、求前驅節點（我們一會再說）和後驅節點等等，它的時間複雜度呢？我們盡量向O(logN)看齊。這就是我們今天的主角–二叉查找樹！

二叉樹知識回顧

首先，如果你對樹和二叉樹的定義不是很了解的話，建議先去看一下這個系列的第一篇文章一文入門二叉樹,力求對樹有一個基本的認識，再來學習

二叉樹的定義

直接上幾組圖，你只需要記住每個節點至多有兩個子節點即可。

這幾張圖幾乎代表了所有類型的二叉樹，你會發現，最後兩個其實就是鏈表，沒錯，二叉樹成功地退化成了鏈表，那性能上肯定會下降，但是關於這個問題如何避免卻不在本文的範圍內，這是下一期文章要解決的問題–[紅黑樹]。我們在這裡只是熟悉一下二叉樹的定義就好了。

二叉樹的存儲方法

上一篇文章我們就已經介紹過，這裡再重複一遍。二叉樹的存儲方法主要有兩種：鏈式存儲法和線性存儲法，它們分別對應著鏈表和數組。完全二叉樹最好用數組存放，因為數組下標和父子節點之間存在著完美的對應關係，而且也能夠盡最大可能的節省記憶體，如圖一所示。

我們把根節點儲存在下標為i=1的位置，那麼左子節點儲存在2*i=2的位置，右子節點儲存在下標為2*i+1=2的位置。依此類推，完成樹的存儲。藉助下標運算，我們可以很輕鬆的從父節點跳轉到左子節點和右子節點或者從任意一個子節點找到它的父節點。如果X的位置為i，則它的兩個子節點的下標分別為2i和2i+1,它的父節點的位置為i/2(這裡結果向下取整)。

相比用數組存儲數據，鏈式存儲法則相應的更加靈活，我們使用自定義類型Node來表示每一個節點。

class Node{
	int data;
	Node left,right;
}

每個節點都是一個Node對象，它包含我們所需要存儲的數據，指向左子節點的引用，直向右子節點的引用，就像鏈表一樣將整個樹串起來。如果該節點沒有左子節點，則Node.left==null或者Node.right==null，如圖二所示。能理解就行，別在意它的美觀度了:)

二叉樹的遍歷

二叉樹的遍歷有三種方法：前序遍歷，中序遍歷和後序遍歷。在這裡我只講和本文我們實現二叉查找樹相關的中序遍歷，如果你希望了解更多，請看上一篇文章吧，那裡我給出了詳細的程式碼和圖示。

所謂中序遍歷，就是指：對於樹中的任意節點來說，先列印它的左子樹，然後再列印它本身，最後列印它的右子樹。具體的程式碼是用遞歸實現的，比較容易理解。

public void inOrder(Node root){
	if(root==null) return;
	inOrder(root.left);
	Systrm.out.println(root.data);
	inOrder(root.right);
}

你可以結合下面這張圖理解一下

以上，我們回顧了二叉樹的基本知識，請確保你已經完全掌握。接下來我們將介紹今天的主角二叉查找樹(Binary Search Tree),它是一種符號表，成功地將鏈表插入的靈活性和有序數組查找的高效性結合起來。聽起來是不是很完美？

二叉查找樹

一起來看一下它的定義吧，其實只是在二叉樹的定義上做了一個小小的限制：

一棵二叉查找樹是一棵二叉樹，其中每個節點的鍵都大於它的左子樹上的任意節點的鍵，並且小於右子樹上任意節點的鍵。

只要按照這個規則，我們構造出來的樹就是二叉查找樹。現在，請仔細看一下上文所有帶數字的樹，它們都是二叉查找樹。
你可能會發現如果我們對二叉查找樹進行中序遍歷的話，得到的序列是有序的，這是二叉查找樹天生的靈活性。具體也可以看一下下面這幅圖：

準備完熱身運動，接下來我們就正式進入二叉查找樹的講解:)。

數據表示
查找數據
插入數據
查找最大值與最小值
查找前驅節點和後繼節點
查找向下取整和向上取整
刪除操作

數據表示

完全等同於二叉樹的鏈式存儲法，我們定義一個節點類Node來表示二叉查找樹上的一個節點，每個節點含有一個鍵，一個值，一個左鏈接，一個有鏈接。其中鍵和值是為了儲存和查找，一般來說，給定鍵，我們能夠快速的找到它所對應的值。

private class Node{
    private int key;//鍵
    private String value;//值，我這裡把數據設為String，為了和key區分開
    private Node left,right;//指向子樹的鏈接
    public Node(int key,String value);//Java中的構造函數
}

查找數據

查找操作接受一個鍵值（key），返回該鍵值對應的值（value），如果找不到就返回 null。
大致思路是：如果樹是空的，則查找未命中，返回null；如果被查找的鍵和根節點的鍵相等，查找命中，返回根節點對應的值；如果被查找的鍵較小，則在左子樹中繼續查找；如果被查找的鍵較大，則在右子樹中繼續查找。我們用遞歸來實現這個操作，具體的程式碼如下：

public String find(int key){
    return find(root,key);
}
private String find(Node x,int key){
    //在以x為根結點的子樹中查找並返回鍵key所對應的值
    //如果找不到，就返回null
    if(x==null) return null;
    if(key<x.key) return find(x.left,key);
    else if(key>x.left) return find(x.right,key);
    else return x.value;
}
// 注意這裡用了兩個方法，一個私有一個公開，私有的用來遞歸，公開的對外開放

遞歸程式碼的實現是很簡潔的，比較容易理解，我們來看你一下動圖：

比如我們想查找32,首先，32小於41，所以對41的左子樹進行查找，32大於20，再對20的右子樹進行查找，緊接著對29的右子樹查找，正好命中32,如果查找不到的話就返回null。

插入數據

我們首先判斷根節點是不是空節點，如果是空節點，就直接創建一個新的Node對象作為根節點即可；
如果根節點非空，就通過while循環以及p.key和key的大小比較不斷向下尋找。循環結束時肯定會找到一個空位置，這時我們就創建一個新的Node對象並把它接在這裡。當然還有一種情況，如果p.key==key,就更新這個鍵鍵對應的值，結束。

來一起看下面這個例子，向樹中插入31，可以結合著實現方法一（非遞歸）理解一下：

實現方法一（非遞歸實現）：

public void insert(int key,String value) {
    //如果根節點為空節點
    if (root == null) {
        root = new Node(key,value);
        return;
    }

    //根節點不是空節點
    Node p = root;
    while (p != null) {
      if (key > p.key) { //向右走
        if (p.right == null) {
          p.right = new Node(key,value);
          return;
        }
        p = p.right;
       } 
       else if { // key < p.key,向左走
         if (p.left == null) {
           p.left = new Node(key,value);
           return;
         }
        p = p.left;
      }
      else p.value=value;//如果原來樹中就含有value鍵，則更新它的值
    }
  }

實現方法二（遞歸實現）：

public void insert(int key,String value){
    root=insert(root,key,value);
}
private Node insert(Node x,int key,String value){
    //如果key存在於以x為根節點的子樹中則更新它的值；
    //如果不在就創建新節點插入到合適的位置；
    if(x==null) return new Node(key,value);
    if(key<x.key) x.left=insert(x.left,key,value);
    else if(key>x.key) x.right=insert(x.right,key,value);
    else x.value=value;
    return x;
}

這個遞歸的程式碼儘管很簡潔，但卻不是那麼容易理解。
我先說一下寫遞歸演算法需要注意的問題:

1.一個問題的解可以分解為幾個子問題的解何為子問題
這個問題與分解之後的子問題，除了數據規模不同，求解思路完全一樣
3.存在遞歸終止條件

PS:關鍵在於寫出遞推公式，找到終止條件

在這裡，遞推公式就是根據條件判斷。然後將根節點對應的樹轉化為規模小一點的左子樹或右子樹，終止條件就是遇到空鏈接

如果實在繞腦子，你只需要理解第一種非遞歸的方法就行了:)。

查找最大值和最小值

這個操作應該是最簡單的了。根據二叉查找樹的定義，最小值就是最左邊的元素，直接從根節點一直向左查找即可。它也有兩種實現方式，具體的程式碼如下：

實現一（遞歸實現）

public int min(){
    return min(root).key;
}
private Node min(Node x){
    // 返回以x為根節點的樹的最小節點
    if(x.left==null) return x;
    return min(x.left);
}

實現二（非遞歸實現）

public int min()
    if(root==null) return -1; //表示不存在最小值
    Node x=root;
    //沿著左子樹一直深入搜索下去，直到遇到左子樹為空的節點，此時當前節 點為最小值
    while(x.left !=null)
        x = x.left
    return x.key;
}

以下是動圖演示:

查找最大元素的道理類似，只需把left換成right即可，在這裡就不再多說了，就當給你留的一個作業了:)。

查找前驅節點和後繼節點

前驅節點指的是小於該鍵的最大鍵，後繼節點指的是大於該鍵的最小鍵。你可以結合中序遍歷理解，通過中序遍歷，在得到的序列中位於該點左側的就是前驅節點，右側的就是後驅節點。

舉個例子,如圖所示：

我們首先介紹以下前驅節點的性質：

1.若一個節點有左子樹，那麼該節點的前驅節點是其左子樹中最大的節點（也就是左子樹中最右邊的那個節點），示例如下：

2.若一個節點沒有左子樹，那麼判斷該節點和其父節點的關係

2.1 若該節點是其父節點的右子節點，那麼該節點的前驅結點即為其父節點。示例如下：

2.2 若該節點是其父節點的左子節點，那麼需要沿著其父親節點一直向樹的頂端尋找，直到找到一個節點P，P節點是其父節點Q的右子節點，那麼Q就是該節點的後繼節點，示例如下：

以上就是尋找的思路，不過實際上我們還有一步操作，就是找到這個給定的節點，在這個過程中，我們同時記錄最近的一個向右走的節點first_parent。具體的程式碼如下（已測試）：

    public int get_prenode(int key)
    {
        if (root==null)
            return -1;//-1表示找不到給定的節點
        if (root.key==key)
            return -1;
        Node p = root;
        Node pp = null;
        Node  first_parent=null;
        while (p != null) {
            if (key>p.key) {
                pp = p;
                first_parent=p;
                p = p.right;

            } else if (key<p.key) {
                pp = p; 
                p = p.left;
            } else {

                break;
            }
        }
        if(p==null) return -1;
        else if(p.left!=null) return max(p.left).key;//對應了第1種情況，如果左子樹不為空，則前驅一定是左子樹的最大值，即小於p的最大值（左子樹的值都小於p節點）
        //以下是左子樹為空的情況2.1
        else if(pp.right==p) return pp.key;
        //以下是左子樹為空的情況2.2
        else if(pp.left==p) return first_parent.key;
        return -1;
    }

向上取整和向下取整

向上取整是指大於等於該鍵的最小鍵，向下取整是指小於等於該鍵的最小值。

向下取整與前驅後繼節點的區別在於查找前驅後繼節點對應的參數是樹中的某一個節點鍵，而向下取整則允許接受任意的鍵作為參數，另一方面，向下取整可以包含等於自己的鍵，是小於等於

關於向上取整與向下取整這兩個操作，我只在演算法(第四版)上面見到過，在其他的相關文章中沒有遇到，不過我感覺咱們可以體會一下它的思想，畢竟我感覺這個操作也蠻重要的。

我們拿上圖中查找19前驅節點為例說明一下流程：首先，在以41為根節點的樹中查詢，由於19<41,在41的左子樹查詢，即在以20為根節點的樹中查詢。接著因為19<20,繼續向左，在以11為根結點的樹中查詢。集中注意力，因為19>11,所以11有可能是19的前驅節點，但是前提是11的右子樹中沒有比19小的元素。也就是說我們應該先在11的右子樹中尋找，然後判斷尋找的情況（命中或未命中），如果命中，那就自動返回結果了，如果沒有命中，則說明11就是19的前驅節點!，這其中查找的過程是一個遞歸的過程！希望你仔細體會:)

我只能說到這裡了，不好理解:(。具體實現如下：

public int floor(int key){
    Node x=floor(root,key);
    if(x==null) return -1;//未查找到
    return x.key;
}
private Node floor(Node x,int key){
    if(x==null) return null;//表示在以x為根節點的樹中沒有查找到
    if(key=x.key) return x;//命中，且恰好在根節點x
    if(key<x.key) return floor(x.left,key);//在x的左子樹中查詢，根節點有x變為x的子節點，數據規模減小
    //往下走說明key>x.key,這個時候要去x的右子樹去尋找
    Node  t=floor(x.right,key);//在右子樹中尋找
    if(t!=null) return t;//在右子樹中找到了
    else return x;//在右子樹中沒有找到，那就說明x節點就是要求的前驅節點
}

向上取整的程式碼類似，我這裡就不詳細說了，你可以自己實現一下。

刪除操作

二叉樹的刪除操作就相對比較複雜了。希望你打起十二分的精神！刪除一個結點只會對一顆二叉查找樹的局部產生一定的影響，所以，我們的任務就是恢復刪除這個結點所帶來的影響。

刪除操作也有遞歸演算法，不過我很迷，而且我見很多地方也不是用遞歸實現的，所以這裡就不再介紹了，感興趣的話可以看一下演算法（第四版），上面有詳細的介紹。好了，不啰嗦了，咱們繼續~

針對待刪除結點的子節點個數的不同，我們將它分為三種情況加以處理。

1.如果要刪除的結點沒有子節點，此時的操作時十分容易的，我們只需要將父節點中指向該節點的鏈接設置為null就可以了。請看下圖,我們的任務是刪除結點27,找到這個節點後直接抹去就 OK 了。

2.如果要刪除的節點只有一個子節點(只有左子節點或只有右子節點)，這種情況也不複雜。我們只需要更新父節點中的指向待刪除結點的鏈接即可，讓它指向待刪除結點的子節點即可。請看下圖，我們的目標是刪除節點50:

3.如果要刪除的節點有兩個子節點，這時就變得複雜了。你聽我仔細描述以下這個過程：我們需要找到這個節點的右子樹上的最小結點【記為H】（因為它沒有左子節點），把【H】替換到我們計劃刪除的節點上；然後，再刪除這個最小的節點【H】（因為它沒有左子節點，所以可以轉化成之前的兩種情況之一），而且，你會發現，二叉查找樹的性質被完美的保留了下來，驚不驚喜！

接下來請看下面這三個例子，它們分別能夠轉化為情況一和情況二：

第一幅圖，想要刪除節點20,它的右子樹的最小節點【H】沒有子節點

第二幅圖，想要刪除節點20,它的右子樹的最小節點【H】存在右節點

注意：【H】不可能有左節點，因為它是最小的

具體的程式碼如下:

    public void delete(int key){
        //如果找到鍵為key的結點，就將它刪除，找不到不做處理
        Node p=root;//p指向需要刪除的結點，這裡初始化為根節點
        Node pp=null;//pp記錄的是p的父節點
        
        //通過while循環查找Key結點
        while(p!=null&&p.key!=Key){
            pp=p;
            if(Key>p.Key) p=p.right;
            else p=p.left;
        }
        if(p==null) return;//沒有找到

        //情況一：要刪除的結點有兩個子結點
        if(p.left!=null&&p.right!=null){
            //查找右子樹的最小結點
            Node minP=p.right;//minP是右子樹的最小結點
            Node minPP=p;//minPP表示minP的父結點
            while(minP.left!=null){
                minPP=minP;
                minP=minP.left;
            }
            p.Key=minP.Key;p.val=minP.val;//替換p（將被刪除的結點）的鍵和值
            
            //轉化，以下問題只需要將minP刪除即可
            //因為minP作為右子樹最小的結點，肯定沒有左子結點，可以轉化為情況二處理
            p=minP;//使p指向右子樹的最小結點
            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) root=child;//刪除的是根結點
        else if(pp.left==p) pp.left=child;
        else pp.right=child;
    }

可以再根據下面這幅圖理解一下:)

理論分析

我們前面用了那麼大的力氣來講解二叉查找樹，那麼它的性能怎麼樣呢？

其實，對於二叉查找樹來說，不管是插入、刪除還是查找操作，時間複雜度都和樹的高度成正比，也就是O(H)，因為每次操作都對應了一條從根節點向下的一條路徑。而對於樹的高度，卻很可能因樹的形狀的不同而不同。

理想情況下，二叉查找樹是一顆完全二叉樹，每層的節點依次為 1、2、4、8、16…………，不難發現，樹的高度為log(N),所以時間複雜度為 O(logN),這是一個相當高效的演算法了。下面是一張表格，對常見的符號表的耗時成本做了一個簡單的對比。

據此可見二叉查找樹的性能，它能夠在O(logN)的時間複雜度內完成查找和插入操作，我們花這麼大力氣學習它是值得的！

但是，你有沒有注意到，它的最壞情況依舊是O(logN)。二叉查找樹在一定條件下可能會退化成鏈表，就像下圖所示，這明明就是一個彎曲的鏈表！

我們希望找到一種數據結構，它能保證無論鍵的插入順序如何，樹的高度將總是總鍵數的對數，這就是平衡二叉查找樹，更精確一點，我們在下一篇文章中介紹紅黑樹！（預告一下）

好了，今天的內容就到這裡了，希望你能夠對二叉查找樹有一個更深的理解，另外，記得一定要動手敲程式碼！咱們下期見紅黑樹。

碼字繪圖不易，如果覺得本文對你有幫助，點贊支援一下作者！

另外，歡迎大家關注我的公眾號：小超說，之後我會繼續創作演算法與數據結構以及電腦基礎知識的文章。也可以加我微信chao_hey,我們一起交流，一起進步！