算法导论第十四章 数据结构的扩张

一、概要

　　我们在教科书上所学的所有数据结构都是最常规、最精简的数据结构，即便如此，基本上所有能遇上的问题都能用这些数据结构来解决。但是有一些特殊的问题，需要对现有的数据结构进行些许改造才能应付，这种改造是很细微的，且改造所添加的信息必须能被该数据结构上的常规操作所更新和维护。比如在链表上添加一个数据域来记录结点的位置、在一棵二叉搜索树上添加一个指针域来记录结点的后继指针，等等。

　　本章介绍两种通过扩张红黑树构造出的数据结构，一种是动态顺序统计树；另一种是区间树。然后介绍了如何扩张现有数据结构的一个通用方法。本章不想花太多时间和言语来描述，思想很简单，告诉我们怎么样根据实际问题，扩张现有数据结构，而不是自己去实现一种新的数据结构。

二、扩张的两种数据结构

　　简单总结下通过红黑树扩张的两种数据结构：动态顺序统计树和区间树。

　　动态顺序统计树在原红黑树的基础上增加一个数据域 x.size，其等于 x 左右孩子的节点数。通过这一小小的改造，就可以利用红黑树解第9章介绍的顺序统计，其所有操作的时间复杂度降到O(lgn)。对于改造的动态顺序统计数，有两个比较重要的函数：一就是求第 k 小的数:Select(x, k); 二是求节点 x 的排名：Rank(T, x)，这两个操作都能在O(lgn)内完成。需要注意的是，对新添加的属性 x.size，原有数据结构的操作都要对 size属性进行维护，如添加一个元素的时候，相应树枝上的元素的size属性也应该做更新，删除亦是。如下是一棵动态顺序统计树：

　　区间树则是对红黑树扩张以便支持由区间构成的动态集合操作，红黑树用到的关键字值是区间树的区间左端点值。以下是一个区间树及其所表示的区间：

区间树的节点还扩展了一个域max，就是以该节点为根的子树的所有区间元素的右端点的最大值。该域很容易在O(1)的时间内维护，那就是左子结点的max、右子结点的max和自身区间的右端点三者的最大值。

　　区间树提供一些与区间有关的操作，比如判断一个区间有没有与区间树中的任何一个区间元素有交集，判断一个点是否落在区间树中的任意一个区间元素中。

关于如何扩张数据结构的方法：

　　书上介绍了四个扩张的步骤：

1）选择一种基础数据结构

2）确定基础数据结构中需要维护的附加信息。

3）检验基础数据结构上的基本修改操作能否维护附加信息。

4）设计一些新操作