二元搜尋樹 Binary search tree · 資料結構 Data Structures

二元搜尋樹

左邊都比較小、右邊都比較大的樹：查找、插入、刪除都只走一條路徑，但路徑多長取決於插入的順序。

走過的路徑找到／新加入補位的後繼者

每個節點左邊的都比它小、右邊的都比它大。查找時每走一步都能丟掉一整棵子樹。試試「依序插入」：同樣是 15 個數，樹會長成一條線。

節點

樹高

最矮可能的高度

這次走了幾個節點

–

亮起來的是這一步執行的程式碼

1class TreeNode {
2  left: TreeNode | null = null;
3  right: TreeNode | null = null;
4  constructor(public key: number) {}
5}
6 
7class BST {
8  root: TreeNode | null = null;
9 
10  search(key: number): boolean {
11    let node = this.root;
12    while (node) {
13      if (key === node.key) return true;
14      node = key < node.key ? node.left : node.right;
15    }
16    return false;
17  }
18 
19  insert(key: number): void {
20    this.root = this.insertAt(this.root, key);
21  }
22 
23  private insertAt(node: TreeNode | null, key: number): TreeNode {
24    if (!node) return new TreeNode(key);
25    if (key < node.key) node.left = this.insertAt(node.left, key);
26    else if (key > node.key) node.right = this.insertAt(node.right, key);
27    return node;
28  }
29 
30  delete(key: number): void {
31    this.root = this.deleteAt(this.root, key);
32  }
33 
34  private deleteAt(node: TreeNode | null, key: number): TreeNode | null {
35    if (!node) return null;
36    if (key < node.key) node.left = this.deleteAt(node.left, key);
37    else if (key > node.key) node.right = this.deleteAt(node.right, key);
38    else if (!node.left) return node.right;
39    else if (!node.right) return node.left;
40    else {
41      let min = node.right;
42      while (min.left) min = min.left;
43      node.key = min.key;
44      node.right = this.deleteAt(node.right, min.key);
45    }
46    return node;
47  }
48}

模型假設與範圍

Big O 與實測步數以頁面列出的基本操作為單位；視覺化的快照、畫圖、程式高亮和輸出成本另計，不是執行時間 benchmark。

什麼時候用

需要保持排序：依序走訪、找前一個或後一個、範圍查詢。
實務上用的是會自我平衡的版本（紅黑樹、AVL 樹、B-tree；AVL 取自發明者 Adelson-Velsky 與 Landis 的姓氏）。這裡展示不平衡的基本款，正好看得出為什麼需要平衡。

和其他主題的關係

被這些用到: AVL 樹紅黑樹
延伸閱讀: 演算法 · 二分搜尋堆積

語言內建的版本

Array<number> + binary search

JavaScript 沒有排序過的 map 或 set：Map 和 Set 只記得插入順序。要「找比 x 大的最小鍵」，最常見的做法是維持一個排序好的陣列，用二分搜尋找位置。

操作	寫法	成本
找第一個 ≥ x 的位置	`lowerBound(keys, 25)`	O(log n)
插入並保持排序	`keys.splice(lowerBound(keys, 25), 0, 25)`	O(n)
ceiling：≥ x 的最小鍵	`keys[lowerBound(keys, 26)]`	O(log n)
依鍵排序列出	`[...m.keys()].sort((x, y) => x - y)`	O(n log n)

// No sorted map or set: keep a sorted array and binary-search it.
function lowerBound(a: number[], x: number): number {
  let lo = 0, hi = a.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (a[mid] < x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}
 
const keys = [10, 20, 30, 40];
lowerBound(keys, 25);                        // → 2
keys.splice(lowerBound(keys, 25), 0, 25);    // → []
keys;                                        // → [10, 20, 25, 30, 40]
keys[lowerBound(keys, 26)];                  // → 30
keys[lowerBound(keys, 26) - 1];              // → 25
keys[lowerBound(keys, 99)];                  // → undefined
 
const m = new Map([[3, "c"], [1, "a"], [2, "b"]]);
[...m.keys()];                               // → [3, 1, 2]
[...m.keys()].sort((x, y) => x - y);         // → [1, 2, 3]
 
// The node shape LeetCode uses for tree problems.
class TreeNode {
  constructor(
    public val = 0,
    public left: TreeNode | null = null,
    public right: TreeNode | null = null,
  ) {}
}
const root = new TreeNode(2, new TreeNode(1), new TreeNode(3));
root.left?.val;                              // → 1
root.right?.right;                           // → null

每個 → 後面的結果都是實際執行這段程式碼驗證過的。

排序陣列查詢是 O(log n)，但插入和刪除要搬移後面的元素，是 O(n)。資料大多是先建好再查詢時很划算；一邊插入一邊查詢又很大量時，就得自己寫平衡樹，或改用 skip list。
lowerBound 回傳的位置可能等於陣列長度（沒有 ≥ x 的鍵），這時讀到的是 undefined，不會丟錯。找 floor（≤ x 的最大鍵）時要先檢查 x 本身在不在，再看前一格。

時間與空間複雜度（Big O）

操作	平均	最差
查找平均指的是隨機順序插入；依序插入就是最差情況	O(log n)	O(n)
插入	O(log n)	O(n)
刪除	O(log n)	O(n)
依序走訪	O(n)	O(n)
平衡樹（紅黑、AVL）的以上操作	O(log n)	O(log n)

空間：O(n)，每個節點多兩個指標

Big O 實測：n 變大時步數怎麼長

數的是：找一個存在的值平均走過的節點數

	Big O	n = 1,000	n = 2,000	n = 4,000	n = 8,000	成長倍數：實測（理論）
隨機順序插入	O(log n)	11.2	13.6	14.2	16.1	×1.4 (×1.3)
依序插入	O(n)	501	1,001	2,001	4,001	×8.0 (×8.0)

同樣的鍵、不同的插入順序：一個每次 n 加倍只多走一兩步，另一個跟著 n 一起加倍。這張表的 n 比較小，因為依序插入的版本建一棵樹要 O(n²)。

和其他做法比

	樹高	找一個值平均走幾個節點	最矮可能的高度
隨機順序插入	22	11.2	10
依序插入	1,000	500.5	10

同樣是 0 到 999 這 1,000 個數，只差在插入的順序。依序插入時每個新節點都接在最右邊，樹高就等於節點數，查找和掃一遍陣列一樣慢。紅黑樹、AVL 這類平衡樹會在插入時旋轉，保證樹高維持在 log n 的常數倍。

真實世界裡的它

C++ 的 std::map、Java 的 TreeMap（紅黑樹）。
資料庫索引的 B+ tree 是同一個想法，只是每個節點放幾百個鍵，讓樹只有三、四層，每層一次磁碟讀取。

取捨與陷阱

依序插入會退化成一條串列，查找變得和掃陣列一樣慢（試試「依序插入 15 個」）。
刪除有兩個子節點的節點最麻煩：要用右子樹最小的節點（後繼者）來補位。
指標多、節點散在記憶體各處，對 CPU 快取不友善：同樣是 O(log n)，實際上常比排序陣列＋二分搜尋慢。

資料結構