解决问题的算法

如果一棵二叉查找树的根节点到任意一个叶子节点的路径长度都基本相等，那么这棵树就是二叉平衡查找树。定义depth(Li)为从根节点到叶子节点Li的路径长度。如果一棵二叉树具有良好的平衡度，那么对任意两个叶子节点L1和L2来说，depth(L2)和depth(L1)的差的绝对值，即|depth(L2)-depth(L1)|≤1；同样对于任何一个叶子节点Li来说，depth(Li)≤log(n)。Gary翻阅了他的算法书籍，决定对Graham的代码进行修改，用更加平衡的红黑树记录内存的分配。红黑树（Cormen,2001）是一个平衡二叉树的高效实现。在红黑树中，给定两个叶子节点L1和L2，depth(L2)/depth(L1)≤2；同样对任意叶子节点Li来说，depth(Li)≤2*log2(n+1)。也就是说，一棵红黑树是大致地平衡的，这确保了在红黑树中，不存在一条路径，其长度是另外一条路径的两倍。

Gary花了几个小时进行了修改和测试。当他完成之后，他将结果演示给Graham看。他们使用新的库，重新运行了上面的三个程序。程序A和程序C仅仅只是比程序B多花了几毫秒而已。性能很明显地大幅改善了，反映在速度提高了近5000倍。这样的性能改善是想当然的，你可以看到平均访问节点的数目从500 000个降到了20个。事实上，这是数量级的降低：你也许期望能够加速25 000倍，但是对树进行平衡的操作开销降低了部分性能。尽管如此，性能的改善仍然是惊人的，Graham的内存泄漏检测程序（包括Gary的修改）将再下一个产品中发布。