高级数据结构

二叉搜索树

定义与那条最有用的推论

BST 的定义是递归的：

对每个节点，左子树里所有节点都比它小，右子树里所有节点都比它大。

🚨 注意是「所有节点」而不是「左右孩子」。这两者的差别就是下面那个经典错法的来源。

由定义直接推出一条性质，也是解 BST 题的万能钥匙：

⭐ 中序遍历 BST，得到升序序列。

前中后序那篇讲过为什么 —— 中序是「左 → 根 → 右」，正好对应「小 → 中 → 大」。

📌 遇到 BST 先想中序，命中率极高。一大批题的解法就是 「中序遍历 + 在中序位置做点事」。

查找与插入：沿着一条路走

function searchBST(root, val) {
  while (root !== null) {
    if (root.val === val) return root;
    root = val < root.val ? root.left : root.right;   // 只走一边
  }
  return null;
}

function insertIntoBST(root, val) {
  if (root === null) return { val, left: null, right: null };
  if (val < root.val) root.left = insertIntoBST(root.left, val);
  else root.right = insertIntoBST(root.right, val);
  return root;                    // ⭐ 把子树接回去，所以要返回
}

⭐ 递归函数返回子树、调用方接住 —— 这是链表和树的修改类操作的通用写法。 不返回的话，新建的节点接不到父亲身上。

⚠️ 复杂度是 O(h)，h 是树高。平衡时 O(log n)， 退化成一条链时 O(n) —— 按升序依次插入就会退化。实测：

随机那一列取 21 个种子的中位数（括号内是区间）：

n 升序插入的树高 随机顺序的树高 log₂n 比值
100 100 13 (11~15) 6.6 1.96
1,000 1,000 22 (20~27) 10.0 2.21
5,000 5,000 27 (24~32) 12.3 2.20
20,000 🚨 爆栈 33 (31~41) 14.3 2.31
100,000 🚨 爆栈 43 (37~45) 16.6 2.59

⭐ 升序插入时树高恰好等于 n，一个分叉都没有 —— 它已经不是树了，是链表。 这一列不用测，是确定的。

🚨 但后两行跑不出来 —— 上面那份递归的 insertIntoBST 直接 RangeError。 本机的阈值在 1.1 万个节点附近（栈大小相关，只记量级）。 换成非递归插入（while 沿着一条路走下去）就能建到 10 万，树高确实恰好等于 n。 👉 所以退化的后果不只是「变慢」：O(h) 的递归实现在 h 变成 n 之后 会直接崩掉，而崩的位置在插入，不在查询。

⚠️ 而随机那一列不是「约 2.3 倍」这么简单 —— 看最后一列， 比值从 1.96 涨到 2.59，它还在往上走。 （n=1000 与 n=5000 两档看着持平在 2.2，是中位数取整造成的： 22/9.966 = 2.208、27/12.288 = 2.197，真实差距只有 0.010 —— 表里那两个 10.0 和 12.3 是显示用的，别拿它们去算比值。） 📌 已知结论的正确形式是渐近的：随机 BST 的期望树高 ~ 4.311 · ln n （换成 log₂ 是 2.99 · log₂n）。这些 n 上实测只到理论值的 0.65~0.87， 还没收敛过去 —— 所以「2.3 倍」是这几档的观测值，不是那条结论本身。

🚨 值得注意的是有序输入是最常见的输入（从数据库按 id 读出来、 从排好序的文件读进来），所以这个最坏情况在真实场景里一点都不罕见。 真实工程里用的是红黑树 / AVL 这类自平衡 BST，面试知道有这回事即可。

删除：三种情况

删除是 BST 里唯一麻烦的操作，因为要保持结构合法。

function deleteNode(root, key) {
  if (root === null) return null;

  if (key < root.val) { root.left = deleteNode(root.left, key); return root; }
  if (key > root.val) { root.right = deleteNode(root.right, key); return root; }

  // 找到了，三种情况：
  if (root.left === null) return root.right;    // ① 没有左孩子 → 右孩子顶上
  if (root.right === null) return root.left;    // ② 没有右孩子 → 左孩子顶上

  // ③ 两个孩子都有：用右子树的最小节点（中序后继）替换自己
  let successor = root.right;
  while (successor.left !== null) successor = successor.left;

  root.val = successor.val;
  root.right = deleteNode(root.right, successor.val);   // 🚨 把后继从右子树里删掉
  return root;
}

⭐ 情况 ① ② 合起来覆盖了「叶子节点」（两个孩子都为空时，返回 null）， 所以不用单独写第四个分支。

🚨 情况 ③ 为什么必须用右子树的最小值（或左子树的最大值）？ 因为要找一个「放在这个位置仍然合法」的值 —— 它必须比左子树全部大、比右子树全部小，而这样的值只有两个： 左子树的最大值和右子树的最小值，也就是这个节点的中序前驱和中序后继。

⚠️ 最后那行 deleteNode(root.right, successor.val) 不能省。 只改 root.val 不删原来那个后继节点的话，树里会出现两个相同的值。

实测（每组 2000 次，随机 BST 各随机删一个节点）：

树的规模      出现重复值        触发「两个孩子都有」   两者相等？
3~17         454 (22.7%)      454                  ✅
5~30         572 (28.6%)      572                  ✅
10~50        621 (31.1%)      621                  ✅

