二元搜尋樹的插入與刪除

刪除比插入難在哪裡

二元搜尋樹（binary search tree，BST）的規則只有一條：每個節點的左子樹全部比它小、右子樹全部比它大。 搜尋和插入都是從根往下走，每比一次往下一層（演算法軌第 14 課有完整的介紹，這一課不要求先看過）。

這一課看的是實作細節。插入只是在最底下多掛一片葉子，不會動到別的節點；刪除卻可能拿掉中間的節點， 它底下的子樹要接到別的地方，而且接完之後整棵樹還是要滿足左小右大。寫刪除時要回答三個問題：

1. 要刪的節點有幾個子節點？
2. 誰來頂替它的位置？要改的是哪一條連結（父節點的 left 還是 right，或是整棵樹的 root）？
3. 拿掉的節點記憶體怎麼處理？（C++ 要自己 delete；Python 和 Java 沒有變數指到的物件會被自動回收）

範例的節點三種語言都用同樣的欄位：val、left、right。C++ 用 struct Node 加指標，空的子節點是 nullptr；Java 是 null；Python 是 None。

刪除的三種情況

先找到要刪的節點 t，再依它有幾個子節點處理：

情況一可以看成情況二的特例：「沒有左子節點，就讓右子節點頂替」，右子節點剛好是空的時，就是葉節點的情況。所以程式只要檢查兩次：

if t.left is None:
    return t.right       # 情況一、二
if t.right is None:
    return t.left        # 情況二

這裡用的是回傳新的子樹根的遞迴寫法：delete(node, key) 回傳「刪除之後，這棵子樹的根」，呼叫的人寫 node.left = delete(node.left, key) 把它接回去。 這樣就不必另外記住父節點，也不必特別處理「刪的是整棵樹的根」：最外層寫 root = delete(root, key)，根換人時 root 自然跟著更新。

先看最簡單的應用：拿掉最小值。最小值一定在最左邊，它沒有左子節點，所以一定是情況一或二。

兩個子節點：讓後繼者頂替

要刪的 t 有兩個子節點時，不能直接讓其中一個子節點頂替：左右兩棵子樹都要有地方接，可是頂替的節點只有一個位置留給另一棵子樹。

解法是找一個「站在 t 的位置也不會違反左小右大」的節點。它必須比左子樹全部大、比右子樹其他值都小，有兩個人選：

• 後繼者（successor）：右子樹裡最小的節點，也就是中序走訪時緊接在 t 後面的那一個
• 前驅（predecessor）：左子樹裡最大的節點，也就是中序走訪時緊接在 t 前面的那一個

用後繼者時的步驟：

1. 從 t.right 出發一路往左走到底，得到後繼者 s（它沒有左子節點）
2. 用 remove_min(t.right) 把 s 從右子樹解開，得到的新右子樹接到 s.right
3. s.left = t.left：把 t 的左子樹接到 s 下面
4. 回傳 s，上一層把它接在原本 t 的位置；C++ 這時 delete t

這種「把後繼者節點整個搬上來」的寫法常稱為 Hibbard 刪除法，出自 Hibbard 1962 年的論文。另一種常見寫法是複製值：把後繼者的值抄到 t，再到右子樹刪掉原本的後繼者（演算法軌第 14 課用的就是這種）。兩種結果的形狀一樣，差別在：

C++ 的 std::map 刪除元素時，指向其他元素的迭代器仍然有效，靠的就是只動連結、不搬其他元素的值。

為什麼刪完還是二元搜尋樹

檢查刪除寫得對不對，最直接的方法是看中序走訪：二元搜尋樹的中序走訪一定由小到大。刪掉 t 之後，中序序列應該剛好少了 t 這一個值，其他順序都不變。

• 情況一、二：t 的子樹整棵往上接，子樹內部的順序沒變，它在中序序列裡的位置也剛好就是 t 原本所在的那一段
• 情況三：後繼者是中序序列裡緊接在 t 後面的那一個。把它搬到 t 的位置，等於序列裡「t、s」變成「s」，其他元素一個都沒動

所以刪除之後，左子樹的值仍然都比新的根小（它們原本就比 t 小，而 s 比 t 大），右子樹剩下的值仍然都比 s 大（s 是右子樹裡最小的）。

用前驅也一樣成立，只是左右對調。有分析指出，大量反覆插入、刪除時一直只用後繼者，樹會慢慢偏向一邊；有些實作會輪流使用前驅與後繼者。

下面的小工具可以自己動手刪，它用的是「複製值」的寫法，每一步都標出屬於哪一種情況。

插入的順序決定樹高

搜尋、插入、刪除都是從根往下走一條路，所以花的時間是 O(h)，h 是樹高（從根到最深的葉經過幾個節點）。 同樣 n 個鍵，樹高最低約 log₂n，最高是 n，完全取決於插入的順序：

• 依序插入 1、2、3、4、5：每個新鍵都比樹裡所有的鍵大，只能一直往右掛，樹變成一條線，其實就是一條鏈結串列
• 先插中間的 3，再插 2、4、1、5：樹只有 3 層

下面用遞迴算樹高：空樹高度是 0，其他節點的高度是「左右子樹比較高的那一個，再加 1」。這個「先算完兩個子樹、再算自己」的順序就是後序走訪，下一課的 AVL 樹每個節點都要記住這個值。

平衡樹：每次操作後把樹整理矮

資料常常是排好序進來的（學號、時間戳記、流水號），普通的二元搜尋樹在這種情況下會退化成串列。 平衡二元搜尋樹在每次插入、刪除之後檢查樹的形狀，必要時用旋轉（rotation）調整，保證樹高一直是 O(log n)：

• 第 11 課 AVL 樹：每個節點記住高度，左右子樹高度最多差 1
• 第 12 課 紅黑樹：每個節點記一個顏色，用顏色規則間接限制樹高；它和 2-3-4 樹（一個節點可以放 1～3 個鍵）是同一件事的兩種畫法
• 第 13 課 B 樹：一個節點放很多個鍵，樹變得又矮又寬，適合存在磁碟上

它們的搜尋和這一課完全一樣，差別只在插入、刪除之後多做的調整。

重點整理

• 插入一定是在最底下多掛一片葉子；迴圈寫法要用 parent 記住上一層，因為 cur 走到空位時已經是空的
• 刪除分三種：葉節點直接拿掉；一個子節點讓子節點頂替；兩個子節點用後繼者（右子樹最小）或前驅（左子樹最大）頂替
• 「回傳新的子樹根」的遞迴寫法（node.left = delete(node.left, key)）不必記父節點，也自動處理刪除根的情況
• 情況三可以改連結（把後繼者節點搬上來，Hibbard 刪除法）或複製值；前者不搬動其他節點的資料
• C++ 拿掉節點後要 delete，而且要先把需要的指標存起來再 delete，避免懸置指標
• 刪除後中序序列只少了被刪的那個值，所以仍然是二元搜尋樹
• 所有操作都是 O(h)；依序插入會退化成一條線，h = n

下一課：AVL 樹。每個節點多記一個高度，插入後發現左右差太多，就用旋轉把樹轉回平衡。