二叉搜索树

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$ 替换，再删除原来的 $8$ 叶子，得到中序序列 $1,3,4,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+1)$，不能借用该保证。

若键集固定、各键的查找频率已知，还可以优化加权比较次数，而不只是最坏树高。Knuth 区间优化理路Knuth 区间动态规划优化Knuth optimization · Knuth–Yao optimization在满足四边形不等式与区间单调性的区间递推中，用两段相邻子问题的最优根夹住当前最优根。用相邻区间的最优根夹住当前根，在二次时间构造最优搜索树；频率模型、平局规则与动态更新的接口都要分别说明。

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