动态顺序统计
1.将红黑树扩展为顺序统计树，可以在 O(lgn) 时间内确定任何的顺序统计量
2.扩展方法为红黑树的结点增加一个新属性 size，表示以该结点为根的子树包含的结点数
3.查找具有给定秩的元素（如第 i 小的元素）
r = x.left.size + 1 ，比较 r 和 i 决定是递归还是结束
4.确定一个元素的秩
思路是从给定的结点上升直至根结点，如果过程中上升的指针是右孩子，总的秩就要加上左孩子的 size + 1，如果是左孩子就不用加
5.对子树规模的维护
顺序统计树在插入和删除操作时，只要对红黑树的相应操作简单修改即可。分别的，第一阶段的升级操作修改路径上每个结点的 size，第二阶段的旋转操作中更新被旋转结点的 size，总共的性能消耗为 O(lgn)
如何扩张数据结构
这里讲的是扩张数据结构的方法论
扩张数据结构的 4 个步骤：
1.选择一种基础数据结构
2.确定基础数据结构中要维护的附加信息
3.检验基础数据结构上的基本修改操作能否维护附加信息
4.设计一些新操作
可以证明，已红黑树为基础数据结构时，某些类型的附加信息可以在插入和删除操作时顺便完成，且不影响其渐进性能（即可以在 O(lgn) 时间内完成）
区间树
本节利用上一节的方法论将红黑树扩展成区间树，每个节点都包含一个区间，以区间的左界作为红黑树的 key
1.增加了附加信息区间的右界的 max 值
2.证明维护这个附加信息不影响插入删除的渐进性能
3.设计了新的操作查找：在 O(lgn) 时间内完成从区间树中查找与给定区间重叠的区间，并给出了证明
网友评论