目錄

• 二叉搜索樹（Binary Search Tree）
  • 回顧與思考
  • 概念
  • 設計
    • 提示Tip
    • 屬性與方法
    • Add方法
    • Remove方法
  • 小結
• 宣告

二叉搜索樹（Binary Search Tree）

回顧與思考

我們來思考這么一個問題，如何在n 個動態的整數中搜索某個整數？（查看其是否存在）

看著還是很簡單的，以動態陣列存放元素，從第0個位置開始遍歷搜索，運氣好的話，第一個就找到了，運氣差的話，可能找到最后都找不到，算一下的話平均時間復雜度是 O(n)，資料規模大的話，是比較慢的

再好一點的話，上一篇 二分查找及其變種演算法 說到了，使用二分查找的話，效率是很高的，最壞時間復雜度：O(logn)，不怕你資料規模大，但是我們要注意一點，這是一個動態的序列，而前面也說到了二分查找針對的是有序集合，那么維護這樣的一個有序的集合，每次修改資料，都需要重新排序，添加、洗掉的平均時間復雜度是O(n)，對于這種動態的資料集合，二分查找的優勢并不明顯，二分查找更適合處理靜態資料，也就是沒有頻繁的資料插入、洗掉操作，

那么針對這個需求，有沒有更好的方案？能將添加、洗掉、搜索的最壞時間復雜度均可優化至：O(logn)，主角登場，二叉搜索樹可以辦到，

概念

定義：是二叉樹的一種，是應用非常廣泛的一種二叉樹，英文簡稱為BST又被稱為：二叉查找樹、二叉排序樹

圖解：

性質：

• 任意一個節點的值都大于其左子樹所有節點的值
• 任意一個節點的值都小于其右子樹所有節點的值
• 它的左右子樹也是一棵二叉搜索樹

使用二叉搜索樹可以大大提高搜索資料的效率，同時也需要注意一點，二叉搜索樹存盤的元素必須具備可比較性，同時不能為null， 比如int、double等，如果是自定義型別，需要指定比較方式，這一點在后面會仔細講到

設計

提示Tip

? 閱讀下面的文章之前，我希望你是讀過我的上一篇文章 — 深入理解二叉樹 的，因為二叉搜索樹并不是一中的新的資料結構，它是有二叉樹衍生出來的概念，也就是說它同樣是二叉樹，只不過是在二叉樹的基礎上，我們對其加入了一些邏輯規則，我希望它的添加是這樣的，比我小的往左拐，比我大的往右拐，

? 也就是說二叉樹與二叉搜索樹的節點設計都是一樣的，同樣，二叉樹的通用方法也能夠被二叉搜搜索樹使用，因為我們的二叉搜索樹會繼承二叉樹，在其基礎上封裝一些新的特性，規則，所以，一些通用方法，比如說判斷葉子節點，尋找前驅、后繼節點，獲取樹的高度、節點數量，包括最有趣的遍歷都是寫在二叉樹中，這些通用方法，是我們接下來會用到的，包括節點類的設計，這些都已經在上篇文章了，這里不會占用篇幅寫了，不熟悉的話，回去翻一翻，知識這東西，就要多過一過腦子

屬性與方法

屬性：

//接收用戶自定義比較器
private Comparator<E> comparator;

公開方法：

• void add(Eelement) —— 添加元素
• void remove(Eelement) —— 洗掉元素
• boolean contains(Eelement)—— 是否包含某元素

在基于二叉樹的基礎上，只需要增加上面這3個介面方法，看完這些方法設計，與之前撰寫的動態陣列，鏈表是不是有一些區別，沒錯，少了index，對于我們現在使用的二叉樹來說，它的元素沒有索引的概念，為什么？我們不是可以按照從上到下，從左到右，進行編號嗎？例如下圖：

但是這樣不對，沒有意義，比如，我們再一個添加，11,15的元素進來，按照二叉排序樹，11 > 8 —> 往右子樹走，11 > 10 —> 在往右走，11 < 14 —> 往左走，11 < 13 —>往左走，發現沒有元素，插入該位置，15也是一樣，那么得出來的結果應該是：

這樣的編號索引與我們之前陣列與鏈表的先入先編號是不一樣，所以在二叉搜索樹中沒有索引的概念

Add方法

方法步驟：

1、找到父節點parent

2、創建新節點node

3、parent.left = node或者parent.right=node

注意點：如果要插入的值暈倒相等的元素該如何處理？

• 直接return，不作處理
• 覆寫原有節點 （建議）

我們一步一步來，首先，我們前面說到，添加的元素必須具備可比較性，所以不能為null，這樣我們需要一個元素非空檢查的方法

