首页 / 算法 / 算法导论--动态顺序统计与区间树
算法导论--动态顺序统计与区间树
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法导论--动态顺序统计与区间树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含21011字，纯文字阅读大概需要31分钟。
内容图文
本文的基础是红黑树 算法导论–红黑树
通过在基础的数据结构中添加一些附加信息，来扩张一种标准的数据结构，然后编写新的操作来支持所需要的应用。下面是介绍在红黑树的基础上扩张的数据结构。
1.动态顺序统计
动态顺序统计可以在O(lgn)时间内确定任何的顺序统计量(即在n个元素的集合中，能在O(lgn)的时间内确定第i小的元素)，同时也可以在O(lgn)的时间内计算一个元素的秩(即它在中序遍历下的位置顺序)。
1 添加附加信息
结点x中加入x.size , size的大小为以x为根的子树（包含x本身）的内结数，即子树的大小。我们定义哨兵的size为0，如下图： 
结点内，虚线上方为关键字key，下方为结点的size。
可以看出： x.size = x.left.size + x.right.size +1；
enum colors{red,black};//枚举类型typedefstruct Node
{
struct Node * p;
struct Node *left;
struct Node *right;
int key;
enum colors color; //颜色属性int size; //新添加的属性size
}Node;
2 修改基本操作
插入操作：
为了对子树规模的维护，需要在不影响插入和删除操作的渐进运行时间的前提下，修改基本的操作。
第一阶段：新节点的插入过程中，需要对从根到将要插入的位置过程中遍历的结点的size加1；
第二阶段：维护红黑树的左旋和右旋函数需要在最后添加以下语句： 
/*左旋*/
y
.size = x.size;x.size = x.left.size + x.right.size +1;/*右旋*/x.size = y.size;y.size = y.left.size + y.right.size +1;
删除操作：
第一阶段：如果要删除的结点z少于两个孩子，则从z到根T的过程遍历的结点size减1；如果要删除的结点z多于两个孩子，则从z的后继y处向上到T的过程中，遍历的结点size减1；
第二阶段：
也是同样在左右旋过程中，添加以上的语句；
插入操作和删除操作运行时间都是O(lgn).
3 设计新的操作
1.给定秩的元素的检索
调用函数OS_Select(Node * x,int i)检索出在以x为根的子树中，第i小的关键字的结点。运行时间为O(lgn);
Node * OS_Select(Node *x,int i)
{
int r =x->left->size+1; //计算以结点x为根的子树中顺序统计量rif (i == r)
return x;
elseif (i < r)
return OS_Select(x->left,i); //在x的左子树里继续递归查找elsereturn OS_Select(x->right,i-r);//在x的右子树里继续递归查找
}
2.确定一个元素的秩
给定指向T中，结点x的指针，过程OS_Rank返回对T中序遍历对应的线性序中x的位置；运行时间为O(lgn)
int OS_Rank(Node *T,Node * x)
{
int r =x->left->size+1; //计算以结点x为根的子树中顺序统计量r
Node * y =x;
while(y != T) //叠加到root根节点位置
{
if (y == y->p->right) //父节点的右子树输出在左子树和根之后，顺序统计量叠加
{
r=r+y->p->left->size+1;
}
y = y->p; //若属于左子树，直接跳向上层
}
return r;
}
4 完整代码
/*
CSDN 勿在浮砂筑高台
http://blog.csdn.net/luoshixian099
算法导论--顺序统计量2015年5月20日
*/
#include <STDIO.H> #include <STDLIB.H>enum colors{red,black};//枚举类型
typedef struct Node
{
struct Node * p;
struct Node *left;
struct Node *right;
int key;
enum colors color;
int size; //添加附加信息size
}Node;
Node *T_NIL=NULL; //建立全部变量 T_NILNode * Tree_Minimum(Node * T) //找最小结点
{
while(T->left != T_NIL)
T=T->left;
return T;
}
voidInorder_Tree_Walk(Node * T) //中序遍历树T,输出
{
if ( T != T_NIL)
{
Inorder_Tree_Walk(T->left); //递归其左孩子
printf("%d",T->key); //输出根的关键字
if (T->color == 0)
{
printf("-R");
}
else
{
printf("-B");
}
printf("-(%d) ",T->size);
Inorder_Tree_Walk(T->right); //递归其右孩子
}
}
voidPre_Tree_Walk(Node * T) //
{
if ( T != T_NIL)
{
printf("%d ",T->key); //输出根的关键字
Pre_Tree_Walk(T->left); //递归其左孩子
Pre_Tree_Walk(T->right); //递归其右孩子
}
}
voidLeft_Rotate(Node **T,Node * x) //左旋
{
Node *y=x->right;
x->right =y->left;
if (y->left != T_NIL)
y->left->p=x;
y->p=x->p;
if(x->p==T_NIL)
*T=y;
elseif (x == x->p->left)
x->p->left = y;
else
x->p->right = y;
y->left = x;
x->p=y;
y->size = x->size; //添加语句维护size
x->size = x->left->size+x->right->size+1;
}
voidRight_Rotate(Node **T,Node * y) //右旋
{
Node *x=y->left;
y->left =x->right;
if (x->right != T_NIL)
x->right->p=y;
x->p=y->p;
if(y->p==T_NIL)
*T=x;
elseif (y == y->p->left)
y->p->left = x;
else
y->p->right = x;
x->right = y;
y->p=x;
x->size = y->size; //添加语句维护size
y->size = y->left->size+y->right->size+1;
}
Node* RB_Insert_Fixup(Node *T,Node *z)
{
Node * y=NULL;
while( z->p->color == red) //违反了性质4，迭代进行修正
{
if (z->p == z->p->p->left)
{
y = z->p->p->right;
if ( y->color == red) // case1 叔结点为红色
{
z->p->color = black; //父节点涂黑
y->color = black; //叔结点涂黑
z->p->p->color = red; //祖结点涂红
z = z->p->p; //向上迭代，更新z的位置
}
elseif ( z == z->p->right) //case2 叔结点为黑色且z为双亲的右孩子
{
z = z->p;
Left_Rotate(&T,z);
z->p->color = black; //case2 已转为 case3 继续处理
z->p->p->color = red;
Right_Rotate(&T,z->p->p);// while循环终止
}
else // case3 叔结点为黑色且z为双亲的左孩子
{
z->p->color = black;
z->p->p->color = red;
Right_Rotate(&T,z->p->p);// while循环终止
}
}
else //对称处理
{
y = z->p->p->left;
if ( y->color == red) // case1 叔结点为红色
{
z->p->color = black;
y->color = black;
z->p->p->color = red;
z = z->p->p;
}
elseif ( z == z->p->left) //case2 叔结点为黑色且z为双亲的右孩子
{
z = z->p;
Right_Rotate(&T,z);
z->p->color = black;
z->p->p->color = red;
Left_Rotate(&T,z->p->p);//
}
else // case3
{
z->p->color = black;
z->p->p->color = red;
Left_Rotate(&T,z->p->p);
}
}
}
T->color = black; //保证不会违反性质2，对根节点涂黑
return T;
}
Node *RB_Insert(Node *Root,Node * z) //红黑树插入,返回树的根
{
Node * y=T_NIL;
Node * x=Root;
while( x != T_NIL) //找到结点z要插入的位置
{
x->size+=1; //插入过程中，遍历的结点size加1
y=x;
if (z->key < x->key)
x = x->left;
else
x = x->right;
}
z->p = y;
if ( y == T_NIL) //插入第一个结点作为根节点的情况
Root = z;
elseif (z->key < y->key)
y->left = z;
else
y->right = z;
Root = RB_Insert_Fixup(Root,z); //插入完毕后，对红黑树的颜色进行修正
return Root;
}
Node * Establish(int *A,int len) //建立红黑树
{
Node * T,*node;
int i=0;
node=NULL;
T_NIL=(Node *)malloc(sizeof(Node)); //建立T_NIL结点
T_NIL->p=NULL;
T_NIL->left=NULL;
T_NIL->right=NULL;
T_NIL->key=-1;
T_NIL->color=black;
T_NIL->size=0;
T=T_NIL;
for (i=0;i<len;i++)
{
node =(Node *)malloc(sizeof(Node));
node->p =T_NIL;
node->left=T_NIL;
node->right=T_NIL;
node->key=A[i];
node->color=red;
node->size=1;
T=RB_Insert(T,node);
}
return T;
}
voidRB_Transplant(Node **T,Node * u,Node * v) //结点替代函数
{
if (u->p == T_NIL)
*T = v;
elseif (u == u->p->left)
u->p->left = v;
else
u->p->right = v;
v->p = u->p; //此处赋值无条件，v如果是T_NIL也要进行赋值
}
voidRB_Delete_Fixup(Node * T,Node * x)
{
Node *w=NULL;
while( x != T && x->color == black) //循环迭代处理
{
if ( x == x->p->left )
{
w = x->p->right;
if (w->color == red) // case1------> case 2 , case 3 ,case 4
{
w->color = black;
x->p->color =red;
Left_Rotate(&T,x->p);
w = x->p->right;
}
if ( w->left->color == black && w->right->color == black ) //case2------>go on / stop
{
w->color = red;
x = x->p;
}
elseif ( w->right->color == black) // case3---->case 4---->stop
{
w->left->color = black;
w->color =red ;
Right_Rotate(&T,w);
w = x->p->right ; //转成case4处理
w->color = x->p->color;
x->p->color = black;
w->right->color = black;
Left_Rotate(&T,x->p);
x = T;
}
else // case4------------------->stop
{
w->color = x->p->color;
x->p->color = black;
w->right->color = black;
Left_Rotate(&T,x->p);
x = T;
}
}
else
{
w = x->p->left;
if (w->color == red) // case1------> case 2 , case 3 ,case 4
{
w->color = black;
x->p->color =red;
Right_Rotate(&T,x->p);
w = x->p->left;
}
if ( w->right->color == black && w->left->color == black ) //case2------>go on/stop
{
w->color = red;
x = x->p;
}
elseif ( w->left->color == black) // case3-----> case 4----->stop
{
w->right->color = black;
w->color =red ;
Left_Rotate(&T,w);
w = x->p->left ; //转成case4处理
w->color = x->p->color;
x->p->color = black;
w->left->color = black;
Right_Rotate(&T,x->p);
x = T;
}
else // case4-------------->stop
{
w->color = x->p->color;
x->p->color = black;
w->left->color = black;
Right_Rotate(&T,x->p);
x = T;
}
}
}
x->color = black; //可能由case2退出，那把x涂黑即可，见分析！也可能有case4退出，把根节点涂黑
}
Node * RB_Delete(Node *T ,Node *z)
{
Node * x =NULL;
Node * y =z;
Node *temp=y->p;
enum colors y_original_color = y->color; //记录下删除前z的颜色
if ( z->left == T_NIL) //左子树不存在的情况
{
x = z->right;
RB_Transplant(&T,z,z->right);
}
elseif ( z->right == T_NIL) //右子树不存在
{
x = z->left;
RB_Transplant(&T,z,z->left);
}
else //左右都存在的情况
{
y = Tree_Minimum(z->right); //找到后继y
temp=y->p;
y_original_color = y->color; //记录下y转移前的颜色
x = y->right;
if ( y->p == z) //如果y是z的子结点
{
x->p = y;
}
else
{
RB_Transplant(&T,y,y->right); //如果y不是z的子结点，用y的右子树代替y的位置
y->right = z->right;
y->right->p = y;
}
RB_Transplant(&T,z,y); //y替代z的位置 ，不论y是不是T_NIL
y->left = z->left;
y->left->p = y;
y->color = z->color; //把y的颜色改成z的颜色
y->size =y->left->size+y->right->size+1;
}
while(temp != T_NIL) //从删除的位置或后继的位置向上遍历size--,直到根节点为止
{
temp->size--;
temp = temp->p;
}
if ( y_original_color == black) //判断y的颜色，若为黑色，需要修复
RB_Delete_Fixup(T,x);
return T;
}
Node * Tree_Search(Node *T ,int k) //寻找数k是否在树中，且返回数k的地址
{
while(T !=T_NIL && T->key != k)
{
if ( k < T->key)
T=T->left;
elseT=T->right;
}
if ( T == T_NIL)
{
return NULL;
}
else
{
return T;
}
}
Node * OS_Select(Node *x,int i) //确定以x为根节点的子树，第i小的关键字
{
int r =x->left->size+1;
if (i == r)
return x;
elseif (i < r)
return OS_Select(x->left,i);
else
return OS_Select(x->right,i-r);
}
intOS_Rank(Node *T,Node * x) //确定x在树T中序遍历中的位置顺序
{
int r =x->left->size+1;
Node * y =x;
while(y != T)
{
if (y == y->p->right)
{
r=r+y->p->left->size+1;
}
y = y->p;
}
return r;
}
void main()
{
int A[]={2,5,1,6,3,8,4,9,7};
int length = sizeof(A)/sizeof(A[0]); //数组A的长度
Node *T =Establish(A,length); //建立红黑树，返回根节点T
printf("中序遍历：\n");
Inorder_Tree_Walk(T);printf("\n"); //中序遍历输出
printf("先序遍历：\n"); //先序遍历输出
Pre_Tree_Walk(T);printf("\n");
printf("__%d__\n",OS_Select(T,5)->key);
printf("--%d--\n",OS_Rank(T,Tree_Search(T,3)));
printf("-----------删除操作后-------------\n");
T=RB_Delete(T,Tree_Search(T,2));
T=RB_Delete(T,Tree_Search(T,5));
T=RB_Delete(T,Tree_Search(T,7));
T=RB_Delete(T,Tree_Search(T,4));
printf("中序遍历：\n");
Inorder_Tree_Walk(T);
printf("\n");
printf("先序遍历：\n");
Pre_Tree_Walk(T);
printf("\n");
}
2.区间树
区间树是通过扩张红黑树来构成由区间构成的动态集合。结点的属性由一个关键字key变成了一个区间。 
1.添加附加信息
添加区间信息INT,INT结构包含区间的左右端点。还包含Max属性，它是以自身为根的子树中所有的区间的端点最大值。（上图中虚线下方）
enum colors{red,black};//枚举类型struct Interval //区间
{
int low;
int high;
};
typedefstruct Node
{
struct Node * p;
struct Node *left;
struct Node *right;
enum colors color;
//添加的属性struct Interval INT; //存储结点区间信息 int Max; //以结点为根的所有区间端点的最大值
}Node;
2.修改基本操作
修改红黑树的插入和删除操作维添加的信息，都能保证在O(lgn)的时间内完成；
1.插入操作：
第一步：由于区间树采用区间左端点作为关键字进行插入，遍历时通过比较INT.low的方式插入；插入前令Max=high，插入时从根节点开始遍历到要插入的位置，把遍历的结点的Max与新添加的结点z的Max进行比较，如果z.Max>x.Max ,更新结点的x.Max=z.Max
Node *Interval_Insert(Node *Root,Node * z) //红黑树插入,返回树的根
{
Node * y=T_NIL;
Node * x=Root;
while( x != T_NIL) //找到结点z要插入的位置
{
if ( z->Max> x->Max) //比较新插入的结点z与结点x的Max大小；
{
x->Max= z->Max;
}
y=x;
if (z->INT.low < x->INT.low)
x = x->left;
else
x = x->right;
}
z->p = y;
if ( y == T_NIL) //插入第一个结点作为根节点的情况
Root = z;
elseif (z->INT.low < y->INT.low)
y->left = z;
else
y->right = z;
Root = Interval_Insert_Fixup(Root,z); //插入完毕后，对红黑树的颜色进行修正return Root;
}
第二步：由于左旋右旋会破坏区间的性质，在函数代码后添加更新信息
void Left_Rotate(Node **T,Node * x) //左旋
{
Node *y=x->right;
x->right =y->left;
if (y->left != T_NIL)
y->left->p=x;
y->p=x->p;
if(x->p==T_NIL)
*T=y;
elseif (x == x->p->left)
x->p->left = y;
else
x->p->right = y;
y->left = x;
x->p=y;
y->Max= x->Max; //添加语句维护Max
x->Max= GetMax(x->left->Max,x->right->Max,x->INT.high);
}
void Right_Rotate(Node **T,Node * y) //右旋
{
Node *x=y->left;
y->left =x->right;
if (x->right != T_NIL)
x->right->p=y;
x->p=y->p;
if(y->p==T_NIL)
*T=x;
elseif (y == y->p->left)
y->p->left = x;
else
y->p->right = x;
x->right = y;
y->p=x;
x->Max= y->Max; //添加语句维护Max
y->Max= GetMax(y->left->Max,y->right->Max,y->INT.high);
}
2.删除操作
第一步：被删除的结点z可能会影响整个区间树的性质，如果结点z少于两个孩子，则沿着z上升到根节点为止，对树重新更新维护；如果有两个孩子则从后继出发，进行维护；
while( temp != T_NIL ) //从要删除的结点或其后继开始向上修复区间树
{
temp->Max= GetMax(temp->left->Max,temp->right->Max,temp->INT.high);
temp = temp->p; //每次一层，至多lgn层
}
第二步：同上，也是在左旋右旋函数后添加代码。
3.设计新的操作
判断给定的一个区间i位于区间树的哪个位置。区间之间的关系： 
a重叠的情况；b、c不重叠的情况
不重叠的情况用代码表示为
x->INT.high < i->low
x->INT.low > i->high
如果存在区间与i重叠则返回结点的位置，否则返回T_NIL
Node * Interval_Search(Node *T ,struct Interval *i) //寻找数k是否在树中，且返回数k的地址
{
Node * x = T;
while(x != T_NIL && ((x->INT.high < i->low)||(x->INT.low > i->high))) //不重叠
{
if (x->left != T_NIL && x->left->Max>= i->low) //在其左子树中搜索
{
x = x->left;
}
else
{
x = x->right;
}
}
return x;
}
每次迭代都是一层，至多lgn层；所以耗时O(lgn)的时间
4.完整代码
/*
CSDN 勿在浮砂筑高台
http://blog.csdn.net/luoshixian099
算法导论--区间树2015年5月20日
*/
#include <STDIO.H> #include <STDLIB.H>enum colors{red,black};//枚举类型
structInterval //区间
{
int low;
int high;
};
typedef struct Node
{
struct Node * p;
struct Node *left;
struct Node *right;
enum colors color;
//添加的属性
struct IntervalINT; //存储结点区间信息
int Max; //以结点为根的所有区间端点的最大值
}Node;
Node *T_NIL=NULL; //建立全部变量 T_NILintGetMax(int a,int b,int c) //返回a,b,c最大值
{
return a>b?(a>c?a:c):(b>c?b:c);
}
Node * Tree_Minimum(Node * T) //找最小结点
{
while(T->left != T_NIL)
T=T->left;
return T;
}
voidInorder_Tree_Walk(Node * T) //中序遍历树T,输出
{
if ( T != T_NIL)
{
Inorder_Tree_Walk(T->left); //递归其左孩子
printf("%d",T->INT.low); //输出根的关键字
if (T->color == 0)
{
printf("-R(%d) ",T->Max);
}
else
{
printf("-B(%d) ",T->Max);
}
Inorder_Tree_Walk(T->right); //递归其右孩子
}
}
voidPre_Tree_Walk(Node * T) //
{
if ( T != T_NIL)
{
printf("%d ",T->INT.low); //输出根的关键字
Pre_Tree_Walk(T->left); //递归其左孩子
Pre_Tree_Walk(T->right); //递归其右孩子
}
}
voidLeft_Rotate(Node **T,Node * x) //左旋
{
Node *y=x->right;
x->right =y->left;
if (y->left != T_NIL)
y->left->p=x;
y->p=x->p;
if(x->p==T_NIL)
*T=y;
elseif (x == x->p->left)
x->p->left = y;
else
x->p->right = y;
y->left = x;
x->p=y;
y->Max = x->Max; //添加语句维护Max
x->Max = GetMax(x->left->Max,x->right->Max,x->INT.high);
}
voidRight_Rotate(Node **T,Node * y) //右旋
{
Node *x=y->left;
y->left =x->right;
if (x->right != T_NIL)
x->right->p=y;
x->p=y->p;
if(y->p==T_NIL)
*T=x;
elseif (y == y->p->left)
y->p->left = x;
else
y->p->right = x;
x->right = y;
y->p=x;
x->Max = y->Max; //添加语句维护Max
y->Max = GetMax(y->left->Max,y->right->Max,y->INT.high);
}
Node* Interval_Insert_Fixup(Node *T,Node *z)
{
Node * y=NULL;
while( z->p->color == red) //违反了性质4，迭代进行修正
{
if (z->p == z->p->p->left)
{
y = z->p->p->right;
if ( y->color == red) // case1 叔结点为红色
{
z->p->color = black; //父节点涂黑
y->color = black; //叔结点涂黑
z->p->p->color = red; //祖结点涂红
z = z->p->p; //向上迭代，更新z的位置
}
elseif ( z == z->p->right) //case2 叔结点为黑色且z为双亲的右孩子
{
z = z->p;
Left_Rotate(&T,z);
z->p->color = black; //case2 已转为 case3 继续处理
z->p->p->color = red;
Right_Rotate(&T,z->p->p);// while循环终止
}
else // case3 叔结点为黑色且z为双亲的左孩子
{
z->p->color = black;
z->p->p->color = red;
Right_Rotate(&T,z->p->p);// while循环终止
}
}
else //对称处理
{
y = z->p->p->left;
if ( y->color == red) // case1 叔结点为红色
{
z->p->color = black;
y->color = black;
z->p->p->color = red;
z = z->p->p;
}
elseif ( z == z->p->left) //case2 叔结点为黑色且z为双亲的右孩子
{
z = z->p;
Right_Rotate(&T,z);
z->p->color = black;
z->p->p->color = red;
Left_Rotate(&T,z->p->p);//
}
else // case3
{
z->p->color = black;
z->p->p->color = red;
Left_Rotate(&T,z->p->p);
}
}
}
T->color = black; //保证不会违反性质2，对根节点涂黑
return T;
}
Node *Interval_Insert(Node *Root,Node * z) //红黑树插入,返回树的根
{
Node * y=T_NIL;
Node * x=Root;
while( x != T_NIL) //找到结点z要插入的位置
{
if ( z->Max > x->Max) //比较新插入的结点z与结点x的Max大小；
{
x->Max = z->Max;
}
y=x;
if (z->INT.low < x->INT.low)
x = x->left;
else
x = x->right;
}
z->p = y;
if ( y == T_NIL) //插入第一个结点作为根节点的情况
Root = z;
elseif (z->INT.low < y->INT.low)
y->left = z;
else
y->right = z;
Root = Interval_Insert_Fixup(Root,z); //插入完毕后，对红黑树的颜色进行修正
return Root;
}
Node * Establish(int A[][2],int len) //建立红黑树
{
Node * T,*node;
int i=0;
node=NULL;
T_NIL=(Node *)malloc(sizeof(Node)); //建立T_NIL结点
T_NIL->p=NULL;
T_NIL->left=NULL;
T_NIL->right=NULL;
T_NIL->INT.low=-1;
T_NIL->color=black;
T_NIL->Max=0;
T=T_NIL;
for (i=0;i<len;i++)
{
node =(Node *)malloc(sizeof(Node));
node->p =T_NIL;
node->left=T_NIL;
node->right=T_NIL;
node->INT.low=A[i][0]; //以INT.low左作为关键字
node->INT.high=A[i][1];
node->Max = A[i][1];
node->color=red;
T=Interval_Insert(T,node);
}
return T;
}
voidRB_Transplant(Node **T,Node * u,Node * v) //结点替代函数
{
if (u->p == T_NIL)
*T = v;
elseif (u == u->p->left)
u->p->left = v;
else
u->p->right = v;
v->p = u->p; //此处赋值无条件，v如果是T_NIL也要进行赋值
}
Node* Interval_Delete_Fixup(Node * T,Node * x)
{
Node *w=NULL;
while( x != T && x->color == black) //循环迭代处理
{
if ( x == x->p->left )
{
w = x->p->right;
if (w->color == red) // case1------> case 2 , case 3 ,case 4
{
w->color = black;
x->p->color =red;
Left_Rotate(&T,x->p);
w = x->p->right;
}
if ( w->left->color == black && w->right->color == black ) //case2------>go on / stop
{
w->color = red;
x = x->p;
}
elseif ( w->right->color == black) // case3---->case 4---->stop
{
w->left->color = black;
w->color =red ;
Right_Rotate(&T,w);
w = x->p->right ; //转成case4处理
w->color = x->p->color;
x->p->color = black;
w->right->color = black;
Left_Rotate(&T,x->p);
x = T;
}
else // case4------------------->stop
{
w->color = x->p->color;
x->p->color = black;
w->right->color = black;
Left_Rotate(&T,x->p);
x = T;
}
}
else
{
w = x->p->left;
if (w->color == red) // case1------> case 2 , case 3 ,case 4
{
w->color = black;
x->p->color =red;
Right_Rotate(&T,x->p);
w = x->p->left;
}
if ( w->right->color == black && w->left->color == black ) //case2------>go on/stop
{
w->color = red;
x = x->p;
}
elseif ( w->left->color == black) // case3-----> case 4----->stop
{
w->right->color = black;
w->color =red ;
Left_Rotate(&T,w);
w = x->p->left ; //转成case4处理
w->color = x->p->color;
x->p->color = black;
w->left->color = black;
Right_Rotate(&T,x->p);
x = T;
}
else // case4-------------->stop
{
w->color = x->p->color;
x->p->color = black;
w->left->color = black;
Right_Rotate(&T,x->p);
x = T;
}
}
}
x->color = black; //可能由case2退出，那把x涂黑即可，见分析！也可能有case4退出，把根节点涂黑
return T;
}
Node * Interval_Delete(Node *T ,Node *z)
{
Node * x =NULL;
Node * y =z;
Node * temp = y->p;
enum colors y_original_color = y->color; //记录下删除前z的颜色
if ( z->left == T_NIL) //左子树不存在的情况
{
x = z->right;
RB_Transplant(&T,z,z->right);
}
elseif ( z->right == T_NIL) //右子树不存在
{
x = z->left;
RB_Transplant(&T,z,z->left);
}
else //左右都存在的情况
{
y = Tree_Minimum(z->right); //找到后继y
temp = y->p;
y_original_color = y->color; //记录下y转移前的颜色
x = y->right;
if ( y->p == z) //如果y是z的子结点
{
x->p = y;
}
else
{
RB_Transplant(&T,y,y->right); //如果y不是z的子结点，用y的右子树代替y的位置
y->right = z->right;
y->right->p = y;
}
RB_Transplant(&T,z,y); //y替代z的位置 ，不论y是不是T_NIL
y->left = z->left;
y->left->p = y;
y->color = z->color; //把y的颜色改成z的颜色
}
while( temp != T_NIL ) //从要删除的结点或其后继开始向上修复红黑树
{
temp->Max = GetMax(temp->left->Max,temp->right->Max,temp->INT.high);
temp = temp->p;
}
if ( y_original_color == black) //判断y的颜色，若为黑色，需要修复
T=Interval_Delete_Fixup(T,x);
return T;
}
Node * Tree_Search(Node *T ,int k) //寻找数k是否在树中，且返回数k的地址
{
while(T != T_NIL && T->INT.low != k)
{
if ( k < T->INT.low)
T=T->left;
elseT=T->right;
}
if ( T == T_NIL)
{
return NULL;
}
else
{
return T;
}
}
Node * Interval_Search(Node *T ,struct Interval *i) //寻找数k是否在树中，且返回数k的地址
{
Node * x = T;
while(x != T_NIL && ((x->INT.high < i->low)||(x->INT.low > i->high))) //不重叠
{
if (x->left != T_NIL && x->left->Max >= i->low) //在其左子树中搜索
{
x = x->left;
}
else
{
x = x->right;
}
}
return x;
}
void main()
{
int A[][2]={0,3, //区间
5,8,
6,10,
8,9,
15,23,
16,21,
17,19,
19,20,
25,30,
26,26};
int length = sizeof(A)/sizeof(A[0]); //数组区间的长度
Node *T,*temp;
struct Interval i;
i.low = 22;
i.high = 25;
T=Establish(A,length); //建立红黑树，返回根节点T
printf("中序遍历：\n");
Inorder_Tree_Walk(T);printf("\n"); //中序遍历输出
printf("-----------删除操作后-------------\n");
T=Interval_Delete(T,Tree_Search(T,6));
printf("中序遍历：\n");
Inorder_Tree_Walk(T);
printf("\n");
temp = Interval_Search(T,&i);
printf("____%d___%d__", temp->INT.low,temp->INT.high);
}
原文：http://blog.csdn.net/luoshixian099/article/details/45871023
内容总结
以上是互联网集市为您收集整理的算法导论--动态顺序统计与区间树全部内容，希望文章能够帮你解决算法导论--动态顺序统计与区间树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】