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

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

在資料結構中，二叉查找樹無疑是極為重要的，但是初學者理解起來卻有些吃力，網上的文章講得也不太全面，本文希望結合多組動圖、圖片以及詳細的代碼實作，力爭讓大家完全掌握二叉查找樹（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=https://www.cnblogs.com/chaotalk/p/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=https://www.cnblogs.com/chaotalk/p/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,我們一起交流，一起進步！

標籤：其他

上一篇：0052. N-Queens II (H)

下一篇：1.1排序演算法的穩定性