⭐ 「重复值」与「触发那个分支」的组数逐个相等 —— 这比出错率有用得多： 只要删的节点有两个孩子，就一定留下重复值；否则一定不留。 出错率本身只反映「随机删到双孩子节点的概率」，随树的规模从 22.7% 涨到 31.1%。

⚠️ 而所有出现重复值的组，中序全部仍是非递减的（454/454、572/572、621/621）。

🚨 这就是它难发现的原因：中序序列看起来完全正常，只是某个值出现了两次。 用「中序是否递增」来自测的话，得用严格递增（>）而不是非递减（>=） —— 差一个等号，这个 bug 就漏网了。实测严格递增能抓到全部，一个不漏。

🚨 验证 BST：只比较父子是错的

这是 BST 最经典的坑：

// ❌ 错误写法
function isValidBST(root) {
  if (root === null) return true;
  if (root.left && root.left.val >= root.val) return false;
  if (root.right && root.right.val <= root.val) return false;
  return isValidBST(root.left) && isValidBST(root.right);
}

它只检查了「每个节点和它的直接孩子」，而定义要求的是整棵子树。反例：

      5
     / \
    1   6
       / \
      3   7      ← 3 在 5 的右子树里，却比 5 小

每一对父子都合法（6>5, 3<6, 7>6, 1<5），但 3 违反了「右子树全部大于 5」。 错误写法会返回 true。

正确做法是把「允许的范围」一路传下去：

function isValidBST(root, min = null, max = null) {
  if (root === null) return true;
  if (min !== null && root.val <= min) return false;
  if (max !== null && root.val >= max) return false;
  return isValidBST(root.left, min, root.val)      // 左子树上界收紧成 root.val
      && isValidBST(root.right, root.val, max);    // 右子树下界收紧成 root.val
}

⭐ 另一种同样正确的写法是中序遍历，检查是否严格递增 —— 直接用上那条万能性质，代码更短，还顺便验证了重复值。

⚖️ 「用 Infinity 当边界会被极端值坑」—— 这条我写错了

这一篇原本写着「节点值可能就是 Number.MIN_SAFE_INTEGER 之类的极端值， 所以用 null 更稳」。实测推翻：

Number.MIN_SAFE_INTEGER > -Infinity        true
两种写法在 3000 组随机树（含人为破坏成非法的）上   结论完全一致，0 组分歧
单节点分别取 MIN_SAFE_INTEGER / MAX_SAFE_INTEGER / ±2³¹ / 0   0 个分歧

-Infinity 比任何有限数都小，Infinity 比任何有限数都大 —— 这正是它们存在的意义。用 Infinity 当哨兵是安全的。

📌 这条错误断言的来源大概是把 JavaScript 和 C++ 混了：C++ 里用 INT_MIN/INT_MAX 当哨兵确实会被等于边界的节点值坑，那时才需要改用 long long 或可空类型。JS 的 Number 没有这个问题。

⭐ 两种写法都对，null 版的好处只剩「意图更明显」这一条 —— 读代码的人一眼看出「这里还没有边界」，而不用想 -Infinity 是不是真的够小。

BST 中第 k 小的元素

中序遍历的第 k 个就是答案，不需要排序：

function kthSmallest(root, k) {
  let count = 0, res = null;
  function inorder(node) {
    if (node === null || res !== null) return;   // 找到就不用再走了
    inorder(node.left);
    if (++count === k) { res = node.val; return; }
    inorder(node.right);
  }
  inorder(root);
  return res;
}

⭐ res !== null 那个提前返回让平均复杂度降到 O(h + k)， 而不是每次都遍历整棵树。10000 个节点的随机 BST， 数访问过的非 null 节点数（21 个种子取中位数，括号内是区间）：

k 带提前返回 不带 省下
1 10 (4~17) 10,000 (9989~10000) 99.9%
10 19 (13~26) 10,000 (9989~10000) 99.8%
100 109 (102~114) 9,999 (9868~10000) 98.9%
1,000 1,008 (1005~1016) 9,998 (9974~10000) 89.9%
10,000 10,000 10,000 0%

⚠️ 「不带」那一列为什么不是恒等于 10000，值得单独说一句： if (++count === k) { res = node.val; return; } 里的 return 本身 就跳过了当前节点的右子树 —— 少访问的正好是那棵右子树。 实测验证：k=1 时最左节点的右子树有 2 个节点，访问数正好是 10000 - 2 = 9998。 📌 所以就算你以为「去掉提前返回就是全量遍历」，它也不是。

🚨 k = 1 时只访问约 10 个节点，但那不是树高 —— 这棵树的树高是 30 左右（见前面那张表：n=10 万时 43）。 访问数等于**「一路向左的深度」（左脊长度）， 21 个种子上两者逐个相等**。两个量的期望差三倍：

一路向左的深度   ≈ ln n        = 9.2      ← k=1 访问的就是这个
随机 BST 的树高  ≈ 4.311·ln n  = 39.7

k 接近 n 时优势归零，符合 O(h + k) 的形状。

📌 如果这个操作很频繁，正经做法是在每个节点上维护子树大小， 查询降到 O(h)。面试被追问「如果要频繁查询呢」，这是想听的答案。

下一步

BST 靠的是「有序」，二叉堆靠的是另一种更弱的约束 —— 只保证父子之间有序，兄弟之间不管。约束更弱，换来的是 O(1) 拿最值。

练习

勾选记录做过哪些，0 / 6 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。