二元搜尋樹 — BST 操作、AVL 與紅黑樹自平衡機制 | 資料結構與演算法
2026/06/23
二元搜尋樹（Binary Search Tree，BST） 是在二元樹的基礎上加了「左子樹所有值 < 根 < 右子樹所有值」這一條有序約束，讓搜尋效率從 O(n) 提升至 O(log n)。理解 BST 的搜尋、插入、刪除三大操作，以及 AVL 樹與紅黑樹如何自動維持平衡，是資料結構與演算法的重要里程碑。
前言
想像你在查一本字典——你不會從第一頁翻到最後，而是先翻到中間，根據字母判斷要查的字在左邊還是右邊，然後再對半查找。這個「對折再對折」的直覺，就是 BST 的核心思想。
BST 讓每次比較都能排除一半的可能，在平衡狀態下，搜尋一個 n 個元素的 BST 只需要 O(log n) 步。但如果插入順序不當，BST 可能退化成一條鏈結串列，效能驟降至 O(n)——這也是為什麼我們需要 AVL 樹和紅黑樹。
本文學習要點：
- BST 性質與中序有序性
- 搜尋、插入、刪除三大操作（含刪除的三種情況）
- TypeScript 完整 BST 實作（驗證 BST、第 K 小、LCA）
- AVL 樹四種旋轉：LL、RR、LR、RL
- 紅黑樹五條性質與核心策略
- C++ STL
std::set、std::map使用與 AVL 實作 - 複雜度分析與 Splay Tree、Treap 延伸
- 五道 LeetCode 練習題解析
核心概念
BST 性質（BST Property）
BST 的本質是一個遞迴定義的有序約束：
對任意節點 N：
- N.left 所有節點的值 < N.val
- N.right 所有節點的值 > N.val
- 左右子樹也各自是 BST（遞迴定義）
- 中序遍歷（左→根→右）= 升序排列
以一棵具體的 BST 為例，搜尋值 6 的路徑：
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
搜尋 6：
訪問 8 → 6 < 8，往左
訪問 3 → 6 > 3，往右
訪問 6 → 6 == 6，找到！
搜尋路徑：8 → 3 → 6（只需 3 步，而非暴力搜尋的 9 步）
BST 退化問題
按升序插入 1, 2, 3, 4, 5，BST 會退化成右傾鏈結串列：
理想 BST（balanced）: 退化 BST（degenerate）:
3 1
/ \ \
2 4 2
/ \ \
1 5 3
\
樹高 = 2 4
搜尋 = O(log n) \
5
樹高 = n-1
搜尋 = O(n)
這就是為什麼需要 AVL 樹和紅黑樹——它們在每次插入、刪除後自動重新平衡，保證樹高始終在 O(log n)。
刪除操作的三種情況
刪除是 BST 中最複雜的操作，需要分三種情況處理：
情況 1：目標是葉節點 → 直接刪除（返回 null）
情況 2：目標只有一個子節點 → 用子節點替代
刪除 3： 結果：
5 5
/ \ / \
3 7 → 4 7
\
4
情況 3：目標有兩個子節點 → 找右子樹最小值（中序後繼）替代
刪除 5： 找到後繼 6，複製值後刪除 6：
5 6
/ \ / \
3 8 → 3 8
/ \ / \
6 9 7 9
\
7
右子樹最小值（中序後繼）保證大於左子樹所有值、小於右子樹其他所有值，完美維持 BST 性質。
JavaScript / TypeScript 實作
基礎 BST 類別（搜尋、插入、刪除、中序）
class BSTNode {
val: number;
left: BSTNode | null = null;
right: BSTNode | null = null;
constructor(val: number) { this.val = val; }
}
class BST {
root: BSTNode | null = null;
// ─── 插入（遞迴）：O(h) ────────────────────────────────────────────────────
insert(val: number): void {
this.root = this._insert(this.root, val);
}
private _insert(node: BSTNode | null, val: number): BSTNode {
if (!node) return new BSTNode(val);
if (val < node.val) node.left = this._insert(node.left, val);
else if (val > node.val) node.right = this._insert(node.right, val);
// val == node.val：BST 通常不儲存重複值，忽略
return node;
}
// ─── 搜尋（迭代）：O(h) ────────────────────────────────────────────────────
search(val: number): boolean {
let curr = this.root;
while (curr) {
if (val === curr.val) return true;
curr = val < curr.val ? curr.left : curr.right;
}
return false;
}
// ─── 刪除：O(h) ────────────────────────────────────────────────────────────
// 三種情況：
// 1. 葉節點 → 直接刪除
// 2. 單子節點 → 子節點替代
// 3. 雙子節點 → 右子樹最小值（中序後繼）替代，再刪後繼
delete(val: number): void {
this.root = this._delete(this.root, val);
}
private _delete(node: BSTNode | null, val: number): BSTNode | null {
if (!node) return null;
if (val < node.val) {
node.left = this._delete(node.left, val);
} else if (val > node.val) {
node.right = this._delete(node.right, val);
} else {
// 找到目標節點
if (!node.left) return node.right; // 情況 1 & 2
if (!node.right) return node.left; // 情況 2
// 情況 3：找右子樹最小值（一路向左）
const successor = this._findMin(node.right);
node.val = successor.val; // 值替換
node.right = this._delete(node.right, successor.val); // 刪除後繼
}
return node;
}
private _findMin(node: BSTNode): BSTNode {
while (node.left) node = node.left;
return node;
}
// ─── 中序遍歷（得到升序序列）───────────────────────────────────────────────
inorder(): number[] {
const result: number[] = [];
const traverse = (node: BSTNode | null): void => {
if (!node) return;
traverse(node.left);
result.push(node.val);
traverse(node.right);
};
traverse(this.root);
return result;
}
}
// 測試
const bst = new BST();
[5, 3, 7, 1, 4, 6, 8].forEach(v => bst.insert(v));
console.log(bst.inorder()); // [1, 3, 4, 5, 6, 7, 8]（升序）
bst.delete(5);
console.log(bst.inorder()); // [1, 3, 4, 6, 7, 8]
驗證 BST（LeetCode 98）
這是 BST 題目中最常見的陷阱——不能只比較父子節點，必須傳遞全局上下界：
// 方法一：上下界傳遞（推薦）
// 根節點值域為 (-∞, +∞)
// 往左走：上界縮小為 node.val（所有左子樹節點必須 < node.val）
// 往右走：下界縮小為 node.val（所有右子樹節點必須 > node.val）
function isValidBST(root: TreeNode | null): boolean {
function validate(
node: TreeNode | null,
min: number,
max: number
): boolean {
if (!node) return true;
// 必須嚴格大於 min、嚴格小於 max（BST 不含重複值）
if (node.val <= min || node.val >= max) return false;
return validate(node.left, min, node.val) &&
validate(node.right, node.val, max);
}
return validate(root, -Infinity, Infinity);
}
// 陷阱：不能只看 node.left.val < node.val < node.right.val
// 反例（錯誤通過但不是 BST）：
// 5
// / \
// 1 4
// / \
// 3 6
// 4.left=3 < 4 看起來合法，但 3 < 5（根），違反右子樹所有值 > 5 的約束
// 方法二：中序遍歷，確認序列嚴格遞增
function isValidBSTInorder(root: TreeNode | null): boolean {
let prev = -Infinity;
function inorder(node: TreeNode | null): boolean {
if (!node) return true;
if (!inorder(node.left)) return false; // 左子樹不合法
if (node.val <= prev) return false; // 當前值不嚴格大於前值
prev = node.val;
return inorder(node.right);
}
return inorder(root);
}
// 時間 O(n)，空間 O(h)
BST 第 K 小元素（LeetCode 230）
BST 中序遍歷 = 升序序列，第 k 個中序元素即第 k 小：
// 迭代中序遍歷：找到第 k 個立即停止，不需要遍歷全部
// 時間 O(h + k)，空間 O(h)
function kthSmallest(root: TreeNode | null, k: number): number {
const stack: TreeNode[] = [];
let curr: TreeNode | null = root;
let count = 0;
while (curr !== null || stack.length > 0) {
// 一路向左（往最小值方向）
while (curr !== null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop()!;
count++;
if (count === k) return curr.val; // 找到第 k 小，立即返回
curr = curr.right;
}
return -1; // 不應到達此處（k 合法時）
}
// 進階：若頻繁調用且有大量插入刪除，可在每個節點額外儲存左子樹節點數
// （leftCount），將查詢降至 O(h) 而不需遍歷
BST 最低公共祖先（LeetCode 235）
BST 的 LCA（Lowest Common Ancestor）可以利用 BST 性質直接定位，不需要像普通二元樹那樣完整 DFS：
// 思路：若 p 和 q 都小於 root，LCA 在左子樹
// 若 p 和 q 都大於 root，LCA 在右子樹
// 否則 root 本身就是 LCA（p 和 q 分屬兩側，或其中一個就是 root）
// 時間 O(h)，空間 O(1)（迭代版本）
function lowestCommonAncestor(
root: TreeNode,
p: TreeNode,
q: TreeNode
): TreeNode {
let curr: TreeNode = root;
while (true) {
if (p.val < curr.val && q.val < curr.val) {
curr = curr.left!; // p, q 都在左子樹
} else if (p.val > curr.val && q.val > curr.val) {
curr = curr.right!; // p, q 都在右子樹
} else {
return curr; // 分屬兩側，curr 即為 LCA
}
}
}
刪除 BST 節點（LeetCode 450）
// 三種情況分類：葉節點 / 單子節點 / 雙子節點
// 時間 O(h)，空間 O(h)（遞迴棧）
function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
if (!root) return null;
if (key < root.val) {
// key 在左子樹
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
// key 在右子樹
root.right = deleteNode(root.right, key);
} else {
// 找到目標節點
if (!root.left) return root.right; // 情況 1 & 2
if (!root.right) return root.left; // 情況 2
// 情況 3：找右子樹最小值（一路向左）
let successor = root.right;
while (successor.left) successor = successor.left;
// 將後繼值複製過來，再從右子樹刪除後繼
root.val = successor.val;
root.right = deleteNode(root.right, successor.val);
}
return root;
}
自平衡 BST
AVL 樹
AVL 樹（Adelson-Velsky and Landis Tree）要求每個節點的平衡因子（Balance Factor）= 左高 - 右高 ∈ {-1, 0, 1}，違反時透過旋轉修正。
四種失衡類型與對應旋轉：
─── LL 型（左左失衡）：右旋（Right Rotation）───────────────────────────
失衡： 修正後：
z [BF=+2] y
/ / \
y [BF=+1] x z
/
x
操作：z.left = y.right; y.right = z; 更新高度
─── RR 型（右右失衡）：左旋（Left Rotation）───────────────────────────
失衡： 修正後：
z [BF=-2] y
\ / \
y [BF=-1] z x
\
x
操作：z.right = y.left; y.left = z; 更新高度
─── LR 型（左右失衡）：先左旋再右旋──────────────────────────────────────
失衡： 中間步： 修正後：
z [BF=+2] z x
/ / / \
y [BF=-1] x y z
\ /
x y
操作：先對 y 做左旋（RR），再對 z 做右旋（LL）
─── RL 型（右左失衡）：先右旋再左旋──────────────────────────────────────
失衡： 中間步： 修正後：
z [BF=-2] z x
\ \ / \
y [BF=+1] x z y
/ \
x y
操作：先對 y 做右旋（LL），再對 z 做左旋（RR）
AVL 樹 TypeScript 完整實作：
class AVLNode {
val: number;
left: AVLNode | null = null;
right: AVLNode | null = null;
height: number = 1; // 新節點高度為 1
constructor(val: number) { this.val = val; }
}
class AVLTree {
private root: AVLNode | null = null;
// ─── 輔助：高度與平衡因子 ──────────────────────────────────────────────────
private height(node: AVLNode | null): number {
return node?.height ?? 0;
}
private updateHeight(node: AVLNode): void {
node.height = 1 + Math.max(this.height(node.left), this.height(node.right));
}
private balanceFactor(node: AVLNode): number {
return this.height(node.left) - this.height(node.right);
}
// ─── 旋轉操作 ──────────────────────────────────────────────────────────────
// 右旋（Right Rotation）：處理 LL 型失衡
private rotateRight(z: AVLNode): AVLNode {
const y = z.left!;
const T3 = y.right;
y.right = z;
z.left = T3;
this.updateHeight(z); // z 先更新（z 現在是 y 的子節點）
this.updateHeight(y);
return y; // y 成為新的子樹根
}
// 左旋（Left Rotation）：處理 RR 型失衡
private rotateLeft(z: AVLNode): AVLNode {
const y = z.right!;
const T2 = y.left;
y.left = z;
z.right = T2;
this.updateHeight(z);
this.updateHeight(y);
return y;
}
// ─── 平衡修正（插入/刪除後自底向上調用）─────────────────────────────────────
private balance(node: AVLNode): AVLNode {
this.updateHeight(node);
const bf = this.balanceFactor(node);
// LL 型
if (bf > 1 && this.balanceFactor(node.left!) >= 0)
return this.rotateRight(node);
// LR 型：先左旋 node.left，再右旋 node
if (bf > 1 && this.balanceFactor(node.left!) < 0) {
node.left = this.rotateLeft(node.left!);
return this.rotateRight(node);
}
// RR 型
if (bf < -1 && this.balanceFactor(node.right!) <= 0)
return this.rotateLeft(node);
// RL 型：先右旋 node.right，再左旋 node
if (bf < -1 && this.balanceFactor(node.right!) > 0) {
node.right = this.rotateRight(node.right!);
return this.rotateLeft(node);
}
return node; // 已平衡，無需旋轉
}
// ─── 插入 ──────────────────────────────────────────────────────────────────
insert(val: number): void {
this.root = this._insert(this.root, val);
}
private _insert(node: AVLNode | null, val: number): AVLNode {
if (!node) return new AVLNode(val);
if (val < node.val) node.left = this._insert(node.left, val);
else if (val > node.val) node.right = this._insert(node.right, val);
else return node; // 不儲存重複值
return this.balance(node); // 插入後自底向上修正平衡
}
// ─── 刪除 ──────────────────────────────────────────────────────────────────
delete(val: number): void {
this.root = this._delete(this.root, val);
}
private _delete(node: AVLNode | null, val: number): AVLNode | null {
if (!node) return null;
if (val < node.val) {
node.left = this._delete(node.left, val);
} else if (val > node.val) {
node.right = this._delete(node.right, val);
} else {
if (!node.left) return node.right;
if (!node.right) return node.left;
// 找右子樹最小值替換
let minRight = node.right;
while (minRight.left) minRight = minRight.left;
node.val = minRight.val;
node.right = this._delete(node.right, minRight.val);
}
return this.balance(node); // 刪除後修正平衡
}
inorder(): number[] {
const result: number[] = [];
const traverse = (n: AVLNode | null): void => {
if (!n) return;
traverse(n.left);
result.push(n.val);
traverse(n.right);
};
traverse(this.root);
return result;
}
}
// 測試：按升序插入（普通 BST 會退化，AVL 不會）
const avl = new AVLTree();
[1, 2, 3, 4, 5].forEach(v => avl.insert(v));
console.log(avl.inorder()); // [1, 2, 3, 4, 5]（平衡後仍是 O(log n) 高度）
紅黑樹（Red-Black Tree）
紅黑樹是另一種自平衡 BST，用顏色標記代替精確的高度控制。相較於 AVL 樹的嚴格平衡，紅黑樹的規則更寬鬆，插入刪除效率更高，因此 Java TreeMap、C++ std::map、std::set 均採用紅黑樹實作。
五條性質（缺一不可）：
- 每個節點是紅色或黑色
- 根節點是黑色
- 葉節點（NIL 節點）是黑色
- 紅色節點的子節點必須是黑色（不能有兩個連續紅節點）
- 從任意節點到其所有後代葉節點的路徑上，黑色節點數量相同（黑高度相同）
為什麼這五條能保證 O(log n)？
由性質 4（紅不連續）和性質 5（黑高度相同），可以推導出：最長路徑（紅黑交替）不超過最短路徑（全黑）的 2 倍。設黑高度為 bh，則樹高 h ≤ 2 * bh = O(log n)。
紅黑樹 vs. AVL 樹的選擇：
| 比較項目 | AVL 樹 | 紅黑樹 |
|---|---|---|
| 平衡嚴格度 | 嚴格（高度差 ≤ 1） | 較寬鬆（最長路徑 ≤ 2 倍最短） |
| 搜尋效能 | 稍快（樹更矮） | 稍慢 |
| 插入旋轉次數 | O(log n) 次旋轉 | O(1) 次旋轉（均攤） |
| 刪除旋轉次數 | O(log n) 次旋轉 | O(1) 次旋轉（均攤） |
| 適合場景 | 讀多寫少 | 讀寫均衡 |
| 實際應用 | — | Java TreeMap、C++ std::map |
C++ 對照
STL 有序容器（底層為紅黑樹）
#include <map>
#include <set>
#include <iostream>
void stdSetExample() {
std::set<int> s = {5, 3, 8, 1, 4, 7, 9};
// lower_bound：第一個 >= key 的迭代器（閉）
auto it = s.lower_bound(4);
std::cout << *it << "\n"; // 4
// upper_bound：第一個 > key 的迭代器（開）
it = s.upper_bound(4);
std::cout << *it << "\n"; // 5
// 範圍查詢：[3, 7] 之間的所有元素
auto lo = s.lower_bound(3);
auto hi = s.upper_bound(7);
for (auto i = lo; i != hi; ++i) {
std::cout << *i << " "; // 3 4 5 7
}
}
void stdMapExample() {
std::map<std::string, int> freq;
// 插入/更新：O(log n)
freq["apple"]++;
freq["banana"] += 2;
freq["apple"] += 3;
// 有序迭代（按 key 的字典序升序）
for (const auto& [word, count] : freq) {
std::cout << word << ": " << count << "\n";
// apple: 4
// banana: 2
}
// lower_bound 在 map 中使用
auto it = freq.lower_bound("b"); // 指向 "banana"
std::cout << it->first << "\n"; // banana
}
裸指標 BST 與 LeetCode 題目
#include <algorithm>
#include <optional>
#include <stack>
// ─── 裸指標 BST（對應 LeetCode 介面）────────────────────────────────────────
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int v = 0, TreeNode* l = nullptr, TreeNode* r = nullptr)
: val(v), left(l), right(r) {}
};
// ─── BST 插入、搜尋、刪除 ─────────────────────────────────────────────────────
class BST {
public:
TreeNode* insert(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
if (val < root->val) root->left = insert(root->left, val);
else if (val > root->val) root->right = insert(root->right, val);
return root;
}
bool search(TreeNode* root, int val) {
while (root) {
if (val == root->val) return true;
root = (val < root->val) ? root->left : root->right;
}
return false;
}
TreeNode* deleteNode(TreeNode* root, int val) {
if (!root) return nullptr;
if (val < root->val) {
root->left = deleteNode(root->left, val);
} else if (val > root->val) {
root->right = deleteNode(root->right, val);
} else {
if (!root->left) return root->right;
if (!root->right) return root->left;
// 找右子樹最小值（中序後繼）
TreeNode* succ = root->right;
while (succ->left) succ = succ->left;
root->val = succ->val;
root->right = deleteNode(root->right, succ->val);
}
return root;
}
};
// ─── 驗證 BST（LeetCode 98）───────────────────────────────────────────────────
class Solution98 {
public:
bool isValidBST(TreeNode* root) {
return check(root, std::nullopt, std::nullopt);
}
private:
bool check(TreeNode* node,
std::optional<long> minVal,
std::optional<long> maxVal) {
if (!node) return true;
if (minVal.has_value() && node->val <= minVal.value()) return false;
if (maxVal.has_value() && node->val >= maxVal.value()) return false;
return check(node->left, minVal, node->val) &&
check(node->right, node->val, maxVal);
}
};
// ─── 第 K 小元素（LeetCode 230）──────────────────────────────────────────────
class Solution230 {
public:
int kthSmallest(TreeNode* root, int k) {
std::stack<TreeNode*> stk;
TreeNode* curr = root;
int count = 0;
while (curr || !stk.empty()) {
while (curr) {
stk.push(curr);
curr = curr->left;
}
curr = stk.top(); stk.pop();
if (++count == k) return curr->val;
curr = curr->right;
}
return -1;
}
};
// ─── AVL Tree C++ 實作 ────────────────────────────────────────────────────────
struct AVLNode {
int val, height;
AVLNode* left;
AVLNode* right;
AVLNode(int v) : val(v), height(1), left(nullptr), right(nullptr) {}
};
class AVLTree {
int height(AVLNode* n) { return n ? n->height : 0; }
void updateHeight(AVLNode* n) {
n->height = 1 + std::max(height(n->left), height(n->right));
}
int bf(AVLNode* n) { return height(n->left) - height(n->right); }
AVLNode* rotateRight(AVLNode* z) {
AVLNode* y = z->left;
AVLNode* T3 = y->right;
y->right = z; z->left = T3;
updateHeight(z); updateHeight(y);
return y;
}
AVLNode* rotateLeft(AVLNode* z) {
AVLNode* y = z->right;
AVLNode* T2 = y->left;
y->left = z; z->right = T2;
updateHeight(z); updateHeight(y);
return y;
}
AVLNode* balance(AVLNode* n) {
updateHeight(n);
int b = bf(n);
if (b > 1 && bf(n->left) >= 0) return rotateRight(n); // LL
if (b > 1 && bf(n->left) < 0) { // LR
n->left = rotateLeft(n->left);
return rotateRight(n);
}
if (b < -1 && bf(n->right) <= 0) return rotateLeft(n); // RR
if (b < -1 && bf(n->right) > 0) { // RL
n->right = rotateRight(n->right);
return rotateLeft(n);
}
return n;
}
AVLNode* _insert(AVLNode* n, int val) {
if (!n) return new AVLNode(val);
if (val < n->val) n->left = _insert(n->left, val);
else if (val > n->val) n->right = _insert(n->right, val);
else return n;
return balance(n);
}
public:
AVLNode* root = nullptr;
void insert(int val) { root = _insert(root, val); }
};
複雜度分析
| 操作 | BST（平均） | BST（最壞，退化） | AVL Tree | 紅黑樹 |
|---|---|---|---|---|
| Search | O(log n) | O(n) | O(log n) | O(log n) |
| Insert | O(log n) | O(n) | O(log n) | O(log n) |
| Delete | O(log n) | O(n) | O(log n) | O(log n) |
| 中序遍歷 | O(n) | O(n) | O(n) | O(n) |
| 空間 | O(n) | O(n) | O(n) | O(n) |
| 旋轉次數（插入） | — | — | O(log n) | O(1) 均攤 |
| 旋轉次數（刪除） | — | — | O(log n) | O(1) 均攤 |
h 為樹高。普通 BST 的 h 介於 O(log n)（平衡）與 O(n)（退化）之間；AVL 樹嚴格保證 h = O(log n)；紅黑樹保證 h ≤ 2 * log₂(n+1)，實際上也是 O(log n)。
變體與延伸
Splay Tree（伸展樹）
Splay Tree 是一種自調整 BST（Self-Adjusting BST）。每次存取（搜尋、插入、刪除）都會把目標節點「伸展（Splaying）」到根節點——通過一系列旋轉。
核心優勢：
- 均攤時間 O(log n)（單次操作最壞 O(n)，但連續 m 次操作總共 O(m log n)）
- 對快取友好（最近存取的節點在根附近，下次存取更快）
- 實作比 AVL 和紅黑樹簡單
適合場景：快取置換、局部性強的存取模式（少數熱點資料被頻繁存取）。
Treap（樹 + 堆）
Treap 是 BST 與最大堆積的結合：每個節點有一個鍵值（key）和一個隨機優先值（priority）。對 key 滿足 BST 性質，對 priority 滿足 Heap 性質。
為什麼有效？ 隨機 priority 使 Treap 的期望形狀接近隨機二元搜尋樹（Random BST），期望樹高為 O(log n)，且不需要複雜的旋轉邏輯——只要維持 heap 性質，旋轉自然而然發生。
適合場景：競程題目、需要簡單實作但又想要期望 O(log n) 效能的場景。
面試考點
驗證 BST 的常見陷阱
// 錯誤做法：只看父子節點關係
function isValidBSTWrong(root: TreeNode | null): boolean {
if (!root) return true;
// 這樣無法偵測到「右子樹的左後代比根節點還小」的情況
const leftOk = !root.left || root.left.val < root.val;
const rightOk = !root.right || root.right.val > root.val;
return leftOk && rightOk &&
isValidBSTWrong(root.left) && isValidBSTWrong(root.right);
}
// 對以下輸入錯誤通過：[5, 1, 4, null, null, 3, 6]
// 4 的左子節點 3 < 4 符合局部條件，但 3 < 5（根），違反整棵樹的 BST 性質
// 正確做法：傳遞全局上下界
function isValidBSTCorrect(root: TreeNode | null): boolean {
function check(node: TreeNode | null, min: number, max: number): boolean {
if (!node) return true;
if (node.val <= min || node.val >= max) return false;
return check(node.left, min, node.val) && check(node.right, node.val, max);
}
return check(root, -Infinity, Infinity);
}
整數溢位防護
LeetCode 98 的節點值可以是 INT_MIN 或 INT_MAX，若用 number 類型（JavaScript 的雙精度浮點數）作為邊界：
// TypeScript 中 -Infinity 和 Infinity 安全處理整數邊界
// 不會有溢位問題（JavaScript number 範圍為 -(2^53-1) 到 2^53-1）
// C++ 版本需要特別注意：
// 錯誤：用 INT_MIN / INT_MAX 作邊界 → 比較時 node->val <= INT_MIN 可能溢位
// 正確：用 std::optional<long> 或 LLONG_MIN / LLONG_MAX
刪除後繼時忘記遞迴刪除
// 常見錯誤：複製後繼值後忘記從右子樹刪除後繼
private _deleteWrong(node: BSTNode, val: number): BSTNode | null {
// ... 找到後繼 ...
node.val = successor.val; // 值複製
// 忘記這一行！樹中出現重複值！
// node.right = this._delete(node.right, successor.val);
return node;
}
LeetCode 練習
LeetCode 98 — Validate Binary Search Tree（Medium）
function isValidBST(root: TreeNode | null): boolean {
function validate(node: TreeNode | null, min: number, max: number): boolean {
if (!node) return true;
if (node.val <= min || node.val >= max) return false;
return validate(node.left, min, node.val) &&
validate(node.right, node.val, max);
}
return validate(root, -Infinity, Infinity);
}
// 時間 O(n)，空間 O(h)
LeetCode 230 — Kth Smallest Element in a BST（Medium）
function kthSmallest(root: TreeNode | null, k: number): number {
const stack: TreeNode[] = [];
let curr: TreeNode | null = root;
let count = 0;
while (curr !== null || stack.length > 0) {
while (curr !== null) { stack.push(curr); curr = curr.left; }
curr = stack.pop()!;
if (++count === k) return curr.val;
curr = curr.right;
}
return -1;
}
// 時間 O(h + k)，空間 O(h)
LeetCode 235 — Lowest Common Ancestor of BST（Medium）
function lowestCommonAncestor(
root: TreeNode, p: TreeNode, q: TreeNode
): TreeNode {
let curr: TreeNode = root;
while (true) {
if (p.val < curr.val && q.val < curr.val) curr = curr.left!;
else if (p.val > curr.val && q.val > curr.val) curr = curr.right!;
else return curr;
}
}
// 時間 O(h)，空間 O(1)
LeetCode 108 — Convert Sorted Array to BST（Easy）
// 中間元素作為根，分治建構高度平衡的 BST
function sortedArrayToBST(nums: number[]): TreeNode | null {
function build(left: number, right: number): TreeNode | null {
if (left > right) return null;
const mid = Math.floor((left + right) / 2);
const node = new TreeNode(nums[mid]);
node.left = build(left, mid - 1);
node.right = build(mid + 1, right);
return node;
}
return build(0, nums.length - 1);
}
// 時間 O(n)，空間 O(log n)（遞迴棧深度 = 樹高）
LeetCode 450 — Delete Node in a BST（Medium）
function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
if (!root) return null;
if (key < root.val) {
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
if (!root.left) return root.right;
if (!root.right) return root.left;
let succ = root.right;
while (succ.left) succ = succ.left;
root.val = succ.val;
root.right = deleteNode(root.right, succ.val);
}
return root;
}
// 時間 O(h)，空間 O(h)
總結
二元搜尋樹是「有序」與「樹」的完美結合，讓字典查詢、範圍查詢、有序統計等問題都能在 O(log n) 內解決。回顧本文的核心知識點：
BST 三大操作：搜尋（利用有序性逐層縮小範圍）、插入（找到正確位置插入）、刪除（三種情況，雙子節點用中序後繼替換）。
中序有序性：BST 的中序遍歷恆為升序，這讓第 K 小、驗證 BST 等問題有了優雅的解法。
退化問題與自平衡：有序插入會讓 BST 退化為 O(n)，AVL 樹（嚴格高度差 ≤ 1）和紅黑樹（黑高度相同+紅不連續）各自用不同策略保證 O(log n)。
選擇依據：讀多寫少選 AVL（搜尋更快）；讀寫均衡選紅黑樹（插入刪除旋轉少）；工業實際幾乎都用紅黑樹（C++ STL、Java TreeMap）。
四大面試陷阱：驗證 BST 必須傳全局上下界、刪除後繼後要遞迴刪除、AVL 旋轉後先更新子節點再更新父節點高度、整數邊界溢位問題。
掌握 BST 及其自平衡變體，是攻克更進階資料結構（Segment Tree、B+ Tree 資料庫索引）的重要基石。希望這篇文章能幫助你建立清晰的 BST 思維，在面試中自信地處理各種樹題。如果有任何問題或疑惑，歡迎至 聯絡頁面 留言交流。
下一篇預告：我們將進入 字典樹（Trie） 的世界，探討如何用多叉樹高效解決字串前綴搜尋、自動補全與單詞過濾等問題。