题目：

思考：

      既然是动态集合，那么我们需要用链表来存储数据方便插入和删除。于是我们可以选用二叉链表，也就是红黑树来存储数据，红黑树由于比较平衡，所以可以得到比较好的查询时间。但是我们并不是直接拿红黑树就可以用了，因为基本的红黑树没有MIN_GAP操作，所以需要自己修改和维护原始的红黑树。

      如何给红黑树添加MIN_GAP操作呢？我们需要先给红黑树结构中加入MAX，MIN指针。这个操作可以参考最坏时间为O(1)的求最大小值，当然只取了里面部分新增代码。既然新指针已经添加好了，那么我们以原有红黑树插入删除操作为子程序，添加针对本题的新插入删除操作。新的插入删除函数维护2个树，一棵是集合Q所组成的树，还有一棵是Q的每两个最接近数的差值组成的树T2

      如何添加新的插入删除操作呢？分以下几个步骤来讲：

插入操作：①先将新结点z插入树中。

                  ②找到新结点z的前驱x1和后继x2。

                  ③分别找到新结点与前驱和后继的GAP，分别插入到以Q的两个最接近数为差值组成的树T2中。

                  ④最后将x1与x2的GAP删除。

删除操作：①查找值为z的结点x。

                  ②找到待删除结点z的前驱x1和后继x2。

                  ③分别找到待删除结点与前驱和后继的GAP，分别删除。

                  ④在删除z之前，z的前驱和后继在删除z后会形成新的GAP，所以插入这个GAP。

                  ⑤最后删除z.

代码如下:

