數據結構：二叉搜索樹（BST）核心操作完整偽代碼解析

BST 基本性質

• 左子樹鍵值 ≤ 根節點鍵值 ≤ 右子樹鍵值。
• 中序遍歷可得遞增序列。
• 基本操作時間複雜度與樹高 h 成正比（平均 O(log n)，最壞 O(n)）。

核心操作偽代碼

1. 中序遍歷

[plain]
inorder-tree-walk(x)
if x != NIL
    inorder-tree-walk(left[x])
    print(key[x])
    inorder-tree-walk(right[x])

2. 查找

[plain]
tree-search(x, k)
if x == NIL or k == key[x] return x
if k < key[x] return tree-search(left[x], k)
else return tree-search(right[x], k)

// 迭代版
while x != NIL and k != key[x]
    if k < key[x] x = left[x]
    else x = right[x]
return x

3. 最小/最大值

[plain]
tree-minimum(x)
while left[x] != NIL x = left[x]
return x

tree-maximum(x)
while right[x] != NIL x = right[x]
return x

4. 後繼節點

[plain]
tree-successor(x)
if right[x] != NIL return tree-minimum(right[x])
y = parent[x]
while y != NIL and x == right[y]
    x = y
    y = parent[y]
return y

原理：若有右子樹，後繼為右子樹最小值；否則向上找第一個作為左孩子的祖先。

5. 插入

[plain]
tree-insert(T, z)
y = NIL
x = root[T]
while x != NIL
    y = x
    if key[z] < key[x] x = left[x]
    else x = right[x]
parent[z] = y
if y == NIL root[T] = z
else if key[z] < key[y] left[y] = z
else right[y] = z

6. 刪除（三種情況）

[plain]
tree-delete(T, z)
if left[z] == NIL or right[z] == NIL
    y = z
else
    y = tree-successor(z)  // y 最多只有一個孩子

if left[y] != NIL x = left[y]
else x = right[y]

if x != NIL parent[x] = parent[y]

if parent[y] == NIL root[T] = x
else if y == left[parent[y]] left[parent[y]] = x
else right[parent[y]] = x

if y != z key[z] = key[y]
return y

三種情況圖解：

1. 無孩子：直接刪除，父節點對應指針置 NIL。
2. 單孩子：孩子頂替被刪節點位置。
3. 雙孩子：找後繼 y（必無左孩子），用 y 的鍵值覆蓋 z，再按情況 1/2 刪除 y。

總結

BST 是動態集合的基礎結構，掌握上述六大操作偽代碼是實現平衡樹（AVL、紅黑樹）的前提。實際工程中建議直接使用 std::map/set 或成熟庫。