第12章 高级数据结构和实现

在这一章里，我们重点讨论6个有关实用性的数据结构。

首先，我们讨论AVL树的替代数据结构，包括优化版本的伸展树、红黑树、treap，以及用于在大文本中匹配某种模式的后缀树等。

然后，我们讨论用于多维数据的数据结构k-d树，其中每个数据项都有多个搜索键。

最后，我们讨论配对堆，这种数据结构似乎是Fibonacci堆的最使用的替代数据结构。

注意，这一章可能会重复如下内容：

• 非递归、自顶向下的搜多树实现。
• 利用哨兵节点的详细的、优化版本的实现。