#include <iostream>
#include <time.h>
using namespace std;
#define BLACK 0
#define RED 1
#define Nil -1
#define LEN sizeof(struct Tree)
#define n 10//这里更改数据量
struct Tree
{
   struct Tree*left;
   struct Tree*right;
   struct Tree*parent;
   int key;
   int color;
   struct Tree*Min;//记录以x为根结点的树中最小的关键字  
   struct Tree* Max;//记录以x为根结点的树中最大的关键字 

};
struct Tree*root1=NULL;
struct Tree*root2=NULL;
struct Tree*nil=NULL;
//非递归版本的查找二叉查找树的最小值
struct Tree*ITERATIVE_TREE_MINIMUM(struct Tree*x)
{
	while (x!=nil&&x->left!=nil)
	{
		x=x->left;
	}
	return x;
}
//非递归版本的查找二叉查找树的最大值
struct Tree*ITERATIVE_TREE_MAXIMUM(struct Tree*x)
{
	while (x!=nil&&x->right!=nil)
	{
		x=x->right;
	}
	return x;
}
void LEFT_ROTATE(struct Tree*&root,struct Tree*x)
{//左旋转：分三个步骤①②③来叙述旋转代码的。
	struct 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;
}
void RIGHT_ROTATE(struct Tree*&root,struct Tree*x)
{//右旋转：分三个步骤①②③来叙述旋转代码的。
	struct 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;
}
void RB_INSERT_FIXUP(struct Tree*&root,struct Tree*z)
{
   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进入下一次循环
		   } 
		   else 
		   {
			   if (z==z->parent->right)//情况二：检查z是否是一个右孩子且叔结点为黑色，前提是p1结点不是叶子结点
			   {//使用一个左旋让情况2转变为情况3
				   z=z->parent;
				   LEFT_ROTATE(root,z);//由于进入if语句后可知旋转结点不可能是叶子结点，这样就不用判断z是否是叶子结点了。
			   } 
               z->parent->color=BLACK;//情况三：是z是一个左孩子且叔结点为黑色，改变z的父和祖父结点颜色并做一次右旋，以保持性质5
			   z->parent->parent->color=RED;
			   RIGHT_ROTATE(root,z->parent->parent);//由于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;
		   } 
		   else 
		   {
			   if (z==z->parent->left)
			   {
				   z=z->parent;
				   RIGHT_ROTATE(root,z);
			   } 
               z->parent->color=BLACK;
			   z->parent->parent->color=RED;
			   LEFT_ROTATE(root,z->parent->parent);
		   }
	   }
   }
   root->color=BLACK;//最后给根结点着为黑色。
}
void RB_INSERT(struct Tree*&root,struct Tree*z)
{
	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;
		while (y)
		{ 
			y->Min=z;
			if (y->parent==nil||y->parent->right==y)
			{
				break;
			}
			y=y->parent;
		}
	}
	else 
	{
		y->right=z;
		while (y)
		{
			y->Max=z;
			if (y->parent==nil||y->parent->left==y)
			{
				break;
			}
			y=y->parent;
		}
	}
	z->left=nil;//给插入结点左右孩子赋值为空。
	z->right=nil;
	z->color=RED;//给插入结点着为红色。
	z->Max=z->Min=z;
	RB_INSERT_FIXUP(root,z);
}
void RB_TRANSPLANT(struct Tree*&root,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*TREE_PREDECESSOR(struct Tree*x)
{
   if (x->left!=nil)
   {
	   return ITERATIVE_TREE_MAXIMUM(x->left);
   }
   struct Tree*y=x->parent;
   while (y!=nil&&x==y->left)
   {
	   x=y;
	   y=y->parent;
   }
   return y;
}
//查找二叉查找树的后继
struct Tree*TREE_SUCCESSOR(struct Tree*x)
{
	if (x->right!=nil)
	{
		return ITERATIVE_TREE_MINIMUM(x->right);
	}
	struct Tree*y=x->parent;
	while (y!=nil&&x==y->right)
	{
		x=y;
		y=y->parent;
	}
	return y;
}
//非递归版本的二叉查找树查找函数
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*&root,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;
			 if (w->color==RED)//情况一：x的兄弟结点w是红色的。
			 {//改变w和x.p的颜色+一次旋转使其变为情况二，三，四。
				 w->color=BLACK;
				 x->parent->color=RED;
				 LEFT_ROTATE(root,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(root,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(root,x->parent);
				 x=root;//x成为根结点，结束循环。
			 }
		 } 
		 else//以下和上面的if分支类似，不做累述。
		 {
             w=x->parent->left;
			 if (w->color==RED)
			 {
				 w->color=BLACK;
				 x->parent->color=RED;
				 RIGHT_ROTATE(root,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(root,w);
					 w=x->parent->left;
				 }
				 w->color=x->parent->color;
				 x->parent->color=BLACK;
				 w->left->color=BLACK;
				 RIGHT_ROTATE(root,x->parent);
				 x=root;
			 }
		 }
     }
	 x->color=BLACK;
}
void RB_DELETE(struct Tree*&root,struct Tree*z)
{
    struct Tree*y=z,*x;//y为待删除或待移动结点
	int y_original_color=y->color;//保存y的原始颜色，为做最后的调整做准备。
	struct Tree*k=z->parent,*p=z->parent,*t=z->parent;
	if (z->left==nil)
	{
		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(root,z,z->right);//把以z.right为根的子树替换以z为根的子树。
	}
	else if (z->right==nil)
	{
		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(root,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的原始位置上
		y->Min=z->left->Min;
		if (y->parent==z)
		{
			x->parent=y;//由于z的父结点是要删除的结点，所以不能指向它，于是指向y
		} 
		else
		{
			struct 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(root,y,y->right);//把以y.right为根的子树替换以y为根的子树。
			y->right=z->right;
			y->right->parent=y;
		}
		RB_TRANSPLANT(root,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(root,x);
	if (root==nil)
	{
		root->Max=root->Min=nil;
	}
}
//中序遍历
void InOderTraverse(struct Tree *p)
{
    if (p!=nil)
	{		
		InOderTraverse(p->left);
		cout<<p->key<<" ";
		InOderTraverse(p->right);
	}
}
//我们以原有红黑树各种操作作为子函数来创建新的插入删除函数
//新的插入删除函数维护2个树，一棵是集合Q所组成的树，还有一棵是Q的每两个最接近数的差值组成的树
void INSERT_GAP(struct Tree *&r1,struct Tree *&r2,struct Tree *z)
{//O(lgn)
	RB_INSERT(r1,z);//先将新结点插入树中。
	struct Tree *x1=TREE_PREDECESSOR(z);//找到x1为前驱
	struct Tree *x2=TREE_SUCCESSOR(z);//找到x2为后继
	if (x1!=nil)
	{
	   struct Tree*x=new struct Tree[LEN];
	   x->key=z->key-x1->key;
	   RB_INSERT(r2,x);//插入z与z的前驱的GAP
	}
	if (x2!=nil)
	{
		struct Tree*x=new struct Tree[LEN];
		x->key=x2->key-z->key;
	   RB_INSERT(r2,x);//插入z的后继与z的GAP
	}
	if (x1!=nil&&x2!=nil)
	{
        struct Tree *x=ITERATIVE_TREE_SEARCH(r2,x2->key-x1->key);
        if(x!=nil) RB_DELETE(r2,x);//删除原x1与x2的GAP
	}
}
void DELETE_GAP(struct Tree *&r1,struct Tree *&r2,int z)
{
   struct Tree*x=ITERATIVE_TREE_SEARCH(r1,z);//查找值为z的结点x
   struct Tree *x1=TREE_PREDECESSOR(x);//x1为x的前驱
   struct Tree *x2=TREE_SUCCESSOR(x);//x2为x的后继
   if(x1!=nil)
   {
     struct Tree* y1=ITERATIVE_TREE_SEARCH(r2,z-x1->key);
	  RB_DELETE(r2,y1);//找到z与z的前驱的GAP并删除它
   }
   if(x2!=nil) 
   {
      struct Tree*y2=ITERATIVE_TREE_SEARCH(r2,x2->key-z);
	  RB_DELETE(r2,y2);//找到z与z的后继的GAP并删除它
   }
   if (x1!=nil&&x2!=nil)
   {
	   struct Tree*d=new struct Tree[LEN];
	   d->key=x2->key-x1->key;
	   RB_INSERT(r2,d);//z被删除后，z的前驱后继会形成新的GAP插入它
   }
   RB_DELETE(r1,x);//最后将z删除。
}
struct Tree*MIN_GAP(struct Tree*r2)
{
	return r2->Min;
}
void main()
{
	srand( (unsigned)time( NULL ) );
	int array1[n] ={0};
	for (int j=0;j<n;j++)
	{
		array1[j]=rand()%100+1;
	} 
	nil=new struct Tree[LEN];
	nil->key=Nil;nil->color=BLACK;
	root2=root1=nil;
	int i=0;
	struct Tree*ROOT=new struct Tree[LEN];
	ROOT->key=array1[i++];
	INSERT_GAP(root1,root2,ROOT);
	root1=ROOT;
    while (i!=n)
    {
		struct Tree*z=new struct Tree[LEN];
		z->key=array1[i];
		INSERT_GAP(root1,root2,z);
		i++;
    }
	InOderTraverse(root1);
	cout<<endl;
	InOderTraverse(root2);
	cout<<endl;
	cout<<"插入后，GAP="<<MIN_GAP(root2)->key<<endl;
	cout<<endl;
	for(i = 0; i< n; i++)  
	{   
		DELETE_GAP(root1,root2,array1[i]);
		cout<<"删除"<<array1[i]<<"后，动态集合Q：GAP="<<MIN_GAP(root2)->key<<endl;
		InOderTraverse(root1); 
		cout<<endl;
		cout<<"由动态集合Q每两个最接近数据组成的GAP组成的集合为:"<<endl;
		InOderTraverse(root2);
		cout<<endl;
		cout<<endl;
	}  
}