[!info] related notes

• 前置概念: 二叉树与遍历
• 平衡机制: AVL 树
• 查找结构对比: 哈希表与有序表
• 所属 MOC: 算法面试题型 MOC

二叉搜索树 Binary Search Tree

一句话定义

二叉搜索树（BST）是一种二叉树，其中每个节点的值大于左子树所有节点、小于右子树所有节点。查找、插入和删除需要 O(h) 时间，h 是树高；平衡时为 O(log n)，退化成链表时为 O(n)。这里先讨论键不重复的版本。

核心机制 / 工作原理

BST 性质（不变量）

对树中任意节点 N：

• N 的左子树中所有节点的值 < N 的值
• N 的右子树中所有节点的值 > N 的值
• 左、右子树本身也分别是 BST（递归定义）

基本操作的时间复杂度

操作	树高为 O(log n) 时	最坏（退化为链表）
查找	O(log n)	O(n)
插入	O(log n)	O(n)
删除	O(log n)	O(n)

中序遍历

对 BST 进行中序遍历（左 -> 根 -> 右），输出的序列恰好是升序排列。这是 BST 最重要的性质之一，也是验证一棵树是否为 BST 的常用方法。

删除操作的三种情况

1. 叶子节点 — 直接删除
2. 只有一个子节点 — 用子节点替换该节点
3. 有两个子节点 — 找到右子树中的最小节点（后继），用后继的值替换该节点，然后删除后继

最小例子

       8
      / \
     3   10
    / \    \
   1   6    14
      / \
     4   7

• 查找 6：8 -> 3 -> 6，这个例子需要三次比较；一般复杂度取决于树高。
• 中序遍历：1, 3, 4, 6, 7, 8, 10, 14（升序）
• 插入 5：8 -> 3 -> 6 -> 4 -> 插到 4 的右子节点

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

function search(root, target) {
  if (!root) return false;
  if (target === root.val) return true;
  if (target < root.val) return search(root.left, target);
  return search(root.right, target);
}

边界与常见误解

• “BST 一定是平衡的” — 错。如果按升序插入 1,2,3,4,5，BST 退化为链表，所有操作变成 O(n)。平衡需要额外机制。
• “BST 等于二叉树” — BST 是二叉树的特例，必须满足左 < 根 < 右的约束。
• 不允许重复值？ — 取决于实现。若允许重复值，必须相应调整不变量，例如统一放到右侧，或在节点中维护计数；不能同时沿用上面的严格大小关系。
• BST vs 哈希表 — BST 保持有序，支持范围查询（如 “找 3~8 之间的所有值”），哈希表不支持。但哈希表平均查找是 O(1)。
• 为什么需要平衡 BST — 为保证最坏情况仍是 O(log n)，引入 AVL 树（严格平衡）或红黑树（近似平衡，插入删除旋转更少）。

学习检查

• 按升序插入键时，BST 为什么会退化？
• 为什么验证 BST 不能只比较节点与它的直接孩子？
• 删除有两个孩子的节点时，为什么可以用中序后继替换？