資料結構基礎----二分搜尋樹

原文：https://loubobooo.com/2018/11/04/%E5%88%9D%E5%AD%A6%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E4%BA%8C%E5%88%86%E6%90%9C%E7%B4%A2%E6%A0%91/

前言

之前我們一直專注線上性資料結構上，在這一章要開始學習計算機領域應用及其廣泛的–樹結構。

樹的概括

下圖的資料存儲方式便是一種樹結構。

資料結構基礎----二分搜尋樹

和線性資料結構不同的是，線性的資料結構是把所有的資料排成一排，而樹結構更像是自然界中樹的枝杈，不斷延伸，不斷擴充，其本身也是一種天然的組織結構，類似于電腦中檔案夾這種目錄結構。

資料結構基礎----二分搜尋樹

将資料使用樹結構存儲後，出奇的高效，其中包括但不限于二分搜尋樹，平衡二叉樹，AVL，紅黑樹，堆，并查集，線段樹，Trie(字典樹，字首樹)

二分搜尋樹的基礎

在了解二分搜尋樹之前，我們首先明确二叉樹的概念，首先它和連結清單一樣，同樣屬于一種動态資料結構。

資料結構基礎----二分搜尋樹

可以看粗，二叉樹中每個元素存在于節點内，和連結清單不同的是，除了要存放元素e，還要有指向其他節點的left和right兩個變量(引用)。

對于樹結構來說，二叉樹也是最常用的一種資料結構，同時二分搜尋樹滿足二叉樹的性質(從本質上講，二分搜尋樹也是一棵二叉樹)
對于一棵二叉樹來說，它隻有一個根節點，并且這個根節點是唯一的(如下圖中28便是這棵二叉樹的根節點)
對于每一個節點來說，它最多隻能有兩個子節點，指向左和右的兩個節點(也可以稱之為左孩子和右孩子)
二叉樹中，一個孩子都沒有的節點，通常稱之為葉子節點

在這裡，不是所有二叉樹都像如下圖示的二叉樹這樣規整(每個節點都有兩個孩子，葉子節點也在最底層)

資料結構基礎----二分搜尋樹

葉子節點：這個節點沒有任何孩子節點，這樣的節點稱之為葉子節點

二叉樹有一個非常重要的性質，是具有天然的遞歸結構(對于每一個節點，它的左孩子同時也是一棵二分搜尋樹的根節點)。

如下圖示，這是一棵滿的二叉樹。即對于每一個節點來說，除了葉子節點外都有兩個孩子節點。

資料結構基礎----二分搜尋樹

如下圖所示，隻有左孩子，或者隻有右孩子，或者左右孩子都為空，甚至退化成連結清單等等，這些都滿足二叉樹的定義。

資料結構基礎----二分搜尋樹

下面可以來看下什麼是二分搜尋樹。二分搜尋樹除了滿足二叉樹的定義(隻有一個根節點，有左右孩子節點或者左右孩子節點為空……)，還有自己獨特的性質，即每個節點的值都要大于其左子樹下所有節點的值，同時每個節點的值小于其右子樹下所有節點的值。

如下圖示顧名思義，根節點28大于左子樹中最大的值22，并且根節點28小于右子樹最小的值29

資料結構基礎----二分搜尋樹

注：二分搜尋樹當然有可能不是一棵滿的二叉樹

為了要能達到這樣的性質，就必須讓我們存儲的元素具有可比較性，那麼我們用二分搜尋樹來存儲資料的話，然後來查找一個資料53就會非常簡單。由于41是根節點，是以根據二分搜尋樹的性質，53這個節點就一定在41的右子樹。這樣一來，41的左子樹所存儲的這些資料就會被忽略，這就大大地加快了查詢速度。

二分搜尋樹中添加元素

首先在最開始的時候，在二分搜尋樹裡一個節點都沒有

現在添加一個新的元素41，顯然這個節點會成為根節點
再來一個新元素28，從根節點出發，判斷28比根節點41小，根據二分搜尋樹的定義、是以添加到41的左子樹中
利用二分搜尋樹的定義，每次添加一個新的元素，從根節點開始，如果小于根節點就插到根節點的左子樹，反之插入到根節點的右子樹
這個過程以此類推……

注：我們此時的二分搜尋樹不包含重複元素

如果想包含重複元素的話，隻需定義：左子樹小于等于節點；或者右子樹大于等于節點

過程如圖示：

資料結構基礎----二分搜尋樹

代碼如下：

private class Node{
    public E e;
    public Node left, right;