/**
 * 新節點元素非空檢查
 * @param element
 * @return
 */
private void elementNotNullCheck(E element){
    if (element == null){
        throw new IllegalArgumentException("element must not be null");
    }
}

接下來我們開始找父節點parent，這里要注意的是，遍歷查找父節點時，我們是從根節點root開始，如果當前是空樹，那么不用找，直接新節點就是根節點，如果樹不為空，那么我們就要從根節點開始找父節點，這是我們重點分析的地方

前面說到了，二叉搜索樹存盤的元素必須具備可比較性，在這里就體現了，找尋父節點的程序就是我們不斷比較的程序，所以我們還需要一個比較方法，用于比較兩個元素的大小

/**
 * 比較函式，回傳0，e1==e2;回傳值大于0，e1>e2;回傳小于0，e1<e2
 * @param e1
 * @param e2
 * @return
 */
private int compare(E e1,E e2){
	return 0;
}

方法的邏輯我們先不寫，這是因為我們的二叉樹在設計上是泛型類，是支持存盤任意型別的，對于Java官方提供的int、double這種基本的數值型別，或者是Integer、Double、String這些實作了比較介面的Comparable來說，比較邏輯是很好寫的，但是對于我們自定義的類，比如Person來說，這是不行的，因為不具備可比較性，同時我們也不知道比較規則

public class BinarySearchTree<E> {
    //...
}

public class Person {

    /**
     * 年齡
     */
    private int age;

    public Person(int age) {
        this.age = age;
    }
}

針對上面說到缺點，我們可以通過以下方法解決：

1、強制要求實作java.lang.Comparable介面，重寫public int compareTo(T o);方法，自定義比較規則

public class BinarySearchTree<E extends Comparable<E>>{
    //....
}

例如：Person 類

public class Person implements Comparable<Person> {

    private int age;

    public Person(int age) {
        this.age = age;
    }

    /**
     * 自定義比較規則
     * @param p
     * @return
     */
    @Override
    public int compareTo(Person p) {
        return Integer.compare(age, p.age);
    }
}

這樣子就可以在BinarySearchTree二叉搜索樹中的compare方法中呼叫重寫的compareTo方法，實作比較邏輯，但是這樣寫有一些不好的地方，比如說，對于傳入的型別進行了強制要求，同時，由于比較規則是撰寫在Person類中的，對于一個類來說只能自定一種比較規則，很不方便，

2、撰寫實作java.util.Comparator介面的匿名內部類，重寫int compare(T o1, T o2);方法

同時在BinarySearchTree類中，添加接收用戶自定義比較器的屬性，這樣做能可以實作按照自定義規則，撰寫不同的比較器

//接收用戶自定義比較器
private Comparator<E> comparator;

/**
 * 建構式
 * @param comparator
 */
public BinarySearchTree2(Comparator comparator) {
    this.comparator = comparator;
}

這時候，只需要在實體化二叉搜索樹時，傳入比較器就行，例如;

BinarySearchTree<Person> bSTree = new BinarySearchTree<>(new Comparator<Person>() {
    //自定義比較規則
    @Override
    public int compare(Person o1, Person o2) {
        return o1.getAge() - o2.getAge();
    }
});

但是，這樣子還是不好，因為在實體化時，如果沒有傳入比較器，編譯器檢測就會報錯，那么就有了第3種方法

3、保留Comparable和Comparator介面，同時提供無參構造，與帶參構造

/**
 * 無參構造
 */
public BST() {
    this(null);
}

/**
 * 建構式
 * @param comparator
 */
public BST(Comparator<E> comparator) {
    this.comparator = comparator;
}

這樣的話，如果用戶有傳入比較器的話，就用比較器，沒有的話默認用戶實作了Comparable介面，對傳入的類強轉為Comparable，如果都沒有，自然會編譯錯誤，拋出例外，這樣BinarySearchTree中的compare應該這么寫:

/**
 * 比較函式，回傳0，e1==e2;回傳值大于0，e1>e2;回傳小于0，e1<e2
 * @param e1
 * @param e2
 * @return
 */
private int compare(E e1,E e2){
    if (comparator != null){
        return comparator.compare(e1,e2);
    }
    return ((Comparable)e1).compareTo(e2);
}

完成了這些就是添加節點方法了，實作了上面的函式后，其實就很好寫了，無非就是小的往左，大的往右，等于的的覆寫

add方法

/**
 * 向二叉樹添加節點
 * @param element
 */
