動機
二元搜尋樹（binary search tree, BST）的形狀記錄了比較結果。在鍵值為
x 的節點，只需一次比較，便可排除整棵不可能包含目標的子樹：較小的
鍵只能在左方，較大的鍵只能在右方。因此，搜尋、最小值、最大值、插入、
中序後繼及刪除並非六套無關技巧，而是同一個次序不變條件的推論。
這個觀點亦可避免把 BST 操作一律寫成 O(log n)。操作沿根至葉的路徑
前進，直接控制成本的是樹高 h。形狀均勻的樹可以有對數高度；插入次序
不理想時，樹也可退化成鏈。這裏說「平衡」只是在描述樹高為 O(log n)
的形狀，不代表任何維護演算法。本節只處理課程資料支持的核心 BST，不教授
AVL、紅黑樹、旋轉或其他平衡演算法。
定義
定義
二元搜尋樹不變條件
本節的 BST 是一棵鍵值可比較且互不相同的二元樹。對每個節點 v，
v.left 內的每一個鍵都嚴格小於 v.key，v.right 內的每一個鍵都
嚴格大於 v.key；左右子樹本身也必須滿足同一條件。
「每一個鍵」是重點。只檢查直接子節點並不足夠；孫節點即使與父節點的 大小關係正確，也可能越過祖先所定的界限。遞迴驗證時，可把容許區間傳入 子樹：左子樹新增上界，右子樹新增下界。
課程來源採用鍵值唯一的約定。若插入已存在的鍵，實作可以拒絕插入，或像 課堂 ADT 一樣替換該鍵所存的資料，但不可建立第二個同鍵節點。
定義
樹高約定
樹高 h 是由根向下至葉的最長路徑所含的節點數。空樹高度為 0，
單節點樹高度為 1；非空樹的高度是左右子樹高度最大值再加一。
搜尋、最小值與最大值
搜尋把目標鍵與當前節點比較；相等便成功，較小走左，較大走右。每輪開始
時維持以下不變條件：若目標仍存在，它必在當前子樹。抵達 NIL 時，所有
合法方向已用盡，故能證明目標不存在，而不只是「暫時找不到」。
SEARCH(root, key):
v = root
while v != NIL:
if key == v.key: return v
if key PRECEDES v.key: v = v.left
else: v = v.right
return NIL
最小值持續走左，直至沒有更小的左子樹；最大值則持續走右。兩者要求起點
非空，否則介面應回傳「不存在」，不可解參照 NIL。最小節點不一定是
葉：它仍可有右子節點；最大節點亦可有左子節點。
MINIMUM(v): MAXIMUM(v):
while v.left != NIL: while v.right != NIL:
v = v.left v = v.right
return v return v
插入
插入其實是一次失敗搜尋：記住最後一個非空節點，並按最後比較把新葉接到 左或右。以下版本拒絕重複鍵。
INSERT(root, key):
if root == NIL: return NEW_NODE(key)
parent = NIL
v = root
while v != NIL:
parent = v
if key == v.key: return root
if key PRECEDES v.key: v = v.left
else: v = v.right
if key PRECEDES parent.key: parent.left = NEW_NODE(key)
else: parent.right = NEW_NODE(key)
return root
舊節點的位置完全不變，新鍵只佔據第一個空位置。遞迴版本必須把回傳的 子樹根重新存入父節點；空樹插入會產生新根，忽略回傳值便會遺失更新。
中序後繼
定義
中序後繼
節點 x 的中序後繼，是中序走訪時緊接 x 被訪問的節點。在鍵值唯一的
BST 中，它也是嚴格大於 x.key 的最小鍵；全樹最大節點沒有後繼。
情況只有兩種：若右子樹非空，答案是右子樹最小節點；否則向上走，略過
所有從右分支抵達的祖先，首個由其左分支抵達的祖先便是答案。若不存在，
回傳 NIL。
SUCCESSOR(x):
if x.right != NIL: return MINIMUM(x.right)
p = x.parent
while p != NIL and x == p.right:
x = p
p = p.parent
return p
從右分支抵達的祖先早已在中序走訪中出現，故必須跳過；首個從左分支 抵達的祖先尚未被訪問。這個做法需要 tutorial 所指出的 parent 指標， 或由根搜尋時保存的完整路徑；只有左右子節點指標不能向上走。
刪除
刪除先搜尋目標，再按子節點數目處理：葉以 NIL 取代；只有一個子節點
時，以該子樹取代；有兩個子節點時，以右子樹最小值（後繼）取代，再刪除
後繼原來的位置。對稱地使用左子樹最大值（前驅）亦正確。
DELETE(t, key):
if t == NIL: return NIL
if key PRECEDES t.key:
t.left = DELETE(t.left, key)
else if t.key PRECEDES key:
t.right = DELETE(t.right, key)
else:
if t.left == NIL: return t.right
if t.right == NIL: return t.left
s = MINIMUM(t.right)
t.record = COPY(s.record)
t.right = DELETE(t.right, s.key)
return t
右子樹最小節點不可能有左子節點，否則該左節點會是同一子樹內更小的鍵； 所以移除後繼只會落入零或一個子節點的簡單情況。程式實作還須分開處理 記憶體擁有權：釋放正確節點、不可釋放後繼後再讀取它，亦要說明複製資料 是深複製還是只複製指標。
定理 / 命題
定理
搜尋路徑排除原理
在 BST 節點 v，若目標鍵小於 v.key，它不可能在 v.right；若目標鍵
較大，它不可能在 v.left。所以每次比較都可安全排除整棵子樹。
定理
核心更新保持 BST 不變條件
若輸入樹鍵值互異並符合 BST 不變條件，把新鍵插入第一個空搜尋位置會 保持不變條件；按零子節點、一子節點或後繼／前驅的兩子節點規則刪除， 亦會保持不變條件。
定理
依樹高計算的成本
若比較、指標讀寫及資料替換均為常數時間，搜尋、極值、插入、後繼及刪除
均為 O(h)。在所有含 n 個節點的可能 BST 形狀中，最壞情況為 O(n)。
證明思路
先證搜尋。若目標小於當前鍵，不變條件指出右子樹所有鍵都更大，因此右方 不可能相等；較大的情況對稱。反覆套用後，找到相等鍵自然正確，而在唯一 可行路徑抵達空樹則證明鍵不存在。
插入不改動任何舊子樹。先前每次比較都把新鍵限制在所有祖先傳下來的正確 區間；最後一次比較又把新葉接到父節點的正確一側，故同時符合父節點及 所有祖先的界限。
刪除零或一子節點時，只移走目標，存活鍵的相對次序不變。兩子節點時，
令 s 為右子樹最小值。原左子樹所有鍵小於被刪鍵，因而也小於 s；
刪除 s 的舊位置後，右子樹餘下所有鍵均嚴格大於新根鍵。前驅版本完全
對稱。注意「複製後繼」後還必須刪除原後繼，否則會破壞唯一性。
成本方面，每個程序只沿常數條祖先或後代路徑前進，每條最多含 h 個
節點。兩子節點刪除雖先找目標再向右子樹找最小值，兩段仍只是一條根至葉
路徑的分段，總成本是 O(h)，不是 O(h²)。BST 不變條件限制鍵的相對
位置，卻不限制兩邊高度；因此「是 BST」本身不保證對數高度。
例題詳解
例題
建立課堂例子的 BST 並追蹤搜尋
依次插入 11, 6, 8, 19, 1, 13, 17, 42, 16。根為 11；左子樹以
6 為根，左右為 1、8；右子樹以 19 為根，右為 42，左方是
以 13 為根、其右子節點為 17，而 17 的左子節點為 16。搜尋 16 的路徑為
11 -> 19 -> 13 -> 17 -> 16，方向依次右、左、右、左。最小值路徑是
11 -> 6 -> 1，最大值路徑是 11 -> 19 -> 42。成本由節點深度決定，
不是由鍵值的數值距離決定。
例題
追蹤三種後繼結果
同一棵樹中，13 有右子樹，其最小節點 16 是後繼。8 沒有右子樹；
向上先從 6 的右方抵達，須繼續，再從 11 的左方抵達，所以後繼為
11。42 沒有右子樹，也沒有合資格祖先，故後繼是 NIL。
例題
用兩種來源支持的策略刪除 19
19 有兩個子節點。使用前驅時，左子樹最大值是 17；以 17 取代
19，再移走原來的 17，其左子節點 16 接到 13 的右方。使用後繼
時，右子樹最小值是 42；以 42 取代 19，再移走原葉 42。兩個
結果形狀不同，但中序鍵列都由 13, 16, 17, 19, 42 變成
13, 16, 17, 42：只刪去目標，兩者都保持不變條件。
例題
相同鍵集合可以有完全不同的高度
插入 4, 2, 6, 1, 3, 5, 7，所得形狀均勻，n = 7 而 h = 3。改以
1, 2, 3, 4, 5, 6, 7 插入，每個新鍵都成為右子節點，故 h = 7。
演算法沒有改變，但前一類形狀的成本可為 O(log n)，退化鏈則為 O(n)。
這只是比較樹形，並沒有假設或教授平衡演算法。
常見錯誤
常見錯誤
只檢查直接子節點
左子節點較小、右子節點較大，不足以驗證整棵 BST；每個後代都要符合所有 祖先界限。
常見錯誤
假設後繼永遠在右子樹
只有右子樹非空時才取其最小值；否則答案可能是祖先，而最大節點沒有後繼。
常見錯誤
複製後繼後忘記刪除舊位置
兩子節點刪除不是複製資料便完成。若不移走原後繼或前驅，同一鍵會出現兩次。
常見錯誤
沒有條件便宣稱 O(log n)
無條件結論是 O(h)；只有樹高為對數級時才可改寫為 O(log n)，退化樹有
h = n。
其他常見實作問題包括：遞迴後沒有接回新的子樹根、在空樹求極值、沒有定義 重複鍵政策，以及刪除時錯誤釋放指標。
總結
- BST 不變條件約束整棵子樹，而不只約束相鄰節點。
- 搜尋每次排除一棵不可能的子樹；極值沿最左或最右路徑取得。
- 插入在失敗搜尋的第一個空位加入新葉。
- 後繼是右子樹最小值，或首個從左分支抵達的祖先。
- 刪除分零、一、兩個子節點；兩子節點情況取後繼或前驅並刪除其舊位置。
- 每次更新都要證明祖先傳下來的鍵值界限仍然成立。
- 核心操作為
O(h)：形狀均勻時可為對數級，退化時為線性；本節不假設 平衡演算法。
練習
思考檢查
根為 20，左右子節點為 10、30，而 10 的右子節點是 25。為何這不是 BST？
指出巢狀節點違反了哪一個祖先界限。
思考檢查
節點 15 的右子樹根為 20，且 20 的左子節點為 18。15 的後繼是甚麼？
先判斷結構情況，再比較候選鍵。
思考檢查
在課堂例子的 BST 中追蹤搜尋 14 失敗的路徑，並指出插入位置。
由根開始記錄每次比較，直至 NIL。
思考檢查
為何兩子節點刪除所取的右子樹最小節點不可能有左子節點？
直接使用「最小」的定義論證。
思考檢查
把 n 個互異鍵按嚴格遞增次序插入；求 h 及搜尋最大值的成本。
先描述所得樹形。
答案與解答
解答 · 解答 1
25 位於 20 的左子樹，所以祖先界限要求它小於 20，但事實並非如此。
它大於直接父節點 10 並不能修補對根所造成的違反。
解答 · 解答 2
15 有右子樹，故取該子樹最小值。由 20 向左到 18，答案是 18，
不是直接右子節點 20。
解答 · 解答 3
比較次序為：14 大於 11、小於 19、大於 13、小於 17、再小於
16，然後抵達 16 的空左子樹。完整路徑是
11 -> 19 -> 13 -> 17 -> 16 -> NIL，所以 14 應接成 16 的左子節點。
解答 · 解答 4
若右子樹最小節點 s 有左子節點，該左節點的鍵便比 s.key 更小，又仍在
同一右子樹內，與 s 為最小值矛盾。
解答 · 解答 5
遞增插入令每個新節點成為前一節點的右子節點，形成長鏈，故 h = n。
搜尋最大值要訪問全部 n 個節點，成本是 Theta(n)，符合一般 O(h)
上界。