首页 > 代码库 > 最大最小值以及前驱后继操作最坏情况都为O(1)的顺序统计树
最大最小值以及前驱后继操作最坏情况都为O(1)的顺序统计树
问题:通过为结点增加指针的方式,试说明如何在扩张的顺序统计树上,支持每一动态集合查询操作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),其他操作渐进性能均不受影响。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。