平衡搜索树

普通二叉搜索树的形状由插入顺序决定，有序到来的键会把它拉成一条链。平衡约束首先保证的是整条搜索路径足够短，并不要求每次比较都排除固定比例的节点：高度相近的两棵子树，节点数仍可能相差很大。

以 AVL 树为例，令 $N(h)$ 为高度 $h$ 的合法树所需的最少节点数。高度为 $h$ 的根至少有高度 $h-1$ 和 $h-2$ 的两棵子树，所以 $N(h)=1+N(h-1)+N(h-2)$，其中 $N(-1)=0,N(0)=1$。这个 Fibonacci 型递推随高度指数增长，反过来便得到高度随节点数对数增长。证明用的是最少节点数，而非每个分叉恰好平分。

插入或删除只改变一条祖先路径上的高度或颜色信息，修复因而沿这条路径推进。一次旋转只涉及常数个链接，但整次更新可能要向上检查 $O(\log n)$ 个节点；AVL 删除可在多层旋转，红黑树染色也可能向根传播，不能笼统说所有修复都只需常数步。

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

前三次插入已能看见修复机制：$1$ 的右孩子为 $2$，$2$ 的右孩子为 $3$，根的两侧高度相差 $2$。以 $1$ 为轴左旋后，$2$ 成为根、$1$ 成为左孩子、$3$ 保持右孩子；中序仍为 $1,2,3$。一般左旋还须把原右孩子的左子树接到旧根的右侧，因为其中所有键都位于这两个根键之间。这个中间子树的转移正是旋转保持搜索序的原因。

“平衡”一词必须点明保证类型。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)$。

若需保留旧版本，可用路径复制共享未改子树，但这属于持久化数据结构理路持久化数据结构Persistent data structure · Persistence in data structures更新产生新版本而保留旧版本可访问性，并通过结构共享控制时间与空间的数据结构技术。的额外设计。树高界只控制一次更新涉及多少层，还须检查旋转、父指针与共享节点能否兼容，并分别计算复制节点数和总空间。