二叉搜索树 - 算法与数据结构教程

讲解

二叉搜索树（BST）在普通二叉树上加了一条序约束：对任意节点，左子树所有值 < 节点值 < 右子树所有值。注意是「整棵子树」而不只是直接孩子——这是验证 BST 时最常掉的坑。这条约束带来的超能力是：查找、插入、删除都能沿一条从根到叶的路径完成，每次比较排除半棵树，理想（树平衡）情况下全是 O(log n)。若树退化成链（连续插入升序数据），则退回 O(n)——这正是工程中使用自平衡 BST（红黑树、AVL）的原因，语言内置的有序 Map 背后都是它们。

BST 的皇牌性质：中序遍历产出升序序列。验证 BST 可以中序遍历后检查单调；找第 K 小元素就是中序数到第 K 个；把 BST 修成合法（两节点被误交换）也靠中序序列里的逆序对定位。遇到 BST 题先想「中序视角下这题在问什么」。

两个进阶操作。最近公共祖先（LCA）在 BST 上有捷径：从根出发，p、q 都在左侧就往左走，都在右侧就往右走，第一次「分道扬镳」（或命中其一）的节点就是 LCA——O(h) 一次走到底，不用像普通二叉树那样递归回传。删除是 BST 最难的基本操作：目标是叶子直接摘；只有一个孩子用孩子顶替；有两个孩子时，用右子树的最小值（中序后继）顶替目标的值，再递归删掉那个后继——这一步把「删双孩子节点」归约成「删后继节点」，而后继最多只有一个孩子。

示例

BST 全操作：插入、查找、验证（上下界法）、LCA、删除（中序后继法），配中序遍历断言：

import assert from 'node:assert/strict';

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function insertIntoBST(root, val) {
  if (root === null) return new TreeNode(val);
  if (val < root.val) root.left = insertIntoBST(root.left, val);
  else root.right = insertIntoBST(root.right, val);
  return root;
}

function searchBST(root, val) {
  let cur = root;
  while (cur !== null) {
    if (cur.val === val) return cur;
    cur = val < cur.val ? cur.left : cur.right;
  }
  return null;
}

// 验证 BST：每个节点带合法开区间 (lo, hi)，向下递归时收紧
function isValidBST(root) {
  function go(node, lo, hi) {
    if (node === null) return true;
    if (node.val <= lo || node.val >= hi) return false;
    return go(node.left, lo, node.val) && go(node.right, node.val, hi);
  }
  return go(root, -Infinity, Infinity);
}

// BST 的 LCA：一次走到底，O(h)
function lowestCommonAncestor(root, p, q) {
  let cur = root;
  while (cur !== null) {
    if (p < cur.val && q < cur.val) cur = cur.left;
    else if (p > cur.val && q > cur.val) cur = cur.right;
    else return cur; // 分道扬镳处即祖先
  }
  return null;
}

// 删除：双孩子节点用右子树最小值（中序后继）顶替
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 succ = root.right;
  while (succ.left !== null) succ = succ.left;
  root.val = succ.val;
  root.right = deleteNode(root.right, succ.val);
  return root;
}

function inorder(root) {
  if (root === null) return [];
  return [...inorder(root.left), root.val, ...inorder(root.right)];
}

let bst = null;
for (const v of [5, 3, 7, 2, 4, 6, 8]) bst = insertIntoBST(bst, v);
assert.deepStrictEqual(inorder(bst), [2, 3, 4, 5, 6, 7, 8]); // 中序 = 升序
assert.strictEqual(isValidBST(bst), true);
assert.strictEqual(searchBST(bst, 4).val, 4);
assert.strictEqual(searchBST(bst, 9), null);
assert.strictEqual(lowestCommonAncestor(bst, 2, 4).val, 3);
assert.strictEqual(lowestCommonAncestor(bst, 2, 8).val, 5);

bst = deleteNode(bst, 3); // 3 有双孩子
assert.deepStrictEqual(inorder(bst), [2, 4, 5, 6, 7, 8]);
assert.strictEqual(isValidBST(bst), true);

// 反例：4 的左子树里有 3，违反「整棵子树」约束
const bad = new TreeNode(5, new TreeNode(1), new TreeNode(4, new TreeNode(3), new TreeNode(6)));
assert.strictEqual(isValidBST(bad), false);

console.log('BST 示例全部通过');

重点看反例 bad：节点 4 的左孩子 3 小于 4，局部看没问题，但 3 处在根 5 的右子树里，违反了「大于 5」的祖先约束——只用「孩子与父亲比较」的判断会漏掉它，上下界法则能抓住。

常见坑

验证 BST 只比直接孩子：约束是「整棵子树」，必须携带从上到下的合法区间（上下界法），或中序检查单调。
上下界写成闭区间：题目通常要求严格小于/大于，界是开区间，判断用 <= lo 或 >= hi 拒绝。
删除时直接摘双孩子节点：会丢掉一整棵子树；正确做法是值替换（中序后继/前驱）再删后继。
以为 BST 查找永远 O(log n)：退化成链时是 O(n)；面试被追问就提平衡树（AVL、红黑树）。
LCA 在普通树和 BST 上混用模板：BST 用值比较一路下走即可；普通二叉树才需要递归回传「左右是否各找到一个」。

小结

BST = 左 < 根 < 右（整棵子树）；中序遍历得升序；查找/插入/删除沿一条路径 O(h)；删除双孩子用中序后继顶替；验证要带上下界。下一章看另一种植根于树的结构：堆与优先队列。