形式陈述

本页聚焦平衡二叉搜索树：在二叉搜索树有序不变量之上，以结构不变量保证含 $n$$n$ 个节点时高度始终为 $O(\log n)$$O(\log n)$。因此搜索具有最坏 $O(\log n)$$O(\log n)$ 时间，插入和删除在沿路径更新后通过旋转、重着色或重构恢复平衡，典型结构也给出最坏 $O(\log n)$$O(\log n)$ 更新。AVL 树限制子树高度差，红黑树限制黑高和连续红节点。伸展树不维持对数高度，单次操作可达 $\Theta(n)$$\mathrm{\Theta }(n)$；它属于自调整搜索树，并以摊还 $O(\log n)$$O(\log n)$ 保证与严格意义的平衡二叉树相邻但不相同。

直觉

普通 BST 可能因有序插入退化成链。平衡条件通过局部调整阻止路径过长，让树始终保持近似对半分割。

例子与边界

向空 BST 依次插入 $1,2,3,\ldots,n$$1,2,3,\dots ,n$ 会得到高度 $n-1$$n-1$；AVL 或红黑树会旋转保持对数高度。旋转保留中序序列，因此不破坏搜索顺序。称“平衡”必须说明保证：随机 BST 的期望高度对随机插入顺序为 $O(\log n)$$O(\log n)$，但没有确定最坏界；伸展树只有摊还界。广义的平衡搜索树还包括多叉外存结构 B 树，但它不属于本页的二叉模型。维护父指针、子树大小等增强字段时，旋转也必须同步更新。

推论与应用

平衡搜索树实现有序映射、集合、范围查询和动态顺序统计，是数据库索引、标准库容器及事件调度的核心抽象。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Robert E. Tarjan, Data Structures and Network Algorithms, SIAM, 1983，Chs. 1–6。