public void add(E element){
    elementNotNullCheck(element);

    //空樹，添加第一個節點
    if (root == null){
        root = new Node<>(element,null);
        size++;
        return;
    }

    //非空樹情況,找到其父節點
    Node<E> node = root;
    //記住找到的父節點，默認根結點
    Node<E> parent = root;
    //記住最后一次的比較情況
    int cmp = 0;
     while (node != null){
        cmp = compare(element,node.element);
        if (cmp > 0){
            parent = node;
            //大于父節點值，取右子節點比較
            node = node.right;
        }else if (cmp < 0){
            parent = node;
            //小于父節點值，取左子節點比較
            node = node.left;
        }else {
            //相等，第1種處理方法，不處理
            //return;
            //相等，第2種處理方法，覆寫原有節點
            node.element = element;
        }
     }

     //插入新節點
     Node<E> newNode = new Node<>(element,parent);
     if (cmp > 0){
        parent.right = newNode;
     }else {
         parent.left = newNode;
     }
     size++;
}

Remove方法

方法步驟：

1、根據傳入的元素查找節點

2、將找到的節點洗掉

大體上是這兩個步驟，先分析一下第一個步驟，實際上就是我們前面思考題中說到的查找演算法嘛，實作起來也比較簡單，因為我們的二叉搜索樹都是排序好的，上代碼：

/**
 * 查找元素為element的節點
 * @param element
 * @return
 */
private Node<E> node(E element) {
    Node<E> node = root;
    while (node != null) {
        int cmp = compare(element, node.element);
        if (cmp == 0) return node;
        if (cmp > 0) {
            node = node.right;
        } else {
            // cmp < 0
            node = node.left;
        }
    }
    return null;
}

有了node方法,我們的contains方法也很好寫了，直接呼叫就可以了

/**
 * 判斷樹是否包含值為element的節點
 * @param element
 * @return
 */
public boolean contains(E element) {
    return node(element) != null;
}

洗掉找到的節點，這里比較復雜了，根據節點的度，有以下三種情況：

1、葉子節點

2、度為 1 的節點：

2、度為 2 的節點：

洗掉節點度為2的節點，做法是找到它的前驅節點，或者后繼節點，例如上圖，要洗掉的節點是5，按照二叉搜索樹的規則，要找到一個節點代替5的位置，使其程成為一個新的二叉搜索樹，那么這個節點就是要洗掉的節點的左子樹節點的最大值，或者右子樹的最小值，也就是器前驅節點，或者后繼節點，這里如果不熟悉的回去上一篇深入理解二叉樹 翻一翻相關概念

上代碼咧：

/**
 * 洗掉元素為element的節點
 * @param element
 */
public void remove(E element) {
    remove(node(element));
}


/**
 * 洗掉傳入的節點
 * @param node
 */
private void remove(Node<E> node) {
    if (node == null) return;

    size--;
    // 洗掉度為2的節點，實際上是轉化為洗掉度俄日1或者0node節點
    if (node.hasTwoChildren()) {
        // 找到后繼節點
        Node<E> s = successor(node);
        // 用后繼節點的值覆寫度為2的節點的值
        node.element = s.element;
        // 洗掉后繼節點
        node = s;
    }

    // 洗掉node節點（node的度必然是1或者0）
    Node<E> replacement = node.left != null ? node.left : node.right;
    // node是度為1的節點
    if (replacement != null) {
        // 更改parent
        replacement.parent = node.parent;
        // 更改parent的left、right的指向
        if (node.parent == null) { // node是度為1的節點并且是根節點
            root = replacement;
        } else if (node == node.parent.left) {
            node.parent.left = replacement;
        } else { // node == node.parent.right
            node.parent.right = replacement;
        }
    } else if (node.parent == null) { // node是葉子節點并且是根節點
        root = null;
    } else { // node是葉子節點，但不是根節點
        if (node == node.parent.left) {
            node.parent.left = null;
        } else { // node == node.parent.right
            node.parent.right = null;
        }
    }
}

小結

到這里，二叉搜索樹的相關內容就學習完了，也可以解釋文章開頭的思考題了，二叉搜索樹能將添加、洗掉、搜索的最壞時間復雜度均可優化至：O(logn)，由于二叉搜索樹的排序性質，無論是添加、洗掉、查找，從根節點開始，根據小向左，大向右的情況，每向下一層，都會淘汰掉令一半的子樹，這是不是跟二分搜索特別的像，再差就是查找到樹的最底層，所以說添加、洗掉、搜索的時間復雜度都可優化到O(logn)

宣告

文章為原創，歡迎轉載，注明出處即可

個人能力有限，有不正確的地方，還請指正

本文的代碼已上傳github,歡迎star —— GitHub地址

標籤：其他

上一篇：CTF-BugKu-WEB-21-34

下一篇：應對機器學習中類不平衡的10種技巧