在二叉搜尋樹中刪除一個鍵,所需保持的不僅是排序後的輸出:所有餘下的子樹都必須仍然可以到達,而以指標實作的版本亦必須遵守其節點身分及記憶體擁有權的約定。
1. 不變量與兩個子節點的障礙
假設各鍵互不相同,並考慮一棵普通的二叉搜尋樹(BST):某節點左子樹中的每個鍵都比該節點的鍵小,而右子樹中的每個鍵都比它大。兩棵子樹亦各自滿足同一規則。搜尋時每作一次比較便沿其中一個子節點前進;其成本由樹的高度控制,而非自動受節點數目的對數所限。
葉節點可以直接移除。若某節點恰有一個子節點,其父節點可以用該子節點取代它;當該節點是根節點時,樹的根就必須改變。若節點有兩個子節點,則任何一個子節點都不能單獨直接取代該節點而不顧及另一棵子樹。一個有用的替代鍵是中序後繼。
定義 17.1.1
(有兩個子節點的節點的中序後繼)
設 是各鍵互不相同的 BST 中有左、右子節點的節點。 的中序後繼是存放 右子樹最小鍵的節點。
引理 17.1.2
(後繼節點的位置)
設 是兩個子節點的節點 的中序後繼。則 沒有左子節點; 左子樹中的每個鍵都小於 的鍵; 右子樹中其餘的每個鍵都大於 的鍵。
證明
(右子樹最小值的最小性)
若 有左子節點,該子節點便是同一右子樹中一個更小的鍵,與最小性矛盾,所以 沒有左子節點。左子樹的每個鍵都小於 的鍵,而 的鍵又小於右子樹的每個鍵,尤其小於 的鍵。右子樹其餘的鍵不小於最小值,又因各鍵互不相同而不等於它,所以較大。
概念視角結構
刪除即與排序中的下一個鍵交換
通過中序序列來讀這棵樹,它按遞增次序列出所有鍵。後繼就是該序列中 之後的下一個鍵。由引理,它沒有左子節點,所以把 的鍵與它交換,雙子節點的刪除便化為較容易的情形:移除至多有一個子節點的節點。
然而,後繼可能有右子節點,而該右子節點必須在其原來的位置取代它。若追蹤過程中假設最小節點必定是葉節點,便很容易遺漏這種情況。
反例模式
後繼節點不一定是葉節點
斷言:要刪除有兩個子節點的節點,只需把後繼的鍵複製進去,再把後繼的父節點的左指標設為 null 以拆下後繼。取根 ,左子節點 ,右子節點 ,其中 有子節點 和 ,而 有右子節點 。 的後繼是 ,它不是葉節點。把 複製到根並把 的左指標設為 null 後,節點 便無法到達,儘管 從未被刪除,中序序列也失去了 。修正辦法是用後繼的右子節點(這裏是 )取代後繼,下面的算法正是這樣做。
2. 回傳新的子樹根
以下是一個遞歸設計。它使用左/右子節點指標,不使用父節點指標,並在每次刪除後回傳可能已改變的根。所儲存的 record 包含鍵及負載數據,不包含節點的子節點連結。在偽代碼中,t.key 是 t.record.key 的簡寫。假設複製一個記錄會得到一個獨立的值,即使來源節點被釋放後仍然有效;在使用具擁有權指標的實際程式中,則需要明確的深層複製或擁有權轉移策略。
pop_min(t): // precondition: t != null
if t.left == null:
record = copy(t.record)
replacement = t.right
free(t)
return (record, replacement)
(record, t.left) = pop_min(t.left)
return (record, t)
delete(t, key):
if t == null: return null
if key < t.key:
t.left = delete(t.left, key)
else if key > t.key:
t.right = delete(t.right, key)
else:
if t.left == null:
replacement = t.right; free(t); return replacement
if t.right == null:
replacement = t.left; free(t); return replacement
(record, t.right) = pop_min(t.right)
t.record = record
return t
pop_min 同時回傳一個複製的記錄及餘下部分的根。在遞歸返回時,每個調用者都把其左子節點重新連接到該餘下部分。刪除的調用者必須把回傳的根賦值回去,包括在最頂層:root = delete(root, key)。刪除不存在的鍵時會到達 null,並保持現有連結不變。若某實作保留父節點指標或可從外部觀察的節點參照,則需要額外的更新,或採用不同的身分策略。
常見錯誤
(忽略回傳的根)
設一棵樹的根 只有右子節點 。調用 delete(root, 5) 會釋放根節點並回傳 。若調用者只寫 delete(root, 5) 而保留舊的 root 變量,它現在持有的是懸空指標。結果必須賦值回去:root = delete(root, 5)。
常見錯誤
(取右子樹的最大值而不是最小值)
在下面第一個刪除例子的樹中,目標 的右子樹含鍵 。若程式碼把最大值 複製到根並移除該葉節點,根變成 ,但 仍在其右子樹中,比根小。次序因而被違反:搜尋 時與 比較後向左進入 的子樹,結果失敗。只有右子樹的最小值才小於該子樹其餘所有的鍵。
3. 刪除例子
例題 17.1.3
(後繼節點不是葉節點)
設根為 40,其左子節點為 20(子節點為 10,30),右子節點為 70(子節點為 50,80)。節點 50 有右子節點 60。使用上述的值複製規則刪除鍵 40。
右子樹中的最小值是 50,經由 70 -> 50 到達;它沒有左子節點,但有右子節點 60。pop_min 把記錄 50 及子樹 60 回傳給其調用者,於是 70.left 變為 60。把該記錄複製到原來的根節點。最終的根的鍵為 50,左子樹以 20 為根,其子節點為 10 和 30;右子樹以 70 為根,其子節點為 60 和 80。其中序序列為 10,20,30,50,60,70,80:它恰好包含除 40 以外的所有原有鍵。
原本存放 40 的節點得以保留,但存有不同的記錄;原本存放 50 的節點則被釋放。若某個用戶端把節點位址視為穩定的身分,便不能默然假設複製鍵就等同於刪除所要求的那個節點。另一種基於移植的設計可以改為移動後繼節點本身,但必須修復其舊父節點及新父節點的連結,並說明哪些參照仍然有效。
例題 17.1.4
(後繼是右子節點,以及不存在的鍵)
取根 40,左子節點 20(子節點為 10,30),右子節點 70,其中 70 只有右子節點 80。刪除鍵 40。右子樹的根沒有左子節點,所以 pop_min(70) 走第一個分支:複製記錄 70,回傳 replacement 80,並釋放節點 70。調用者令 40.right = 80,並把記錄 70 複製到根,得到根 70,左子樹為 20(子節點 10,30),右子節點為 80。中序序列為 10,20,30,70,80,即原有的鍵去掉 40。從原來的樹刪除鍵 99 時,依次與 40、70、80 比較,到達 null,各節點原封不動地回傳。
例題 17.1.5
(刪除只有一個子節點的根)
設樹的根 5 只有右子節點 8。delete(root, 5) 在根處找到相等,看到 t.left == null,保存 replacement = t.right,釋放根並回傳 8。新的根是 8,其下的子樹不變。若根只有左子節點,則第二個分支會回傳該子節點。兩種情況下樹的根變量都會改變,這就是 delete 的結果要賦值回去的原因。
4. 正確性與成本
定理 17.1.6
(刪除的正確性)
設 是各鍵互不相同的 BST 的根。當 null,pop_min(t) 回傳最小鍵的記錄,以及恰好存放其他鍵的 BST 的根。而 delete(t, key) 回傳一棵 BST 的根,該 BST 恰好存放 中除 key 以外的鍵;若 key 不存在,鍵集合不變。
證明
(對樹高作歸納)
對 pop_min:若 t.left 為 null,最小值就是 t.key,因為右邊的鍵都較大,而餘下部分 t.right 是存放其他鍵的 BST。否則 的最小值就是左子樹的最小值,因為所有左邊的鍵都小於 t.key;由歸納,pop_min(t.left) 回傳它以及存放其餘左鍵的 BST,把該 BST 重新連為左子節點,其所有鍵仍小於 t.key。
對 delete,按高度作歸納。null 的情況回傳 null,正確,因為鍵不存在。若鍵小於 t.key,它只可能在左子樹中;由歸納,左子樹成為存放相同鍵(去掉它)的 BST,其鍵仍全部小於 t.key,所以 是 BST。鍵較大的情況對稱。若鍵等於 t.key 且有一個子節點為 null,另一棵子樹本身就是存放其餘鍵的 BST。有兩個子節點時,設 為後繼。由引理,左邊的鍵都小於 的鍵,而 pop_min 留下的右邊餘下部分存放其餘右鍵,全都大於它。把 的記錄複製進 ,所得 BST 的鍵就是 的鍵去掉舊鍵。每種情況下,回傳的子樹只是少了一個鍵,其鍵仍在舊子樹的界限之內,所以祖先的界限仍然成立。
證明透視
互不相同與最小性用在哪裏
後繼的最小性用了兩次:令複製的鍵大於左子樹的一切,並令右邊餘下部分的每個鍵都大於複製的鍵。互不相同把「不小於最小值」變成 BST 規則所要求的「嚴格較大」。回傳根的約定使單一子節點的情況和根的情況可以共用同一個證明:每次遞歸調用都回傳鍵集合已知的子樹,所以父節點只須把它重新連接。歸納得以完成,因為每次調用都向下一層。
設 h 為最長由根到葉路徑上的節點數目。搜尋目標,然後向下找到並移除其後繼,總共訪問 O(h) 個節點;經遞歸返回則使用 O(h) 個堆疊框架。在一條鏈上,h 可以等於 n,因此最壞情況的時間為 O(n)。平衡的高度界限需要額外的平衡保證;普通的 BST 並不提供這種保證。以上成本假設鍵的比較、記錄的複製及指標的更新均為常數時間,並假設輸入是一棵有效且無環的樹。
5. 檢查
快速檢查
(在第一個刪除例子的樹中, 仍在,刪除 。所得的樹及其中序序列是甚麼?)
找出 的右子樹的最小值。
解答 · 答案
的右子樹只有節點 ,所以後繼是 ,pop_min 回傳記錄 及空的餘下部分。原來存放 的節點現在存放 ,左子節點為 ,沒有右子節點。中序序列為 10,30,40,50,60,70,80。
快速檢查
(在同一棵樹中刪除 。哪個節點成為後繼,右邊部分的形狀是怎樣的?)
的右子樹是節點 。
解答 · 答案
後繼是 ,是葉節點。原來存放 的節點現在存放 ,保留左子節點 (其右子節點為 ),失去右子節點。中序序列為 10,20,30,40,50,60,80。
快速檢查
(為何調用者必須寫 root = delete(root, key),而不是只調用 delete(root, key)?)
想一想刪除唯一的節點,或只有一個子節點的根。
解答 · 答案
根節點本身可能被釋放,並由其子節點或 null 取代。只有回傳值才標示新的根;舊變量會懸空。
快速檢查
(依 的次序把它們插入空的普通 BST。 是多少?delete(root, 4) 訪問多少個節點?)
先畫出這棵樹,再計算。
解答 · 答案
這棵樹是由右子節點組成的鏈 ,所以 個節點。調用依次與 比較,然後以回傳其 null 右子節點的方式移除葉節點 ,所以訪問 個節點,與 成線性。