首页 > 代码库 > 红黑树上的连接操作

红黑树上的连接操作

技术分享

a)①对于插入调整红黑树性质函数。注意到仅仅有case1才会添加黑高,引用书中的图13-5所看到的 无论是a图还是b图,结点C从左图到右图黑高添加了1.其它结点黑高均无变化。详细13-5和13-6图全部结点黑高能够
參考13.3-3题目答案。
  ②对于删除调整红黑树性质函数,能够使用13.3-3类似的方法计算其黑高变化,结果就是case2的B结点降低1。case4结点D添加1,结点B降低1.(请參考图13-7)其它case和结点均无变化。
  ③对于删除函数假设是第3种情况。须要找到删除结点的后继,那么我们把其删除结点的黑高复制给其后继。
因而我们能够仅仅需把删除和插入函数某个if-else推断上添加几行对黑高的计算代码,当然不用额外加入不论什么迭代和递归操作就能够完毕上面操作。详细请看以下代码。
b)找出右子树的右子树的。。

。。

的右子树,循环或者递归地找出树高为bh[T2].

c)发现bh[Ty]=bh[T2],又由于key[y]≤key[x]≤key[T2],所以用以x为根的树,其左子树就是子树y,右子树就是树T2。

d)着红色。详细看以下程序。

e)对于bh[T1]≤bh[T2],能够在T2中找出高度为bh[T1]的最大结点y。将Ty∪{x}∪T1代替Ty.

f)由于a,b,c,d部分的时间都是O(lgn),详细看以下程序便知。

完整程序例如以下:

//13-2红黑树的连接操作
#include <iostream>
using namespace std;
#define BLACK 0
#define RED 1
#define Nil -1
#define LEN sizeof(struct Tree)
struct Tree
{
   struct Tree*left;
   struct Tree*right;
   struct Tree*parent;
   int bh;
   int key;
   int color;
};
struct Tree*root=NULL;
struct Tree*nil=NULL;
void LEFT_ROTATE(struct Tree*x,struct Tree*&root)
{//左旋转:分三个步骤①②③来叙述旋转代码的。
	struct Tree*y=x->right;//设置y结点。
	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; } void RIGHT_ROTATE(struct Tree*x,struct Tree*&root) {//右旋转:分三个步骤①②③来叙述旋转代码的。 struct Tree*y=x->left;//设置y结点。 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; } void RB_INSERT_FIXUP(struct Tree*z,struct Tree*&root) { while (z->parent->color==RED) { if (z->parent==z->parent->parent->left) { struct 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进入下一次循环 z->bh++;//13-2插入函数新添加的计算黑高表达式。 } else { if (z==z->parent->right)//情况二:检查z是否是一个右孩子且叔结点为黑色。前提是p1结点不是叶子结点 {//使用一个左旋让情况2转变为情况3 z=z->parent; LEFT_ROTATE(z,root);//因为进入if语句后可知旋转结点不可能是叶子结点,这样就不用推断z是否是叶子结点了。 } z->parent->color=BLACK;//情况三:是z是一个左孩子且叔结点为黑色,改变z的父和祖父结点颜色并做一次右旋,以保持性质5 z->parent->parent->color=RED; RIGHT_ROTATE(z->parent->parent,root);//因为p2可能是叶子结点,所以不妨用一个if推断 } } else//以下else分支相似于上面,注意到else分支的情况2和情况3所做旋转正好是if分支情况的逆。 { struct 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; z->bh++;//13-2插入函数新添加的计算黑高表达式。

} else { if (z==z->parent->left) { z=z->parent; RIGHT_ROTATE(z,root); } z->parent->color=BLACK; z->parent->parent->color=RED; LEFT_ROTATE(z->parent->parent,root); } } } root->color=BLACK;//最后给根结点着为黑色。 } void RB_INSERT(struct Tree*z,struct Tree*&root) { struct Tree*y=nil; struct Tree*x=root; while (x!=nil) { y=x; if (z->key<x->key) { x=x->left; } else x=x->right; } z->parent=y; if (y==nil) { root=z; } else if(z->key<y->key) { y->left=z; } else y->right=z; z->left=nil;//给插入结点左右孩子赋值为空。

