Java簡單幾步實現一個二元搜尋樹

2023-02-08 22:00:49

1、認識二元搜尋樹

從字面上來看，它只比二元樹多了搜尋兩個字，我們回想一下，如果要是在二元樹中查詢一個元素的話，需要遍歷這棵樹，效率很慢，而二元搜尋樹，則會效率高很多，為什麼呢？

二元搜尋樹，可以是一棵空樹，或者是具有以下的性質：

若它的左子樹不為空，則左樹上所有的節點都小於根節點
若它的右子樹不為空，則右樹上所有節點的都大於根節點
它的左子樹和右子樹也分別為二元搜尋樹

通俗來講，左孩子都小於父節點，右孩子都大於父節點，以此類推，這裡我們畫圖來認識下二元搜尋樹：

當然二元搜尋樹不要求是完全二元樹或滿二元樹，甚至會出現單分支的二元搜尋樹，所以針對這種特殊的情況進行了優化也就延申而來的 AVL樹，這個是後續的話題。

仔細觀察上圖，可以觀察出二元搜尋樹的一個新特性：

中序遍歷二元搜尋樹是有序的，所以二元搜尋樹也被稱為二叉排序樹。

2、實現一個二元搜尋樹

2.1 成員變數

public class BinarySearchTree {
    private TreeNode root; //存放根節點
    private static class TreeNode {
        private int val;
        private TreeNode left;
        private TreeNode right;
        private TreeNode(int val) {
            this.val = val;
        }
    }
}

這裡跟我們的二元樹成員變數大同小異，主要是去實現插入，查詢，刪除的邏輯。

2.2 insert 方法

往二元搜尋樹插入一個節點的時候，我們要注意兩點，首先如果二元搜尋樹為空，則直接令 root 為當前插入的節點即可，那如果二元搜尋樹不為空，我們則需要利用二元搜尋樹的性質，找到該節點要插入的位置即可，具體我們來看下圖：

通過動圖我們可以看到，當二元搜尋樹不為空的時候，新的元素會依次節點比較，如果比根節點大，則去根的右邊，比根節點小，則取根的左邊，以此類推。(搜尋二元樹不存在相同的元素)

但是我們用程式碼如何實現呢？定義一個 cur 參照，當 cur 等於 null 了，則表示是我要插入的位置，既然找到了要插入的位置，但是還得知道這個位置的父節點是誰，通過父節點的指標域給連線起來，於是程式碼可以這樣寫：

public boolean insert(int key) {
    // 二元搜尋樹沒有節點的情況
    if (root == null) {
        root = new TreeNode(key);
        return true;
    }
    // 二元搜尋樹不為空的情況 -> 找到該節點要插入的位置進行插入
    // 如果已經存在該節點了, 則不用插入 -> 二元搜尋樹中不能出現重複值
    TreeNode parent = null; // 記錄cur的父節點
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val < key) {
            parent = cur;
            cur = cur.right;
        } else if (cur.val > key) {
            parent = cur;
            cur = cur.left;
        } else {
            return false; // 插入重複的節點
        }
    }
    // 走到這, cur為空了, key 需要插入到 parent 的左節點或右節點中
    TreeNode newNode = new TreeNode(key);
    if (parent.val < key) {
        parent.right = newNode;
    } else {
        parent.left = newNode;
    }
    return true;
}

2.3 search 方法

搜尋方法，也就是給一個 key 你，讓你在這顆二元樹找有沒有這個元素，有的話返回該節點，沒有的話返回 null，這個就很簡單了，跟上面的步驟一樣無非就是碰到相同的元素返回 cur 嘛，當 cur 根據 key 遍歷完這棵二元搜尋樹的時候，也就是 cur 為 null 了，則表示沒有該元素，直接返回 null即可。

程式碼如下：

public TreeNode search(int key) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val < key) {
            cur = cur.right;
        } else if (cur.val > key) {
            cur = cur.left;
        } else {
            return cur;
        }
    }
    return null;
}

