12.7 配对堆我们考查的最后一个数据结构是配对堆( pairing heap)。对配对堆的分析仍然未解决，不过，当需要decreaseKey操作的时候，它似...

12.5 treap树最后--种二叉查找树可能是最简单的一种，叫做treap树。它像跳跃表-样使用随机数并且对任意的输人都能给出O( log N)期望时间...

12.4 AA树因为大量可能的旋转，红黑树的编程相当复杂，特别是删除操作。虽在一定程度上确定性跳跃表的编程代码要少一些，但仍然是相当复杂...

12.3 确定性跳跃表用于红黑树的-一-些想法可以应用到跳跃表以保证对数最坏情形操作。在这一节，我们描述所得到数据结构的最简单的实现方法...

12.2 红黑树历史上AVL树流行的另一变种是红黑树( red black tree)。对红黑树的操作在最坏情形下花费O(log N)时间，而且我们将看到，(...

第12章 高级数据结构及其实现本章讨论7种重点在于实用性的数据结构。首先考查第4章讨论过的AVL树的一些变种，包括优化的伸展树、红黑树、...

123

11.4 斐波那契堆在9.3.2节我们指出如何使用优先队列来改进Djlstra最短路径算法粗略的运行时间O(I VI)。重要的观察结果是运行时间被|E|次d...

11.3 斜堆二项队列的分析可以算是摊还分析一个容易的实例。现在我们来考察斜堆。像许多的例子一样，一旦找到正确的位势函数，分析起来就容...

第11章 摊还分析在这一章，我们将对在第4章和第6章出现的几种高级数据结构的运行时间进行分析，特别是我们将考虑任意顺序的M次操作的最坏...