    public Node(E e){
        this.e = e;
        left = null;
        right = null;
    }
}
private Node add(Node node, E e){
    if(node == null){
        // 将null的節點連接配接起來
        size++;
        return new Node(e);
    }
    // 這裡用遞歸，不斷調用左孩子節點，然後比較插入的元素和節點e
    if(e.compareTo(node.e) < 0){
        node.left = add(node.left, e);
    }else if(e.compareTo(node.e) > 0){ //e.compareTo(node.e) > 0
        node.right = add(node.right, e);
    }
    // 對相等的情況不做判斷了
    return node;
}

二分搜尋樹的查詢

對于查詢元素操作來說，隻需要看一下節點node所存的元素就好了，不必牽扯添加一個元素之後如何挂接到整個二分搜尋樹中，是以是相對簡單的。

代碼如下

// 看二分搜尋樹中是否包含元素e
public boolean contains(E e){
    return contains(root, e);
}

// 看以node為根的二分搜尋樹中是否包含元素e，遞歸算法
private boolean contains(Node node, E e){
    if(node == null){
        return false;
    }
    if(e.compareTo(node.e) == 0){
        return true;
    }else if(e.compareTo(node.e) < 0){
        return contains(node.left, e);
    }else{ // e.compareTo(node.e) > 0
        return contains(node.right, e);
    }
}

二分搜尋樹的前中後序周遊

前序周遊

對于一個資料結構的周遊，本質很簡單，就是把這個資料結構中所存儲的所有元素都通路一遍。對應到二分搜尋樹便是通路一遍所有節點。
對于線性資料(無論數組還是連結清單)，從頭到尾做一層循環就解決了，但是對于樹結構來說卻不是。要通路整個二叉樹所有節點，需要考慮左子樹所有節點，還要考慮右子樹所有節點。

在通路完根節點，先通路了左子樹，再通路了右子樹，這就完成了二叉樹的周遊操作，而這種周遊操作也稱之為前序周遊。

用代碼來實作：

// 二分搜尋樹的前序周遊
public void preOrder(){
    preOrder(root);
}

// 前序周遊以node為根的二分搜尋樹，遞歸算法
private void preOrder(Node node){
    if(node == null){
        return;
    }
    preOrder(node.left);
    preOrder(node.right);
}

中序周遊

通常而言，對于二分搜尋來說。前序周遊是最自然的一種周遊方式，同時呢也是最常用的一種周遊方式。

如果我們改變節點的通路順序，使之先通路該節點的左子樹，再通路該節點，最後通路該節點的右子樹，這樣的周遊操作稱之為中序周遊。

用代碼實作

//中序周遊以node為根的二分搜尋樹，遞歸算法
public void inOrder(){
    inOrder(root);
}

private void inOrder(Node node){
    if(node == null){
        return;
    }
    inOrder(node.left);
    inOrder(node.right);
}

後序周遊

同理，先通路該節點的左子樹，再通路該節點的右子樹，最後通路這個節點，這樣的周遊操作便是後序周遊。

用代碼實作

// 二分搜尋樹的後序周遊
public void postOrder(){
    postOrder(root);
}

// 後序周遊以node為根的二分搜尋樹，遞歸算法
private void postOrder(Node node){
    if(node == null){
        return;
    }
    postOrder(node.left);
    postOrder(node.right);
}

二分搜尋樹的層序(廣度優先)周遊

上述二分搜尋樹的前中後序周遊，本質上都是深度優先的周遊。于此相對應的是廣度優先周遊(即層序周遊)。

廣度優先周遊

對于二分搜尋樹來說，每一個節點對應右一個深度值，通常會把根節點叫做深度為0相應的節點。層序周遊就是，先周遊第0層的節點(28)，再周遊第1層的節點(16，30)，最後周遊第2層的節點(13，22，29，42)。

如下圖示：

資料結構基礎----二分搜尋樹

用代碼實作

// 二分搜尋樹的層序周遊
public void levelOrer(){
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    while(!queue.isEmpty()){
        // 目前周遊的節點 等于 隊列中的元素出隊之後的那個元素
        Node cur = queue.remove();
        System.out.println(cur.e);
        if(cur.left != null){
            queue.add(cur.left);
        }
        if(cur.right != null){
            queue.add(cur.right);
        }
    }
}

意義

更快的找到問題的解
常用于算法設計中-最短路徑
圖中的深度優先周遊和廣度優先周遊

二分搜尋樹删除節點

删除最大值和最小值

對于二分搜尋樹來說，删除一個節點相對是比較複雜的操作。是以分解删除操作，從最簡單的，删除二分搜尋樹的最小值和最大值開始。

首先，要想删除二分搜尋樹的最小值和最大值，就需要先找到二分搜尋樹的最小值和最大值
對于二分搜尋樹來說，其一個節點的左子樹中所有節點都小于該節點
是以删除最小值一定是從根節點開始，不停的向左走，直到向左走再也走不動為止，那個值一定是最小值
删除最大值同理

用代碼實作：

