平衡二叉搜索树

由前文可知，二叉搜索树的所有操作的时间复杂度为 \(O(h)\)，\(h\) 为树的高度，然而，其平均高度为 \(O(\sqrt n)\)，这并不能令人满意，因此我们要试图降低树的高度。

节点数目固定时，兄弟子树高度越接近（平衡），全树也将倾向于更低。

由 \(n\) 个节点组成的二叉树，高度不低于 \(\lfloor log_2 n \rfloor\) —— 恰为 \(\lfloor log_2 n \rfloor\) 时，称作理想平衡。

完全二叉树、满二叉树都是理想平衡的。

理想平衡出现概率极低、维护成本过高，故须适当地放松标准。

高度渐进地不超过 \(O(logn)\)，即可称作适度平衡。适度平衡的 BST，称作平衡二叉搜索树（Balanced Binary Search Tree，BBST）。

也就是说，BBST 是 BST 的一个子集，如果经过某些操作（一般为动态操作）之后，它不再保持适度平衡，就会游离这个子集之外，此时，我们就需要一整套方法将它重新拉回这个子集之内，这叫做重平衡（rebalance）。不同的 BBST（比如 AVL 树、伸展树、红黑树等），它们的适度平衡的标准不一样，重平衡方法也不一样。无论哪种重平衡方法，本质上来说都是一系列的等价变换。

拓扑结构不尽相同，但中序遍历序列却相同的任何一对 BST，称作相互等价的 BST。等价的 BST 之间，在拓扑结构上虽然不尽相同，但也有其独特的规律：

• 上下可变：联接关系不尽相同，承袭关系可能颠倒。即等价的 BST 在垂直方向有一定的自由度。
• 左右不乱：中序遍历序列完全一致，全局单调非降

实际上，任何一对等价 BST 之间的相互转换，都可以视作是由一系列的基本操作串接而成，而这种基本的变换无非两类，彼此对称，即 zig（顺时针旋转）和 zag（逆时针旋转）。