一、概念1.动态顺序统计
动态顺序统计是指，在一个动态的无序的集合中，任意的顺序统计量都可以在O(lgn)时间内确定。
2.基础数组结构
红黑树，每个树结点的域包括：key[x]，color[x]，left[x]，right[x]
3.附加信息
size[x]：以结点x为根的子树的内部结点（包括x）数，即子树的大小。
如果定义哨兵nil，则size[nil[T]]为0
size[x] = size[left[x]] + size[right[x]] + 1
4.对信息的维护
（1）插入操作：
第一个阶段，即从根开始，沿树下降，将新结点插入为某个已有结点的孩子，这一阶段的维护方法是对路径上每个结点的size都+1，时间是O(lgn)
第二个阶段，即沿树上升，做一些颜色修改和旋转以保持红黑性质，例如LEFT-ROTATE(T, x)，维护方法是size[y]<-size[x]，size[x]<-size[left[x]] + size[right[x]] + 1，由于至多旋转两次，时间是O(1)
（2）删除操作：
第一阶段，即对查找树进行操作，维护方法是对路径上每个结点的size都-1，时间是O(lgn)
第二阶段到多做三次旋转，，维护方式与上面相同，时间是O(1)
5.设计新的操作
OS-SELECT(x, i)：找出顺序统计树T中的第i小关键字，时间为O(lgn)
OS-RANK(T, x)：给定指向一顺序统计树T中结点x的指针，返回对T进行中序遍历后得到 的线性序中x的位置，时间为O(lgn)
二、代码1.Os_Tree.h
#include <iostream>using namespace std;#define BLACK 0#define RED 1//顺序统计量树结点结构struct node{/*红黑树的域*/int key;bool color;node *p;node *left;node *right;/*附加信息*/int size;//以结点x为根的子树的内部结点的个数，x->key=x->left->key+x->right->key+1/*构造函数*/node(node *init, int k):left(init),right(init),p(init),key(k),color(BLACK),size(1){} };//顺序统计量树结构class Os_Tree{public:node *root;node *nil;//哨兵/*构造函数*/Os_Tree(){nil = new node(NULL, -1);root = nil;nil->size = 0;}; /*动态顺序统计相关操作*/node *Os_Select(node *x, int i);int Os_Rank(node *x);/*红黑树的相关操作*/void Left_Rotate(node *x);//左旋void Right_Rotate(node *x);//右旋void Os_Insert_Fixup(node *z);//插入调整void Os_Insert(node *z);//插入void Os_Delete_Fixup(node *x);//删除调整node *Os_Delete(node *z);//删除void Print();//输出void Print(node *x);//输出node *Os_Search(node *x, int k);//在x的子树中查找关键字为k的结点node *Tree_Successor(node *x);//求后继node *Tree_Minimum(node *x);//求关键字最小的点};//左旋，令y = x->right, 左旋是以x和y之间的链为支轴进行旋转//涉及到的结点包括：x,y,y->left，令node={p,l,r},具体变化如下：//x={x->p,x->left,y}变为{y,x->left,y->left}//y={x,y->left,y->right}变为{x->p,x,y->right}//y->left={y,y->left->left,y->left->right}变为{x,y->left->left,y->left->right}void Os_Tree::Left_Rotate(node *x){//令y = x->rightnode *y = x->right;//按照上面的方式修改三个结点的指针，注意修改指针的顺序x->right = y->left;if(y->left != nil)y->left->p = x;y->p = x->p;if(x->p == nil)//特殊情况：x是根结点root = y;else if(x == x->p->left)x->p->left = y;else x->p->right = y;y->left = x;x->p = y;//对附加信息的维护y->size = x->size;x->size = x->left->size + x->right->size + 1;}//右旋，令y = x->left, 左旋是以x和y之间的链为支轴进行旋转//旋转过程与上文类似void Os_Tree::Right_Rotate(node *x){node *y = x->left;x->left = y->right;if(y->right != nil)y->right->p = x;y->p = x->p;if(x->p == nil)root = y;else if(x == x->p->right)x->p->right = y;else x->p->left = y;y->right = x;x->p = y;//对附加信息的维护y->size = x->size;x->size = x->left->size + x->right->size + 1;}//红黑树调整void Os_Tree::Os_Insert_Fixup(node *z){node *y;//唯一需要调整的情况，就是违反性质2的时候，如果不违反性质2，调整结束while(z->p->color == RED){//p[z]是左孩子时，有三种情况if(z->p == z->p->p->left){//令y是z的叔结点y = z->p->p->right;//第一种情况，z的叔叔y是红色的if(y->color == RED){//将p[z]和y都着为黑色以解决z和p[z]都是红色的问题z->p->color = BLACK;y->color = BLACK;//将p[p[z]]着为红色以保持性质5z->p->p->color = RED;//把p[p[z]]当作新增的结点z来重复while循环z = z->p->p;}else{//第二种情况：z的叔叔是黑色的，且z是右孩子if(z == z->p->right){//对p[z]左旋，转为第三种情况z = z->p;Left_Rotate(z);}//第三种情况：z的叔叔是黑色的，且z是左孩子//交换p[z]和p[p[z]]的颜色，并右旋z->p->color = BLACK;z->p->p->color = RED;Right_Rotate(z->p->p);}}//p[z]是右孩子时，有三种情况，与上面类似else if(z->p == z->p->p->right){y = z->p->p->left;if(y->color == RED){z->p->color = BLACK;y->color = BLACK;z->p->p->color = RED;z = z->p->p;}else{if(z == z->p->left){z = z->p;Right_Rotate(z);}z->p->color = BLACK;z->p->p->color = RED;Left_Rotate(z->p->p);}}}//根结点置为黑色root->color = BLACK;}//插入一个结点void Os_Tree::Os_Insert(node *z){node *y = nil, *x = root;//找到应该插入的位置，与二叉查找树的插入相同while(x != nil){x->size++;y = x;if(z->key < x->key)x = x->left;elsex = x->right;}z->p = y;if(y == nil)root = z;else if(z->key < y->key)y->left = z;elsey->right = z;z->left = nil;z->right = nil;//将新插入的结点转为红色z->color = RED;//从新插入的结点开始，向上调整Os_Insert_Fixup(z);}//对树进行调整，x指向一个红黑结点，调整的过程是将额外的黑色沿树上移void Os_Tree::Os_Delete_Fixup(node *x){node *w;//如果这个额外的黑色在一个根结点或一个红结点上，结点会吸收额外的黑色，成为一个黑色的结点while(x != root && x->color == BLACK){//若x是其父的左结点（右结点的情况相对应）if(x == x->p->left){//令w为x的兄弟，根据w的不同，分为三种情况来处理//执行删除操作前x肯定是没有兄弟的，执行删除操作后x肯定是有兄弟的w = x->p->right;//第一种情况：w是红色的if(w->color == RED){//改变w和p[x]的颜色w->color = BLACK;x->p->color = RED;//对p[x]进行一次左旋Left_Rotate(x->p);//令w为x的新兄弟w = x->p->right;//转为2.3.4三种情况之一}//第二情况：w为黑色，w的两个孩子也都是黑色if(w->left->color == BLACK && w->right->color == BLACK){//去掉w和x的黑色//w只有一层黑色，去掉变为红色，x有多余的一层黑色，去掉后恢复原来颜色w->color = RED;//在p[x]上补一层黑色x = x->p;//现在新x上有个额外的黑色，转入for循环继续处理}//第三种情况，w是黑色的,w->left是红色的,w->right是黑色的else{if(w->right->color == BLACK){//改变w和left[x]的颜色w->left->color = BLACK;w->color = RED;//对w进行一次右旋Right_Rotate(w);//令w为x的新兄弟w = x->p->right;//此时转变为第四种情况}//第四种情况：w是黑色的,w->left是黑色的,w->right是红色的//修改w和p[x]的颜色w->color =x->p->color;x->p->color = BLACK;w->right->color = BLACK;//对p[x]进行一次左旋Left_Rotate(x->p);//此时调整已经结束，将x置为根结点是为了结束循环x = root;}}//若x是其父的左结点（右结点的情况相对应）else if(x == x->p->right){//令w为x的兄弟，根据w的不同，分为三种情况来处理//执行删除操作前x肯定是没有兄弟的，执行删除操作后x肯定是有兄弟的w = x->p->left;//第一种情况：w是红色的if(w->color == RED){//改变w和p[x]的颜色w->color = BLACK;x->p->color = RED;//对p[x]进行一次左旋Right_Rotate(x->p);//令w为x的新兄弟w = x->p->left;//转为2.3.4三种情况之一}//第二情况：w为黑色，w的两个孩子也都是黑色if(w->right->color == BLACK && w->left->color == BLACK){//去掉w和x的黑色//w只有一层黑色，去掉变为红色，x有多余的一层黑色，去掉后恢复原来颜色w->color = RED;//在p[x]上补一层黑色x = x->p;//现在新x上有个额外的黑色，转入for循环继续处理}//第三种情况，w是黑色的,w->right是红色的,w->left是黑色的else{if(w->left->color == BLACK){//改变w和right[x]的颜色w->right->color = BLACK;w->color = RED;//对w进行一次右旋Left_Rotate(w);//令w为x的新兄弟w = x->p->left;//此时转变为第四种情况}//第四种情况：w是黑色的,w->right是黑色的,w->left是红色的//修改w和p[x]的颜色w->color =x->p->color;x->p->color = BLACK;w->left->color = BLACK;//对p[x]进行一次左旋Right_Rotate(x->p);//此时调整已经结束，将x置为根结点是为了结束循环x = root;}}}//吸收了额外的黑色x->color = BLACK;}//找最小值 node *Os_Tree::Tree_Minimum(node *x) {//只要有比当前结点小的结点while(x->left != nil)x = x->left;return x; } //查找中序遍历下x结点的后继，后继是大于key[x]的最小的结点 node *Os_Tree::Tree_Successor(node *x) {//如果有右孩子if(x->right != nil)//右子树中的最小值return Tree_Minimum(x->right);//如果x的右子树为空且x有后继y，那么y是x的最低祖先结点，且y的左儿子也是node *y = x->p;while(y != NULL && x == y->right){x = y;y = y->p;}return y; } //递归地查询二叉查找树 node *Os_Tree::Os_Search(node *x, int k) {//找到叶子结点了还没找到，或当前结点是所查找的结点if(x->key == -1 || k == x->key)return x;//所查找的结点位于当前结点的左子树if(k < x->key)return Os_Search(x->left, k);//所查找的结点位于当前结点的左子树elsereturn Os_Search(x->right, k); } //红黑树的删除node *Os_Tree::Os_Delete(node *z){//找到结点的位置并删除，这一部分与二叉查找树的删除相同node *x, *y;if(z->left == nil || z->right == nil)y = z;else y = Tree_Successor(z);node *p = y->p;while(p != nil){p->size–;p = p->p;}if(y->left != nil)x = y->left;else x = y->right;x->p = y->p;if(y->p == nil)root = x;else if(y == y->p->left)y->p->left = x;elsey->p->right = x;if(y != z)z->key = y->key;//如果被删除的结点是黑色的，则需要调整if(y->color == BLACK)Os_Delete_Fixup(x);return y;}void Os_Tree::Print(node *x){if(x->key == -1)return;Print(x->left);cout<<x->key<<‘ ‘<<x->color<<endl;Print(x->right);}void Os_Tree::Print(){Print(root);cout<<endl;}//查找以x为根结点的树中第i大的结点node *Os_Tree::Os_Select(node *x, int i){//令x左子树中点的个数为r-1,int r = x->left->size +1;//那么x是x树中第r大的结点if(r == i)return x;//第i大的元素在x->left中else if(i < r)return Os_Select(x->left, i);//第i大的元素在x->right中elsereturn Os_Select(x->right, i – r);}//计算树T中进行顺序遍历后得到的线性序中x的位置int Os_Tree::Os_Rank(node *x){//置r为以x为根的子树中key[x]的秩int r = x->left->size + 1;node *y = x;while(y != root){//若y是p[y]的右孩子，p[y]和p[y]左子树中所有结点前于xif(y == y->p->right)r = r + y->p->left->size + 1;y = y->p;}return r;}2.main.cpp
#include <iostream>#include "Os_Tree.h"using namespace std;int main(){char ch;int x;//生成一棵顺序统计树Os_Tree *T = new Os_Tree;while(1){cin>>ch;switch(ch){//插入一个元素case ‘I’:{cin>>x;node *z = new node(T->nil, x);T->Os_Insert(z);break;}//删除一个元素case ‘D’:{cin>>x;node *z = T->Os_Search(T->root, x);if(z == NULL)cout<<"not exist"<<endl;elseT->Os_Delete(z);break;}//计算第x小关键字case ‘S’:{cin>>x;node *z = T->Os_Select(T->root, x);if(z == NULL)cout<<"not exist"<<endl;elsecout<<z->key<<endl;break;}//计算x的位置case ‘R’:{cin>>x;node *z = T->Os_Search(T->root, x);if(z == NULL)cout<<"not exist"<<endl;elsecout<<T->Os_Rank(z)<<endl;break;}case ‘P’:T->Print();break;default:break;}}return 0;}三、练习因为有了梦想，我们才能拥有奋斗的目标，
