邵阳高端网站建设/湖南网站推广优化

编程中常常会遇到已有的数据结构无法解决问题，这时不要急着创建新的数据结构，可以在已有数据结构的基础上添加新的字段。本节在红黑树这一基础数据结构上进行扩展，得出两个重要的应用—动态顺序统计和区间树。

一、动态顺序统计

       一种支持一般动态集合上顺序统计操作的数据结构。通过这种数据结构，可以快速找到一个集合中的第i小的数，（select）或给出一个指定元素在集合的全序中的位置。（rank）

【思想】添加新项：在红黑树的结点上记录下该结点的子树个数。size[x] = size[left[x]] + size[right[x]] +1。 若结点为空，则为0。

此外当你对该扩展的数据结构进行插入和删除操作时，需随时更新子树的大小，与插入和删除操作同步进行，但是需要重新使其回到平衡。主要在于case2和case3这两种情况的旋转。<可以与算法系列笔记4>红黑树的插入代码进行对比，看修改情况。

代码：

返回第i 排名的元素os_select(i)
 

BSTNode* OSRBTree::os_select(BSTNode *p, const int &ith){if(p == NULL) return p;int k = 1;if(p->left != NULL){k = p->left->size + 1;           // 当前该结点所对应的rank}if(ith == k) return p;if(ith < k) return os_select(p->left, ith);else return os_select(p->right, i