2.4 remove 方法(重點)

在二元搜尋樹中，刪除一個節點是一個比較麻煩的事，但是隻要把各種刪除的情況下列舉出來，一一解決它即可，對於二元搜尋樹來說，你刪除了一個節點，它仍然滿足二元搜尋樹的性質。

設 cur 為要刪除的節點，所以首先我們得判斷這個二元搜尋樹中，是否存在要刪除的節點，這個邏輯上面已經寫過了，找到要刪除的節點後，我們一共會面臨三種情況：

① 如果 cur 沒有左子樹的情況

如果 cur 是 root 的情況，只需要 root = cur.right
如果 cur 不是 root，cur 是 parent.left 的情況，只需要 parent.left = cur.right
如果 cur 不是 root，cur 是 parent.right 的情況，只需要 parent.right = cur.right

圖解：

② 如果 cur 沒有右子樹的情況

如果 cur 是 root 的情況，只需要 root = cur.left
如果 cur 不是 root，cur 是 parent.left 的情況，只需要 parent.left = cur.left
如果 cur 不是 root，cur 是 parent.right 的情況，只需要 parent.right = cur.left

圖解：

③ 如果 cur 既有左子樹，又有右子樹的情況

使用替換法進行刪除，即在 cur 的右子樹中，一直往左尋找最小的元素，將這個最小值賦值給要刪除節點的 val 值中，接著把這個最小元素的節點刪除即可，刪除的邏輯見下圖和完整刪除程式碼。

程式碼如下：

public boolean remove(int key) {
    TreeNode parent = null;
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val < key) {
            parent = cur;
            cur = cur.right;
        } else if (cur.val > key) {
            parent = cur;
            cur = cur.left;
        } else {
            removeNode(parent, cur);
            return true;
        }
    }
    return false;
}
private void removeNode(TreeNode parent, TreeNode cur) {
    if (cur.left == null) {
        if (cur == root) {
            root = cur.right;
        } else if (cur == parent.left) {
            parent.left = cur.right;
        } else {
            parent.right = cur.right;
        }
    } else if (cur.right == null) {
        if (cur == root) {
            root = cur.left;
        } else if (cur == parent.left) {
            parent.left = cur.left;
        } else {
            parent.right = cur.left;
        }
    } else {
        TreeNode target = cur.right;
        TreeNode targetParent = cur;
        while (target.left != null) {
            targetParent = target;
            target = target.left;
        }
        // 走到這, target就是要刪除節點的右子樹中最小的節點, 接下來進行覆蓋
        cur.val = target.val;
        // 覆蓋完成, 現在需要刪除 target 節點
        // 如果 cur.right 沒有左孩子的情況, 此時的target就是cur.right
        // 即直接將 cur.right 覆蓋到 cur 位置, 也就是滿足 target == targetParent.right 條件
        // 所以需要進行特殊處理.
        if (target == targetParent.right) {
            targetParent.right = target.right;
        } else {
            targetParent.left = target.right;
        }
    }
}

3、二元搜尋樹總結

二元搜尋樹在最好的情況下為完全二元樹，查詢的平均比較次數為：logn

二元搜尋樹在最差的情況下退化成但分支，查詢的平均比較次數為：n/2

所以二元搜尋樹在最差的情況下效率是不高的，為了解決單分支的情況，於是有了 AVL樹，當發現二元搜尋樹左右子樹高度差太大，會自動旋轉，以致平衡，避免旋轉的次數太多，又引入了紅黑樹，給節點增加了顏色，細節部分後期講解，這裡有個概念即可，下期將會介紹由紅黑樹作為底層的集合：TreeSet 和 TreeMap

下期預告：【Java 資料結構】TreeSet 和 TreeMap

到此這篇關於Java簡單幾步實現一個二元搜尋樹的文章就介紹到這了,更多相關Java二元搜尋樹內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！