二叉搜索树

二叉搜索树的定义、性质与基本操作说明

#status / growing #type / concept

[!info] related notes

前置概念: [[binary-tree|二叉树]], [[tree-traversal|树的遍历]]

进阶结构: AVL树, [[red-black-tree|红黑树]], [[b-tree|B树]]

所属 MOC: [[data-structure-moc|数据结构 MOC]]

二叉搜索树 Binary Search Tree

一句话定义

二叉搜索树（BST）是一种二叉树，其中每个节点的值大于左子树所有节点、小于右子树所有节点，从而支持 O(log n) 的查找、插入和删除。

核心机制 / 工作原理

BST 性质（不变量）

对树中任意节点 N：

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

基本操作的时间复杂度

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

中序遍历

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

删除操作的三种情况

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

最小例子

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

查找 6：8 -> 3 -> 6，三次比较，O(log n)
中序遍历：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 树（严格平衡）或红黑树（近似平衡，插入删除旋转更少）。

[[binary-tree|二叉树]]
AVL树
[[red-black-tree|红黑树]]
[[tree-traversal|树的遍历]]
堆