小探险家学算法

Appearance

20. 会找路的树（二叉搜索树） ​

知识点：二叉搜索树（BST）—— 左小右大，查找像二分（平均 O(log n)）

项目：成绩管理器（查询 / 插入 / 按顺序打印）

故事开场：三样都想要的老师 ​

期中考试出成绩了。老师要一个"成绩管理器"，三个要求：

  1. 查询：报一个分数，马上知道"有没有这个分"
  2. 插入：新成绩随时加进来
  3. 按顺序打印：随时能把所有成绩从低到高列出来

你翻了翻学过的武器库：

  • 数组 + 二分查找（第 11 章）：查询 O(log n)！打印也快（本来就排着）。 可插入要挪位——O(n)，新成绩多了就慢了
  • Map（第 8 章）：插入 O(1)！可按顺序打印？Map 不按大小排
  • 链表（第 9 章）：插入 O(1)！可查询只能从头走——O(n)

"数组查得快、链表插得快、Map 都不慢……"你叹气，"就没有一个 三个愿望都满足的？"

笨办法先行：把"二分查找"种成一棵树 ​

老师看你发愁，提示了一句："想想第 19 章练习里那个巧合—— 中序遍历二叉树，输出刚好是从小到大！"

你回去翻作业：那棵成绩树是 80 在根，60 在左，90 在右—— 左边的比根小，右边的比根大！所以中序（左→自己→右）就是排序！

"如果我种一棵有纪律的树：左孩子永远比自己小，右孩子永远比自己大……"

  • 查询：从根出发，目标比根小就走左边，比根大就走右边—— 和二分查找一模一样，每次排除半棵树！O(log n)！
  • 插入：也走这条路，走到空位就"挂"上去——像链表一样改一个钩子！
  • 打印：中序遍历，自动从小到大！

你一拍大腿："这棵树自己会找路！"

引出知识点：二叉搜索树——左小右大的树 ​

**二叉搜索树（Binary Search Tree，简称 BST）**的规矩只有一条：

左子树的所有节点 < 根节点 < 右子树的所有节点 （而且左子树、右子树自己也要守这个规矩——递归！）

有了这条规矩，整棵树就是"立起来的二分查找"：

        50
      ↙    ↘
    30      70
   ↙  ↘    ↙  ↘
  20  40  60  80

找 60：50 比 60 小 → 走右 → 70 比 60 大 → 走左 → 找到了！ 三步，排除了 5 个数。树越"平衡"，每次排除的越多，平均 O(log n)。

动手实现：成绩管理器 ​

先造"种树"和"找路"两个函数：

ts
type BSTNode = {
  value: number
  left: BSTNode | null
  right: BSTNode | null
}

function makeNode(value: number): BSTNode {
  return { value: value, left: null, right: null }
}

// 插入：新成绩"走一路、找个空位挂上"
function insert(root: BSTNode | null, value: number): BSTNode {
  if (root === null) {
    return makeNode(value)          // 找到空位！种一个新节点
  }
  if (value < root.value) {
    root.left = insert(root.left, value)     // 比根小 → 去左子树找空位
  } else if (value > root.value) {
    root.right = insert(root.right, value)   // 比根大 → 去右子树找空位
  }
  return root                       // 相等：重复成绩，不种了
}

// 查询：从根出发，一路"问路"
function search(root: BSTNode | null, target: number): boolean {
  if (root === null) {
    return false                    // 问路问到死胡同：没有
  }
  if (root.value === target) {
    return true                     // 找到了！
  }
  if (target < root.value) {
    return search(root.left, target)    // 比根小，去左边问
  }
  return search(root.right, target)     // 比根大，去右边问
}

// 按顺序打印：中序遍历（左 → 自己 → 右）
function inorder(root: BSTNode | null): void {
  if (root === null) { return }
  inorder(root.left)
  console.log(root.value)
  inorder(root.right)
}

组装成成绩管理器：

ts
let root: BSTNode | null = null

root = insert(root, 50)
root = insert(root, 30)
root = insert(root, 70)
root = insert(root, 20)
root = insert(root, 40)
root = insert(root, 60)
root = insert(root, 80)

console.log("有 60 分吗？" + search(root, 60))    // true
console.log("有 65 分吗？" + search(root, 65))    // false

// 新成绩插入
root = insert(root, 65)
console.log("插入 65 后有 65 分吗？" + search(root, 65))   // true

console.log("按顺序打印所有成绩：")
inorder(root)

输出：

有 60 分吗？true
有 65 分吗？false
插入 65 后有 65 分吗？true
按顺序打印所有成绩：
20
30
40
50
60
65
70
80

查询、插入、按顺序打印——三个愿望，一棵树全满足！

跑起来：BST 的"路"有多短？ ​

