一、平衡树概述
- 接下来几篇文章将会介绍平衡树结构：
- 树的高度为O(
)
- 其中有两种平衡二叉树结构：AVL和红黑树。它们适合内部存储的引用
- 一个树结构：B-树，它的度大于2。其适合外部存储的引用（例如，存储在磁盘上的大型字典）
- 上面这些平衡树结构可以在最坏情况下用时O(logn)实现字典操作和按名次的操作。当用索引平衡树表示线性表时，操作get、insert、erase的用时为O(logn)
- 分裂树：高度为O(n)，而且在分裂树上的单个字典操作用时为O(n)，但是每一个含有u个操作票的序列，其用时仅为O(ulogu)
- 树的高度为O(
二、各种字典结构的渐近时间新能比较
- 下面用到的函数都是Θ的
三、总结
- STL的map和multimap使用的是红黑树结构，以保证查找、插入、删除操作都具有对数级的时间性能
- 关于实际的运行时间性能，AVL和红黑树是相似的；相比之下，分裂树在实施一个含有u个操作的序列时，用时比较少。另外，分裂树的实现方法比较简单
-
AVL和红黑树都是用“旋转”来保持平衡：
- AVL树对每个插入操作最多需要一次旋转，对每个删除操作最多需要O(logn)次旋转
- 红黑树对每次插入和删除操作，都只需要一次旋转
- 这种差别在大多数应用中无关紧要，因为一次旋转仅需用时Θ(1)。但是对那些需要平衡的应用，一次旋转不能在常量时间内完成，这种差别就非常重要了。例如，平衡优先搜索树（McCreight）就是这样一种应用。平衡优先搜索树用于描述具有二维关键字的元素，此时，每个关键字是一数对（x,y）。它是关于y的优先队列，同时又是关于x的搜索树。在这样的树中，每一次旋转都需要耗时O(logn)。如果用红黑树来描述平衡优先搜索树，则因为每一次插入或杀出仅需要一次旋转，所欲插入或删除操作的总时间仍然为O(logn)。当使用AVL树时，则删除操作的时间将变为O(
)
- 虽然对比较小的可以在内存中处理的字典，AVL树、红黑树和分裂树均能提供比较高的性能，但是对大型字典，它们就不适合了。当字典存储在磁盘上时，需要使用度数更大、高度更小的搜索树，例如B-树