问题：通过为结点增加指针的方式，试说明如何在扩张的顺序统计树上，支持每一动态集合查询操作MINIMUM,MAXIMUM,SUCCESSOR和PREDECESSOR在最坏时间O(1)内完成。顺序统计树上的其他操作的渐近性能不应受影响。
代码如下：
//本程序在原有的红黑树基础上增加了子树结点个数，前驱后继结点以及最大小结点属性。
#include <iostream>
#include <time.h>
using namespace std;
#define BLACK 0
#define RED 1
#define Nil -1
#define n 20 //更改顺序统计树内的结点数。
#define LEN sizeof(struct OS_Tree)
struct OS_Tree
{
struct OS_Tree*right,*left;
struct OS_Tree*parent;
struct OS_Tree*next,*prev;
struct OS_Tree* Max,*Min;
int key,color,size;//size表示子树的结点数。
};
struct OS_Tree*root=NULL,*nil=NULL,*head=NULL,*tail=NULL;
void LEFT_ROTATE(struct OS_Tree*x)
{//左旋转：分三个步骤①②③来叙述旋转代码的。
struct OS_Tree*y=x->right;//设置y结点。
if(y->left!=nil)x->Max=y->left->Max;//对附加信息的维护
else x->Max=x;
y->Min=x->Min;
x->right=y->left;//本行代码以及下面的if结构表达的是“y的左孩子成为x的右孩子”。①
if(y->left!=nil)
{
y->left->parent=x;
}
y->parent=x->parent;//本行代码以及下面的if-else结构表达的过程是“y成为该子树新的根”。②
if(x->parent==nil)
{
root=y;
}
else if(x==x->parent->left)
{
x->parent->left=y;
}
else x->parent->right=y;
y->left=x;//本行代码以及下面一行都表达了“x成为y的左孩子”。③
x->parent=y;
y->size = x->size; //对附加信息的维护
x->size = x->left->size + x->right->size +1;
}
void RIGHT_ROTATE(struct OS_Tree*x)
{//右旋转：分三个步骤①②③来叙述旋转代码的。
struct OS_Tree*y=x->left;//设置y结点。
if(y->right!=nil) x->Min=y->right->Min;//对附加信息的维护
else x->Min=x;
y->Max=x->Max;
x->left=y->right;//本行代码以及下面的if结构表达的是“y的左孩子成为x的右孩子”。①
if(y->right!=nil)
{
y->right->parent=x;
}
y->parent=x->parent;//本行代码以及下面的if-else结构表达的过程是“y成为该子树新的根”。②
if(x->parent==nil)
{
root=y;
}
else if(x==x->parent->right)
{
x->parent->right=y;
}
else x->parent->left=y;
y->right=x;//本行代码以及下面一行都表达了“x成为y的左孩子”。③
x->parent=y;
y->size = x->size; //对附加信息的维护
x->size = x->left->size + x->right->size +1;
}
void RB_INSERT_FIXUP(struct OS_Tree*z)
{
while (z->parent->color==RED)
{
if (z->parent==z->parent->parent->left)
{
struct OS_Tree*y=z->parent->parent->right;//叔结点
if (y->color==RED)//情况一：叔结点为红色
{//给p1,y,p2着色以保持性质5。并且解决了z的父结点和z都是红色结点问题
z->parent->color=BLACK;
y->color=BLACK;
z->parent->parent->color=RED;
z=z->parent->parent;//把z的祖父结点当成新结点z进入下一次循环
}
else
{
if (z==z->parent->right)//情况二：检查z是否是一个右孩子且叔结点为黑色，前提是p1结点不是叶子结点
{//使用一个左旋让情况2转变为情况3
z=z->parent;
LEFT_ROTATE(z);//由于进入if语句后可知旋转结点不可能是叶子结点，这样就不用判断z是否是叶子结点了。
}
z->parent->color=BLACK;//情况三：是z是一个左孩子且叔结点为黑色，改变z的父和祖父结点颜色并做一次右旋，以保持性质5
z->parent->parent->color=RED;
RIGHT_ROTATE(z->parent->parent);//由于p2可能是叶子结点，所以最好还是用一个if判断
}
}
else//下面else分支类似于上面,注意到else分支的情况2和情况3所做旋转正好是if分支情况的逆。
{
struct OS_Tree*y=z->parent->parent->left;
if (y->color==RED)
{
z->parent->color=BLACK;
y->color=BLACK;
z->parent->parent->color=RED;
z=z->parent->parent;
}
else
{
if (z==z->parent->left)
{
z=z->parent;
RIGHT_ROTATE(z);
}
z->parent->color=BLACK;
z->parent->parent->color=RED;
LEFT_ROTATE(z->parent->parent);
}
}
}
root->color=BLACK;//最后给根结点着为黑色。
}
void RB_INSERT(struct OS_Tree*z)
{
struct OS_Tree*y=nil;
struct OS_Tree*x=root;
while (x!=nil)
{
x->size++;
y=x;
if (z->key<x->key)
{
x=x->left;
}
else x=x->right;
}
z->parent=y;
if (y==nil)
{
tail=head=root=z;
root->next=nil;
root->prev=nil;
}
else if(z->key<y->key)
{
y->left=z;
z->next=y;
y->prev=z;
while (y)
{
y->Min=z;
if (y->parent==nil||y->parent->right==y)
{
break;
}
y=y->parent;
}
if (y->parent==nil)
{
head=z;
z->prev=nil;
}
else if (y->parent->right==y)
{
y->parent->next=z;
z->prev=y->parent;
}
}
else
{
y->right=z;
z->prev=y;
y->next=z;
while (y)
{
y->Max=z;
if (y->parent==nil||y->parent->left==y)
{
break;
}
y=y->parent;
}
if (y->parent==nil)
{
tail=z;
z->next=nil;
}
else if (y->parent->left==y)
{
y->parent->prev=z;
z->next=y->parent;
}
}
z->left=nil;//给插入结点左右孩子赋值为空。
z->right=nil;
z->color=RED;//给插入结点着为红色。
z->Max=z->Min=z;
z->size=1;
z->left->size=0;
z->right->size=0;
RB_INSERT_FIXUP(z);
//InOderTraverse(root);
}
void RB_TRANSPLANT(struct OS_Tree*u,struct OS_Tree*v)
{
if (u->parent==nil)
root=v;
else if(u==u->parent->left)
u->parent->left=v;
else u->parent->right=v;
v->parent=u->parent;
}
struct OS_Tree*TREE_MINIMUM(struct OS_Tree*x)//求二叉查找树当前结点最小值
{
return x->Min;
}
struct OS_Tree*TREE_MAXINUM(struct OS_Tree*x)//求二叉查找树当前结点最大值
{
return x->Max;
}
struct OS_Tree*TREE_PREDECESSOR(struct OS_Tree*x)//查找二叉查找树的前驱
{
return x->prev;
}
struct OS_Tree*TREE_SUCCESSOR(struct OS_Tree*x)//查找二叉查找树的后继
{
return x->next;
}
//非递归版本的二叉查找树查找函数
struct OS_Tree*ITERATIVE_TREE_SEARCH(struct OS_Tree*x,int k)
{
while (x!=nil&&k!=x->key)
{
if (k<x->key)
{
x=x->left;
}
else x=x->right;
}
return x;
}
void RB_DELETE_FIXUP(struct OS_Tree*x)
{
struct OS_Tree*w=NULL;//w是x的兄弟结点
while (x!=root&&x->color==BLACK)//如果x是黑色并且不是根结点，才进行循环。
{//x是一个具有双重颜色的结点，调整的目的是把x的黑色属性向上移动。
if (x==x->parent->left)
{
w=x->parent->right;
if (w->color==RED)//情况一：x的兄弟结点w是红色的。
{//改变w和x.p的颜色+一次旋转使其变为情况二，三，四。
w->color=BLACK;
x->parent->color=RED;
LEFT_ROTATE(x->parent);
w=x->parent->right;
}
if (w->left->color==BLACK&&w->right->color==BLACK)//情况二：x的兄弟结点w是黑色的，而且w的两个子节点都是黑色。
{
w->color=RED;//从x和w上去掉一重黑色。x还是黑色，而w变为红色。
x=x->parent;//x结点向上移动成为新的待调整结点。
}
else
{
if (w->right->color==BLACK)//情况三：x的兄弟结点w是黑色的，w的左孩子是红色的，w的右孩子是黑色的。
{//交换w和w.left的颜色+旋转使其转变为情况四。
w->left->color=BLACK;
w->color=RED;
RIGHT_ROTATE(w);
w=x->parent->right;
}
w->color=x->parent->color;//以下是情况四：x的兄弟结点w是黑色的，且w的右孩子是红色的。
x->parent->color=BLACK;//置x.p和w.right为黑色+旋转使其去掉x的额外黑色。
w->right->color=BLACK;
LEFT_ROTATE(x->parent);
x=root;//x成为根结点，结束循环。
}
}
else//以下和上面的if分支类似，不做累述。
{
w=x->parent->left;
if (w->color==RED)
{
w->color=BLACK;
x->parent->color=RED;
RIGHT_ROTATE(x->parent);
w=x->parent->left;
}
if (w->left->color==BLACK&&w->right->color==BLACK)
{
w->color=RED;
x=x->parent;
}
else
{
if (w->left->color==BLACK)
{
w->right->color=BLACK;
w->color=RED;
LEFT_ROTATE(w);
w=x->parent->left;
}
w->color=x->parent->color;
x->parent->color=BLACK;
w->left->color=BLACK;
RIGHT_ROTATE(x->parent);
x=root;
}
}
}x->color=BLACK;
}
void RB_DELETE(struct OS_Tree*z)
{
struct OS_Tree*y=z,*x;//y为待删除或待移动结点
int y_original_color=y->color;//保存y的原始颜色，为做最后的调整做准备。
struct OS_Tree*k=z->parent,*p=z->parent,*t=z->parent;
if (z->left==nil)
{
while (t!=nil)
{
t->size--;
t=t->parent;
}
x=z->right;//x指向y的唯一子结点或者是叶子结点，保存x的踪迹使其移动到y的原始位置上
if (z->parent->left==z)
{
if (x!=nil)
{
while (p!=nil&&p->parent->left==p)
{
p->Min=x->Min;
p=p->parent;
}
p->Min=x->Min;
}
else
{
while (p!=nil&&p->parent->left==p)
{
p->Min=k;
p=p->parent;
}
p->Min=k;
}
}
else
{
if (x!=nil)
{
while(p!=nil&&p->parent->right==p)
{
p->Max=x->Max;
p=p->parent;
}
p->Max=x->Max;
}
else
{
while (p!=nil&&p->parent->right==p)
{
p->Max=k;
p=p->parent;
}
p->Max=k;
}
}
RB_TRANSPLANT(z,z->right);//把以z.right为根的子树替换以z为根的子树。
}
else if (z->right==nil)
{
while (t!=nil)
{
t->size--;
t=t->parent;
}
x=z->left;//x指向y的唯一子结点或者是叶子结点，保存x的踪迹使其移动到y的原始位置上
if(z->parent->right==z)
{
while (p!=nil&&p->parent->right==p)
{
p->Max=x->Max;
p=p->parent;
}
p->Max=x->Max;
}
else
{
while (p!=nil&&p->parent->left==p)
{
p->Min=x->Min;
p=p->parent;
}
p->Min=x->Min;
}
RB_TRANSPLANT(z,z->left);//把以z.left为根的子树替换以z为根的子树。
}
else
{
y=TREE_MINIMUM(z->right);//找到z.right的后继。
struct OS_Tree*t=y->parent;
y->size=z->size-1;//y替换z原来的位置，所以size属性在待删除结点z基础上-1
while (t!=nil)
{
t->size--;
t=t->parent;
}
y_original_color=y->color;//y的新的原始结点被重置。
x=y->right;//x指向y的唯一子结点或者是叶子结点，保存x的踪迹使其移动到y的原始位置上
y->Min=z->left->Min;//+
if (y->parent==z)
{
x->parent=y;//由于z的父结点是要删除的结点，所以不能指向它，于是指向y
}
else
{
struct OS_Tree*w=z->right;
if (y->right!=nil)
{
while (w->left!=nil)
{
w->Min=x->Min;
w=w->left;
}
}
else
{
while (w->left!=nil)
{
w->Min=y->parent;
w=w->left;
}
}
y->Max=z->Max;//+
RB_TRANSPLANT(y,y->right);//把以y.right为根的子树替换以y为根的子树。
y->right=z->right;
y->right->parent=y;
}
RB_TRANSPLANT(z,y);//把以y为根的子树替换以z为根的子树。
y->left=z->left;
y->left->parent=y;
y->color=z->color;//把已经删除的结点颜色赋值给y，保证了y以上的树结构红黑性质不变。
}
if (z->prev==nil)
{
head=z->next;
}
if (z->next==nil)
{
tail=z->prev;
}
z->prev->next=z->next;
z->next->prev=z->prev;
if(y_original_color==BLACK) //y的原始颜色为黑色，说明需要调整红黑颜色。
RB_DELETE_FIXUP(x);
}
//中序遍历
void InOderTraverse(struct OS_Tree *p)
{
if (p!=nil)
{
InOderTraverse(p->left);
cout<<p->key<<" "<<p->color<<" "<<"最大值:"<<p->Max->key<<"最小值:"<<p->Min->key<<"秩："<<p->size<<endl;
InOderTraverse(p->right);
}
}
int RAND(int a[],int i)//随机选择N个互不相同的数。
{
int k=rand()%n+1;
for (int j=0;j<i;j++)
{
if (a[j]==k)
{
k=rand()%n+1;
j=-1;
}
}
return k;
}
struct OS_Tree*OS_SELECT(struct OS_Tree*x,int i)//查找顺序统计树给定秩的元素
{
int r=x->left->size+1;
if (i==r)
{
return x;
}
else if (i<r)
{
return OS_SELECT(x->left,i);
}
else return OS_SELECT(x->right,i-r);
}
int OS_RANK(struct OS_Tree*T,struct OS_Tree*x)//确定顺序统计树的秩
{
int r=x->left->size+1;
struct OS_Tree*y=x;
while (y!=root)
{
if (y==y->parent->right)
{
r=r+y->parent->left->size+1;
}
y=y->parent;
}
return r;
}
void main()
{
//srand( (unsigned)time( NULL ) );
int array1[n]={0};
for (int j=0;j<n;j++)
{
array1[j]=RAND(array1,j);
cout<<array1[j]<<" ";
}
cout<<endl;
nil=new struct OS_Tree[LEN];
nil->key=Nil;nil->color=BLACK;
root=nil;
int i=0;
struct OS_Tree*ROOT=new struct OS_Tree[LEN];
ROOT->key=array1[i++];
RB_INSERT(ROOT);
root=ROOT;
while (i!=n)
{
struct OS_Tree*z=new struct OS_Tree[LEN];
z->key=array1[i];
RB_INSERT(z);
i++;
}
InOderTraverse(root);
cout<<endl;
struct OS_Tree*x=NULL;
i=0;
while(i!=n)
{
x=ITERATIVE_TREE_SEARCH(root,array1[i]);
cout<<OS_RANK(root,x)<<endl;
RB_DELETE(x);
cout<<"删除"<<array1[i++]<<"后中序遍历："<<endl;
InOderTraverse(root);
}
cout<<endl;
}
总结：以上程序适当地对插入和删除函数进行修改，修改部分只是增加了O(lgn)时间的常系数，比如在插入过程中，需要从叶结点向上遍历到根结点，遍历这段路径只需O(lgn)时间，删除函数也有类似情况。其他函数有的增加了常数时间，有的未作改动。总体来看，在增加新属性的基础上，除求最值和前驱后继操作时间变为O(1)，其他操作渐进性能均不受影响。