1. 平衡树¶
二叉搜索树 作为一种实用查找结构有一个严重的缺陷。 那就是它很容易变得不平衡，致使某些结点位于树的深处。 事实上，一棵有 \(n\) 个结点的 BST 深度可能达到 \(n\)， 这使得它在最坏情况下的查找速度并不比链表快。 如果我们能以某种方式保持树的平衡，那么查找代价就只需 \(\Theta(\log n)\)， 这是一个巨大的改进。
解决这个问题的方法之一是采用另一种查找树结构，而不是使用 BST。 这种替代树结构的一个例子是 2-3 树 或 B-树。 但另一种选择是以某种方式修改 BST 的访问函数，以保证树性能良好。 这是一个很有吸引力的思路，而且该思路对堆很有效——堆的访问函数使堆保持 完全二叉树的形态。 遗憾的是，堆要保持其平衡形态，代价是对结点与其孩子之间相对值的约束较弱， 这使它成为一种糟糕的查找结构。 而且要求 BST 始终保持完全二叉树的形态，在更新时需要对树进行过度的修改， 正如我们在这个例子中看到的那样。
Figure 26.1.1: 插入后试图重新平衡 BST 的代价可能很高。 (a) 一棵有六个结点、呈完全二叉树形态的 BST。 (b) 将值为 1 的结点插入到 (a) 中的 BST。 要保持完全二叉树形态和 BST 性质，需要对树进行大规模重组。¶
如果我们愿意放宽平衡要求，就可以设计出替代的更新例程， 它们在更新代价和最终树结构的平衡性两方面都表现良好。 AVL 树 就是按这种方式工作的： 它对 BST 的插入和删除例程加以修改，以确保每个结点的左、右子树的深度之差至多为 1。
改进 BST 性能的另一条途径是：不要求树始终保持平衡， 而是在每次访问 BST 时花费一些精力使其更加平衡。 这有点类似于 UNION/FIND 算法 所使用的路径压缩思想。 这种折衷方案的一个例子叫做 伸展树。
红黑树 也是一种二叉树，但它使用不同的平衡机制。