// 尋找二分搜尋樹的最大元素
public E maximum(){
    if(size == 0){
        throw new IllegalArgumentException("BST is empty!");
    }
    return minimum(root).e;
}

// 傳回以node為根的二分搜尋樹的最大值所在的節點
private Node maximum(Node node){
    if(node.right == null){
        return node;
    }
    return minimum(node.right);
}

// 從二分搜尋樹中删除最小值所在節點，傳回最小值
public E removeMin(){
    E ret = minimum();
    root = removeMin(root);
    return ret;
}

// 删除以node為根的二分搜尋樹中的最小節點
// 傳回删除節點後新的二分搜尋樹的根
private Node removeMin(Node node){
    // 現在最小節點就是node本身，然後接上node.right
    if(node.left == null){
        Node rightNode = node.right;
        node.right = null;
        size--;
        return rightNode;
    }
    node.left = removeMin(node.left);
    return node;
}

// 從二分搜尋樹中删除最大值所在節點，傳回最大值
public E removeMax(){
    E ret = maximum();
    root = removeMax(root);
    return ret;
}

// 删除以node為根的二分搜尋樹中的最大節點
// 傳回删除節點後新的二分搜尋樹的根
private Node removeMax(Node node){
    // 現在最小節點就是node本身，然後接上node.right
    if(node.right == null){
        Node leftNode = node.left;
        node.left = null;
        size--;
        return leftNode;
    }
    node.right = removeMax(node.right);
    return node;
}

删除任意節點

在二分搜尋樹中删除任意節點，會出現以下3種情況：

删除隻有左孩子的節點
要删除的節點元素58這種情況，與删除最大值的邏輯相同，并在删除完成之後，讓左孩子所在的二叉樹挂接到原來父親節點

過程如下圖所示：

資料結構基礎----二分搜尋樹

用代碼實作：

// 待删除節點右子樹為空的情況
if(node.right == null){
    Node leftNode = node.left;
    node.left = null;
    size--;
    return leftNode;
}

删除隻有右孩子的節點
要删除的節點元素58這種情況，與删除最大值的邏輯相同，并在删除完成之後，讓左孩子所在的二叉樹挂接到原來父親節點

過程如下圖所示：

資料結構基礎----二分搜尋樹

用代碼實作：

// 待删除節點左子樹為空的情況
if(node.left == null){
    Node rightNode = node.right;
    node.right = null;
    size--;
    return rightNode;
}

删除左右都有孩子的節點d
1. 找到d節點右子樹中最小的值，即s=min(d->right)
2. 删除s節點，即delMin(d->right)
3. 連接配接上之前d的左子樹，即s->right。連接配接上之前d的右子樹，即s->left
4. 删除d,使s成為新的子樹的根

注：

->

表示指向

過程如下圖所示：

資料結構基礎----二分搜尋樹

用代碼實作：

// 待删除節點左右子樹均不為空的情況
// 找到比待删除節點大的最小節點，即待删除節點右子樹的最小節點
// 用這個節點頂替待删除節點的位置,successor --> 後繼
Node successor = minimum(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;

node.left = node.right = null;
return successor;

完整代碼實作

// 從二分搜尋樹中删除元素為e的節點
public void remove(E e){
    root = remove(root, e);
}

// 删除以node為根的二分搜尋樹中值為e的節點，遞歸算法
// 傳回删除節點後新的二分搜尋樹的根
private Node remove(Node node, E e){
    if(node == null){
        return null;
    }
    if(e.compareTo(node.e) < 0){
        node.left = remove(node.left, e);
        return node;
    }else if(e.compareTo(node.e) > 0){
        node.right = remove(node.right, e);
        return node;
    }else{ // e == node.e

        // 待删除節點左子樹為空的情況
        if(node.left == null){
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }
        // 待删除節點右子樹為空的情況
        if(node.right == null){
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }
        // 待删除節點左右子樹均不為空的情況
        // 找到比待删除節點大的最小節點，即待删除節點右子樹的最小節點
        // 用這個節點頂替待删除節點的位置,successor --> 後繼
        Node successor = minimum(node.right);
        successor.right = removeMin(node.right);
        successor.left = node.left;

        node.left = node.right = null;
        return successor;
    }
}

資料結構基礎----二分搜尋樹

原文：https://loubobooo.com/2018/11/04/%E5%88%9D%E5%AD%A6%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E4%BA%8C%E5%88%86%E6%90%9C%E7%B4%A2%E6%A0%91/

前言

樹的概括

二分搜尋樹的基礎

二分搜尋樹中添加元素

二分搜尋樹的查詢

二分搜尋樹的前中後序周遊

前序周遊

中序周遊

後序周遊

二分搜尋樹的層序(廣度優先)周遊

意義

二分搜尋樹删除節點

删除最大值和最小值

删除任意節點

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器