平衡树

平衡树是一类高度平衡（左右子树高度相近）的有序二叉搜索树（BST）, 保证：

• 中序遍历是有序序列（BST的性质）
• 树高度期望为 $O(\log{n})$
• 插入、删除、查询、前驱后继、排名等操作期望均为 $O(\log{n})$

核心思想就是通过旋转或重构维护 BST, 尽量保持平衡，避免退化成链。

平衡树有很多，大致可以分为两类：

1. 通过旋转维持平衡

• AVL 树 最早的平衡树，左右子树高度差小于等于1，频繁旋转保持平衡，算法竞赛中很少手写，用于原理理解。

• 红黑树 工业届常用，set/map 就是使用红黑树。通过旋转维持“从根到叶子的最长路径小于最短路径的二倍” ，旋转少、常数小、性能稳定，很多库都采用这种方式，但由于代码量，竞赛中不手写。

• 伸展树 Splay Tree

  每次访问把节点旋转(双旋)到根，利用局部性原理加速，多次操作期望树期望高度为 $O(\log{n})$。Splay 是实现 LCT(动态树) 基础，具有代码短、更能强的优点，但存在常数略大、可能被卡常、无法可持久化等缺点。

2. 通过重构维持平衡

• 替罪羊树 当达到失衡阈值重构这个子树，思想简单、实现容易。

• 无旋 Treap(FHQ-Treap)

  被称为竞赛手写王者，只用 分裂+合并 就能完成所有操作。无旋转、逻辑清晰、容易调试等优点，支持区间翻转、区间赋值、可持久化等操作。

  ---

  Treap