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);
}