和数组版"插入 + 查找"比比看：造 2 万个成绩，交替插入、查询：

ts
// 造 2 万个随机成绩，插进 BST
let tree: BSTNode | null = null
for (let i = 0; i < 20000; i++) {
  tree = insert(tree, Math.floor(Math.random() * 100000))
}

// 查询 1000 次
console.time("BST 查询 1000 次")
let hit = 0
for (let i = 0; i < 1000; i++) {
  if (search(tree, Math.floor(Math.random() * 100000))) {
    hit++
  }
}
console.timeEnd("BST 查询 1000 次")
console.log("查到了 " + hit + " 次")

在我这台电脑上，输出（数字可能不一样）：

BST 查询 1000 次: 0.5ms

1000 次查询，半毫秒。每次查询只走大约 15 层（log₂ 20000 ≈ 15） ——2 万个数，每层排除一半，15 步就能到任何地方。 这比数组的二分查找（不用挪位）还方便：插入和查询一样快。

危险：树长歪了怎么办？ ​

老师突然说："把成绩按从小到大的顺序插进去试试！"

ts
let crooked: BSTNode | null = null
for (let i = 1; i <= 10; i++) {
  crooked = insert(crooked, i)     // 1, 2, 3, 4, ..., 10
}
inorder(crooked)

树变成了什么样？画一画：

1
 \
  2
   \
    3
     \
      4
       \
        ...

长成一条链了！ 每个新节点都比根大，永远往右挂—— "树"退化成了"链表"！查询"10"要走 10 步（O(n)）， 查询"1 万"要走 1 万步——BST 的 O(log n) 没了！

所以真正的二叉搜索树都有"防歪"机制：插完自动旋转，让树保持 两边差不多高（这叫平衡）。你以后会学到 AVL 树、红黑树—— 它们就是"不会长歪的 BST"。今天先记住： BST 平均 O(log n)，但前提是树不能歪。

小挑战 ​

  1. 找最小 / 找最大：BST 里最小的数在哪里？最大的呢？ 写 findMin(root) 和 findMax(root)（提示：一路往左走 / 一路往右走，走到走不动为止——不用递归也行！）。
  2. 数节点：写 countNodes(root) 数出一共有多少个节点 （提示：1 + 左子树 + 右子树，递归）。
  3. 成绩范围：找出所有"60 到 80 之间"的成绩（提示：中序遍历时， 只打印范围内的——或者更聪明：如果根小于 60，左边整棵都不用看！）。

课后练习 ​

第 1 题（动手题）：种一棵自己的 BST ​

依次插入 [5, 3, 8, 1, 4, 7, 9]，画出这棵树（在纸上）， 然后回答：树高几层？中序遍历输出什么？用程序验证。

参考答案（点开查看）
        5
      ↙    ↘
    3        8
   ↙  ↘    ↙  ↘
  1    4  7    9
  • 树高 3 层（5 → 3 → 1 是 3 步）
  • 中序遍历：1 3 4 5 7 8 9（从小到大！）

程序验证：insert 依次种入，inorder 输出应该完全一致。

第 2 题（思考题）：为什么中序遍历是排序？ ​

BST 的规矩是"左 < 根 < 右"，中序遍历是"左 → 自己 → 右"。 把这两个结合起来，解释一下为什么中序遍历的输出一定是从小到大。

参考答案（点开查看）

中序遍历每个节点时，都先走完它的左子树（全比它小）， 然后打印它自己，再走右子树（全比它大）。

所以打印的顺序是：小 → 中 → 大，一层层递归下去， 整棵树打印出来就是从小到大。

一句话：树的规矩（左小右大） + 遍历的顺序（左中右） = 排序。 这就是 BST 的"隐藏技能"——它天然自带排序输出。

第 3 题（思考题）：BST vs Map ​

BST 能"按顺序打印"，Map 不能。那 BST 能完全替代 Map 吗？ （提示：想想 Map 的 O(1) 是从哪来的，BST 是多少。）

参考答案（点开查看）

不能完全替代。

  • Map 查找是 O(1)（哈希函数一步算出位置），BST 是 O(log n)（要走几层）
  • 所以"只要查得快"的场景，Map 更优

但 Map 有两个短板：① 不能按大小顺序遍历 ② 不能找"比 X 小的有多少个" 这类范围问题。BST（和它的平衡版本）擅长这些。

选择口诀：只要"按键查找"→ Map；要"有序 + 范围查询"→ BST。 两种结构都常用，谁也替代不了谁。

下一课预告：游戏排行榜！班主任要知道"全班最高分"，而且 新成绩随时进来、旧成绩随时出去。数组？每次找最大要遍历 一遍 O(n)。BST？找最大要一路往右走。有没有一个结构， 最顶上永远放着最大的数，取它只要一步？