首页 > 代码库 > 红黑树上的连接操作
红黑树上的连接操作
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<<"关键字:"<<p->key<<"\t"<<" 颜色:";
if (p->color)
{
cout<<"红"<<"\t";
}
else cout<<"黑"<<"\t";
cout<<" 黑高："<<p->bh<<"\t"<<endl;
InOderTraverse(p->right);
}
}
//13-2b问求T1中黑高度为bh[T2]的最大关键字黑结点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);
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。