z->right=nil; z->color=RED;//给插入结点着为红色。 RB_INSERT_FIXUP(z,root); } void RB_TRANSPLANT(struct Tree*u,struct 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 Tree*ITERATIVE_TREE_MINIMUM(struct Tree*x) { struct Tree*x1=x->parent; while (x->left->key!=Nil) { x=x->left; } x->bh=x1->bh; return x; } //非递归版本号的二叉查找树查找函数 struct Tree*ITERATIVE_TREE_SEARCH(struct 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 Tree*x) { struct Tree*w=NULL;//w是x的兄弟结点 while (x!=root&&x->color==BLACK)//假设x是黑色而且不是根结点。才进行循环。

{//x是一个具有双重颜色的结点。调整的目的是把x的黑色属性向上移动。 if (x==x->parent->left) { w=x->parent->right;//x的兄弟结点w if (w->color==RED)//情况一:x的兄弟结点w是红色的。 {//改变w和x.p的颜色+一次旋转使其变为情况二。三。四。 w->color=BLACK; x->parent->color=RED; LEFT_ROTATE(x->parent,root); 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结点向上移动成为新的待调整结点。 x->bh--;//情况2:原结点x的父结点也就是如今新结点x黑高降低1. } else { if (w->right->color==BLACK)//情况三:x的兄弟结点w是黑色的,w的左孩子是红色的。w的右孩子是黑色的。

{//交换w和w.left的颜色+旋转使其转变为情况四。 w->left->color=BLACK; w->color=RED; RIGHT_ROTATE(w,root); 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,root); w->bh++;//情况4:w的黑高添加1 w->left->bh--;//情况4:未做旋转时的w的父结点也就是旋转后的w的左孩子结点黑高减1 x=root;//x成为根结点,结束循环。 } } else//以下和上面的if分支相似,不做累述。

{ w=x->parent->left; if (w->color==RED) { w->color=BLACK; x->parent->color=RED; RIGHT_ROTATE(x->parent,root); w=x->parent->left; } if (w->left->color==BLACK&&w->right->color==BLACK) { w->color=RED; x=x->parent; x->bh--; } else { if (w->left->color==BLACK) { w->right->color=BLACK; w->color=RED; LEFT_ROTATE(w,root); w=x->parent->left; } w->color=x->parent->color; x->parent->color=BLACK; w->left->color=BLACK; RIGHT_ROTATE(x->parent,root); w->right->bh--; w->bh++; x=root; } } } x->color=BLACK; } void RB_DELETE(struct Tree*z) { struct Tree*y=z,*x;//y为待删除或待移动结点 int y_original_color=y->color;//保存y的原始颜色,为做最后的调整做准备。

if (z->left==nil) { x=z->right;//x指向y的唯一子结点或者是叶子结点,保存x的踪迹使其移动到y的原始位置上 RB_TRANSPLANT(z,z->right);//把以z.right为根的子树替换以z为根的子树。 } else if (z->right==nil) { x=z->left;//x指向y的唯一子结点或者是叶子结点。保存x的踪迹使其移动到y的原始位置上 RB_TRANSPLANT(z,z->left);//把以z.left为根的子树替换以z为根的子树。 } else { y=ITERATIVE_TREE_MINIMUM(z->right);//找到z.right的后继。 y_original_color=y->color;//y的新的原始结点被重置。 x=y->right;//x指向y的唯一子结点或者是叶子结点,保存x的踪迹使其移动到y的原始位置上 if (y->parent==z) { x->parent=y;//因为z的父结点是要删除的结点。所以不能指向它,于是指向y } else { 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(y_original_color==BLACK) //y的原始颜色为黑色,说明须要调整红黑颜色。

RB_DELETE_FIXUP(x); } //中序遍历 void InOderTraverse(struct Tree *p) { if (p!=nil) { InOderTraverse(p->left); cout<<"keyword:"<<p->key<<"\t"<<" 颜色:"; if (p->color) { cout<<"红"<<"\t"; } else cout<<"黑"<<"\t"; cout<<" 黑高:"<<p->bh<<"\t"<<endl; InOderTraverse(p->right); } } //13-2b问求T1中黑高度为bh[T2]的最大keyword黑结点y. struct Tree*T1_MAX_bhT2(struct Tree*T1,struct Tree*T2) { struct Tree*T=T2; while (T2->right->key!=Nil) { T2=T2->right; } while (T1->bh!=T->bh) { T1=T1->right; } struct Tree*y=T1; return y; } //RB-JOIN T1=T2的情况。 struct Tree*RB_JOIN1(struct Tree*y,struct Tree*&x,struct Tree*T2) { x=new struct Tree[LEN]; x->key=48; x->color=RED;//为了防止破坏性质135所以这里初始为红色。 struct Tree*Root=x; x->left=y;//x左子树是以结点y的子树 x->right=T2;//x右子树是以结点T2的子树 y->parent=x;//父结点也对应的连接上 T2->parent=x;//父结点也对应的连接上 x->parent=nil;//假设y的黑高就是T1的黑高。那么结点x为根,所以其父结点就要赋值为空。 x->bh=T2->bh+1;//因为T2树的根一定是黑色的,所以结点x的黑高是T2黑高加1. return Root; } //RB-JOIN T1>=T2的情况。

struct Tree*RB_JOIN2(struct Tree*T1,struct Tree*&x,struct Tree*T2) { struct Tree*y=T1_MAX_bhT2(T1,T2);//找出第1棵树中黑高为第2棵树的高度的最大结点。

struct Tree*y1=y->parent;//保存最大结点的父结点用于连接结点x。 struct Tree*Root=RB_JOIN1(y,x,T2);//用结点x连接以y为根的子树和T2树组成新树。

if (y->bh!=T1->bh)//T1与T2黑高不等,就把上面刚组合成的新树与T1中的y父结点连接。终于达成T1与T2合并的目标。

{ y1->right=Root; Root->parent=y1; } RB_INSERT_FIXUP(x,T1);//结点x因为初始为红色,所以可能破坏性质2与4,于是进行调整。 return T1; } void main() { int array1[20]={26,17,41,14,21,30,47,10,16,19,23,28,38,7,12,15,20,35,39,3};//该样例能够非常好的囊括删除case1234 //int array1[9]={11,2,14,1,7,15,5,8,4};//该样例能够非常好的囊括插入case123 nil=new struct Tree[LEN]; nil->key=Nil;nil->color=BLACK; root=nil; int i=0; struct Tree*ROOT=new struct Tree[LEN]; ROOT->key=array1[i++]; ROOT->bh=1; RB_INSERT(ROOT,root); root=ROOT; while(i!=20) { struct Tree*z=new struct Tree[LEN]; z->key=array1[i]; z->bh=1; RB_INSERT(z,root); i++; } cout<<"本数据选自书中第1节所给数据:"<<endl; InOderTraverse(root); cout<<endl; int array2[8] = {14,26,21,30,41,7,19,16}; //该样例能够非常好的囊括删除case1234 for(i = 0; i<8; i++) { struct Tree*x=ITERATIVE_TREE_SEARCH(root,array2[i]); RB_DELETE(x); cout<<"删除"<<array2[i]<<"后树中数据有"<<endl; InOderTraverse(root); cout<<endl; } struct Tree*root1=NULL; struct Tree*root2=NULL; int array3[8]={49,50,51,52,53,54,55,56}; root1=nil; i=0; struct Tree*ROOT1=new struct Tree[LEN]; ROOT1->key=array1[i++]; ROOT1->bh=1; RB_INSERT(ROOT1,root1); root1=ROOT1; while(i!=20) { struct Tree*z=new struct Tree[LEN]; z->key=array1[i]; z->bh=1; RB_INSERT(z,root1); i++; } root2=nil; int j=0; struct Tree*ROOT2=new struct Tree[LEN]; ROOT2->key=array3[j++]; ROOT2->bh=1; RB_INSERT(ROOT2,root2); root2=ROOT2; while(j!=8) { struct Tree*z=new struct Tree[LEN]; z->key=array3[j]; z->bh=1; RB_INSERT(z,root2); j++; } cout<<"第1棵树:"<<endl; InOderTraverse(root1); cout<<endl; cout<<"第2棵树:"<<endl; InOderTraverse(root2); struct Tree*x=NULL; struct Tree*f=RB_JOIN2(root1,x,root2); cout<<endl; cout<<"连接两棵树后:"<<endl; InOderTraverse(f); }




红黑树上的连接操作