二叉搜索树

BST 是二分查找公理库二分查找Binary search在有序数组中反复排除一半候选区间的查找算法。的结构化版本：有序数组靠下标计算中点，BST 则把比较路标直接铸进指针结构——每个结点是一块路牌，“小往左、大往右”，一次比较即可丢弃整棵另一侧子树。换来的收益是动态性：数组中段插入要搬移 $O(n)$ 个元素，BST 只需在叶位挂上新结点。效率的全部秘密在形状：每次比较能丢弃的候选比例取决于左右子树的均衡程度，而形状由键的插入顺序决定，这就是同一键集可能对应高效或退化的树的原因。不变量必须覆盖整棵子树，因为查找只依据路径上的比较导航——任何“越界”滞留的键都会被路径永久绕开。

依次插入 $5,3,8,1,4$：$3$ 入 $5$ 的左侧，$8$ 入右侧，$1$ 入 $3$ 的左侧，$4$ 入 $3$ 的右侧。查找 $4$ 沿 $5\to 3\to 4$，三次比较结束；中序遍历输出 $1,3,4,5,8$。删除有两个孩子的结点（如根 $5$）时，用其中序后继（右子树的最小键 $8$）覆盖它，再转而删除那个后继——后继至多有一个孩子，问题化归为简单情形。

一个经典反例说明“只查父子”不够：根 $5$、左孩子 $3$、$3$ 的右孩子 $6$——每条父子边局部看都合理（$3<5$，$6>3$），但 $6$ 落在 $5$ 的左子树里，违反全局不变量；查找 $6$ 时从 $5$ 起直接右拐，永远碰不到它。另一边界是退化：按 $1,2,\dots ,n$ 递增插入得到高度 $n-1$ 的链，所有操作 $O(n)$；随机顺序插入的期望高度为 $O(\log n)$，但这是对插入顺序的期望，不是最坏保证。同一键集合还对应多棵合法 BST——树的形状携带了插入历史的信息。

BST 是有序字典公理库字典、映射与集合 ADTDictionary ADT · Map ADT · Set ADT以有限偏函数统一刻画按键查询、更新和删除的字典、映射与集合接口。的原型：除查找、插入、删除外，还支持最值、前驱后继与范围查询，这是哈希表公理库哈希表Hash table用哈希函数把键映射到桶并处理冲突的字典结构。不承诺的次序信息。平衡搜索树公理库平衡搜索树Balanced search tree以结构不变量保证对数高度和最坏对数搜索时间的二叉搜索树族。在有序不变量之上追加形状约束，把路径长度升级为最坏 $O(\log n)$；未经平衡的本页结构仍只有 $O(h)$，不能借用该保证。

节点若保存可由孩子合并的摘要，就进入搜索树增强公理库搜索树增强定理与方法Search-tree augmentation在搜索树节点维护可由局部子树摘要恢复的信息，并证明旋转后仍可常数更新。；保存子树大小并暴露 select/rank 接口的具体结构是顺序统计树公理库顺序统计树order-statistic tree · dynamic order statistics在平衡搜索树中维护子树大小，动态支持按秩选择与键的秩查询。。伸展树公理库伸展树splay tree · 伸展树每次访问后把目标旋至根，并以势能获得序列敏感摊还界的自调整搜索树。用访问后的旋转获得摊还界，Treap公理库Treap 与随机优先级搜索树treap · randomized search tree同时满足键的搜索树序和独立随机优先级堆序的随机平衡树。用随机优先级获得期望界，它们都保留 BST 的中序不变量，却给形状加入不同的概率或序列保证。外存场景的多路 B 树再改用块占用不变量，不是二叉指针模型的直接延伸。