Day18. 二元搜尋樹(Binary Search Tree)的 CRUD - 修改(Update)和刪除(Delete)

15th鐵人賽

雜食性的貓

2023-10-03 22:46:46

311 瀏覽

分享至

如昨天講的，今天主要會討論二元搜尋樹的刪除與修改。今天寫標題才突然想到，如果 Create 我指的是創建整棵樹，那好像刪除也要同等是講整棵樹，不過今天要討論的刪除是著重在節點的刪除，而修改指的是節點的插入。
BST 作為有序的樹結構，插入和刪除節點都有一定的步驟必須遵循，以維持左子樹全部節點小於根節點、右子樹全部節點大於根節點的這個規則。

Insert into a Binary Search Tree

給定一棵 BST，插入一個指定數值的節點，並在插入後要依然保持為 BST，BST 可能有多種可能，回傳任一種皆可。
遞迴起手式，想一下函式定義：給定 BST 根結點，給定插入點的值，回傳新的根結點。
如果根節點為 null，則直接回傳新的值構成的節點就好。
其餘情況，如果值小於當前節點，表示他的位置在左子樹，讓左子樹回傳他的根節點上來，符合上一行的函式定義，所以這邊遞迴進去就好，左子樹指向回傳回來的新根節點。右子樹反之亦然。
過完左右子樹的插入，我們可以判斷這個點應該被插入在哪個位置了，回傳根結點，結束。

public class Solution {
    public TreeNode InsertIntoBST(TreeNode root, int val) {
        if(root == null){
            return new TreeNode(val);
        }
        if(root.val > val){
            root.left = InsertIntoBST(root.left, val);
        }
        if(root.val < val){
            root.right = InsertIntoBST(root.right, val);
        }
        return root;
    }
}

這題的遞迴可能稍微抽象一點，但是也是個「知道函式定義跟終止條件後，遞迴看起來可能有點怪，但就是會對」，如果不能理解為什麼這樣能跑出來，可以手畫一下圖，就能知道插入的邏輯，基本的遞迴邏輯就是上面描述的那樣。

假設上面這棵樹要插入 3，最後 3 就會插入到：

一如這樣的例子，新插入的點必然可以成為某個樹的葉子節點(在 BST 的定義下)，我們並不需要去移動其他點與點之間的關聯，所以操作上還相對簡單。但在刪除節點，可就不是這麼回事了，讓我們繼續看下去。

Delete Node in a BST

題目給定一棵 BST 的根節點以及一個要被刪除的節點的值，讓我們回傳新的 BST 的根節點。
當然，第一步肯定是先找到該節點，找不到節點，也就沒辦法操作。
對一個 BST 的節點來說，總共有三種可能，沒有子節點、有一個子節點、有兩個子節點。
如果要刪除一個點，那分別的影響是：

沒有子節點：不影響，直接刪除節點就好
有一個子節點：讓那個子節點來頂替要被刪除節點的位置
有兩個子節點：最麻煩的情況，不能直接拿任一個子節點來補，例如直接相連的左子節點如果還有右子節點，那那個左子節點的右子節點必定大於左子節點本身的值(BST 的定義)。所以為了滿足 BST 的定義，我們必須補上左子樹中最大的點或右子樹最小的點 ─ 要再做一次搜尋的動作。

可以想見如果是沒有子節點的情況下，我們會讓父節點指向 null，一個子節點是讓父節點指向該子節點，有兩個子節點則是透過規則找到頂替的點後，讓父節點指過去。
可以知道在我們的操作裡，我們關心的是「父節點指向的點」。
假如我們要用遞迴來寫，一樣想清楚這個 DeleteNode 本身的定義，「給定一棵樹，於樹中尋找指定值，回傳根節點」。
也就是說我們 return 的對象必定為根節點本身，或是取代的新節點。

沒有子節點與有一個子節點的情況都好處理，就是回傳另一邊，邏輯統整後可以寫得更漂亮一點(像下面的寫法裡的連續兩個 if 會同時處理掉這兩個 case)。
有兩個子節點的情況會比較麻煩一點，我們有個例子好些。
當遞迴覺得複雜構造難以在腦袋裡一步一步想解法，可以用最簡單的 case 來想，像這題我們可以想一棵三個節點的 BST，這樣想像會比較簡單。

  2
 / \
1   3

像這樣，假設我們要刪除 2 這個節點，我們選擇以往右邊找右子樹中最小節點來替換來舉這個例子。
往右子樹找最小節點很簡單，就寫一個遞迴，不斷往左子樹找(BST特性)，找不到左子樹就回傳自己，這樣我們就有右子樹中最小的點了。
找到這個點之後，我們要做什麼？我們要讓本來指向的這個點來替換當前已經找到、最初要被刪掉的點。也就是說這棵點如果同時有左右子樹，那我們也要做一次假設把這個點移掉，會變成哪棵點作為根節點的判斷，正好是需要把這個節點先從右邊刪除(重複函式本身)。
刪除後，要替換現在這個節點，讓被替換的節點的左右，改由這個右邊被刪除的點來指向，最後回傳替換完成的節點，這個節點已經是新的根結點了。
這邊的步驟比較複雜，可能要用稍微大一點的樹會更好想，建議如果這邊看不清楚，自己手動畫一下至少 3 層的樹會比較知道發生什麼事。

再來是如果沒找現在這個節點不是目標節點，那就簡單了，就是直接往左右去找節點就好，享受 BST 帶來的規則。
最後回傳新的的根結點，程式完成。

public class Solution {
    public List<TreeNode> list = new List<TreeNode>();
    public TreeNode DeleteNode(TreeNode root, int key) {
        if(root == null){
            return root;
        }
        if(root.val == key){
            if(root.left == null){
                return root.right;
            }
            if(root.right == null){
                return root.left;
            }
            else{
                var minNode = FindMinNode(root.right);
                root.right = DeleteNode(root.right, minNode.val);
                minNode.left = root.left;
                minNode.right = root.right;
                root = minNode;
            }
        }

        if(root.val > key){
            root.left = DeleteNode(root.left, key);
        }
        if(root.val < key){
            root.right = DeleteNode(root.right, key);
        }
        return root;
    }

    public TreeNode FindMinNode(TreeNode node){
        if(node.left != null){
            return FindMinNode(node.left);
        }
        return node;
    }
}

這題的遞迴相較前面比較繞一點，要很清楚定義根要做的事情。注意回傳的東西是什麼，跟用盡可能簡化後的結構去定義出基本步驟，才能夠知道自己前幾步要做什麼。

至此，所有 BST 相關的 CRUD 操作都走過一遍，如果一開始有些想不通，可以先從嘗試遞迴函式本身意義理解起。
再把自己認為函式達不到的例子或比較有疑問的例子手繪，用紙筆跑一次程式碼，就會更明瞭知道遞迴的流程，最後嘗試自己從零開始重寫一次，能寫出來那就沒問題了。