平衡搜索树

普通二叉搜索树的形状由插入顺序决定，有序到来的键会把它拉成一条链，搜索退化为线性扫描。平衡不变量的作用是让“每次比较都排除大约固定比例的候选”始终成立——树高对数正是这句话的形状化表述。设计上的巧妙在于不变量是局部的：违反只发生在更新路径附近，用常数个局部旋转或染色即可修复，无须全局重建；而“局部约束蕴含全局对数高度”正是每种平衡方案各自需要证明的定理。可以把不变量想成一根张紧的弓弦：每次更新轻微拨动，修复动作立即把形变限制在允许范围内。

向空树依次插入 $1,2,\dots ,n$：普通 BST 得到高度 $n-1$ 的右链；AVL 树则沿途不断触发旋转，例如插入 $1$ 至 $7$ 后得到以 $4$ 为根、高度为 $2$ 的完全平衡树。这一对照说明平衡树的最坏保证不依赖输入顺序的任何随机性。

“平衡”一词必须点明保证类型。AVL 与红黑树给出最坏情形界；随机顺序插入下普通 BST 的期望高度是 $O(\log n)$，却不是最坏保证；伸展树单次操作可达 $\mathrm{\Theta }(n)$，提供的是摊还公理库摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。 $O(\log n)$。面向外存块传输公理库外存 / I/O 模型External-memory model · I/O model · Aggarwal–Vitter model只计大小为 B 的数据块在容量为 M 的内存与外存之间传输次数的两层存储模型。的B 树公理库B 树B-tree以高扇出、有界节点占用率和等深叶层降低外存查找 I/O 的平衡搜索树。和B+ 树公理库B+ 树B+ tree · B-plus tree将全部记录保存在等深叶层、以内部路由键和叶链同时支持单键与范围访问的多路搜索树。采用多路节点与占用率不变量，不是本页二叉旋转模型的“高叉变体”。节点若带父指针、子树大小等增强字段，每次旋转都必须同步更新，否则相关查询会失效。

平衡搜索树实现有序字典公理库字典、映射与集合 ADTDictionary ADT · Map ADT · Set ADT以有限偏函数统一刻画按键查询、更新和删除的字典、映射与集合接口。，支持查找、更新、前驱后继与范围查询。扫描线公理库扫描线范式Sweep-line paradigm · Plane sweep按事件推进一条虚拟直线，并用动态有序状态维护当前横截面组合关系的计算几何范式。还可用它维护与当前横截线相交对象的动态次序，使“找几何相邻对象”落到前驱、后继与局部更新。若节点再维护子树摘要，旋转时必须同步重算；这套通用方法由搜索树增强公理库搜索树增强定理与方法Search-tree augmentation在搜索树节点维护可由局部子树摘要恢复的信息，并证明旋转后仍可常数更新。说明，维护子树大小的具体接口则形成顺序统计树公理库顺序统计树order-statistic tree · dynamic order statistics在平衡搜索树中维护子树大小，动态支持按秩选择与键的秩查询。。增强字段不自动继承复杂度，只有字段能由孩子在 $O(1)$ 时间合并时，更新才继续保持相应的最坏 $O(\log n)$。

本页的中心是“结构不变量怎样保证高度”，而非罗列全部树族。伸展树公理库伸展树splay tree · 伸展树每次访问后把目标旋至根，并以势能获得序列敏感摊还界的自调整搜索树。不保持逐时对数高度，只给操作序列上的摊还 $O(\log n)$；Treap公理库Treap 与随机优先级搜索树treap · randomized search tree同时满足键的搜索树序和独立随机优先级堆序的随机平衡树。用随机优先级得到期望对数高度；B 树公理库B 树B-tree以高扇出、有界节点占用率和等深叶层降低外存查找 I/O 的平衡搜索树。面向块传输，以多路节点占用率换取 $O({\log }_{B}n)$ 级 I/O。保留旧版本并共享未改子树还属于持久化数据结构公理库持久化数据结构Persistent data structure · Persistence in data structures更新产生新版本而保留旧版本可访问性，并通过结构共享控制时间与空间的数据结构技术。问题，需要另计复制与空间。这些结构共享“有序搜索”目标，却不能把保证类型和成本模型互换。