#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include "rbTree.h"
/*初始化红黑树
输入为空
返回值的类型为RBTree
*/
RBTree *Init_RBTree()
{
RBTree *T;
T=(RBTree *)malloc(sizeof(RBTree));//动态分配空间
T->nil=(RBNode *)malloc(sizeof(RBNode));
T->nil->color=Black;
T->nil->key=0;
T->nil->left=NULL;
T->nil->right=NULL;
T->nil->parent=NULL;
T->root=T->nil;
return T;
}
/*初始化结点
返回值类型为RBNode
*/
RBNode *Init_RBNode(int k)
{
RBNode *node;
node=(RBNode *)malloc(sizeof(RBNode));//动态分配空间
node->parent=NULL;
node->left=NULL;
node->right=NULL;
node->key=k;
node->color=Red;
return node;
}
/*左旋*/
void RB_Left_Rotate(RBTree *T,RBNode *x)
{
RBNode *y;//创建一个新结点
y=x->right;
x->right=y->left;
if(y->left!=T->nil)
y->left->parent=x;
y->parent=x->parent;
if(x->parent==T->nil)
T->root=y;
else if(x==x->parent->left)
x->parent->left=y;
else
x->parent->right=y;
y->left=x;
x->parent=y;
}
/*右旋*/
void RB_Right_Rotate(RBTree *T,RBNode *y)
{
RBNode *x;
x=y->left;
y->left=x->right;
if(x->right!=T->nil)
x->right->parent=y;
x->parent=y->parent;
if(y->parent==T->nil)
T->root=x;
else if(y==y->parent->right)
y->parent->right=x;
else
y->parent->left=x;
x->right=y;
y->parent=x;
}
/*查找树中关键字为k的结点,并将其返回*/
RBNode *RBTree_Search(RBTree *T, int k)
{
RBNode *x = T->root;
while(x!=T->nil&&k!=x->key)
{
if(k<x->key)
x=x->left;
else
x=x->right;
}
return x;
}
/*对树进行调整,使其符合树的性质*/
void RB_Insert_Fixup(RBTree *T,RBNode *z)
{
RBNode *y;
while(z->parent->color==Red)
{
if(z->parent==z->parent->parent->left)
{
y=z->parent->parent->right;
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->right)
{
z=z->parent;
RB_Left_Rotate(T,z);
}
z->parent->color=Black;
z->parent->parent->color=Red;
RB_Right_Rotate(T,z->parent->parent);
}
}
else
{
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;
RB_Right_Rotate(T,z);
}
z->parent->color=Black;
z->parent->parent->color=Red;
RB_Left_Rotate(T,z->parent->parent);
}
}
}
T->root->color=Black;
}
/*
插入结点
以树和结点为输入
返回void
*/
void RB_Insert(RBTree *T,RBNode *z)
{
RBNode *x,*y;
y=T->nil;
x=T->root;
while(x!=T->nil)
{
y=x;
if(z->key<x->key)
x=x->left;
else
x=x->right;
}
z->parent=y;
if(y==T->nil)
T->root=z;
else
{
if(z->key<y->key)
y->left=z;
else
y->right=z;
}
z->left=T->nil;
z->right=T->nil;
z->color=Red;
RB_Insert_Fixup(T,z);
}
/*对树进行调整,使其符合树的性质*/
void RB_Delete_Fixup(RBTree *T,RBNode *x)
{
RBNode *w;
while((x!=T->root)&&(x->color==Black))
{
if(x==x->parent->left)
{
w=x->parent->right;
if(w->color==Red)
{
w->color=Black;
x->parent->color=Red;
RB_Left_Rotate(T,x->parent);
w=x->parent->right;
}
if((w->left->color==Black)&&(w->right->color==Black))
{
w->color=Red;
x=x->parent;
}
else
{
if(w->right->color==Black)
{
w->left->color=Black;
w->color=Red;
RB_Right_Rotate(T,w);
w=x->parent->right;
}
w->color=x->parent->color;
x->parent->color=Black;
w->right->color=Black;
RB_Left_Rotate(T,x->parent);
x=T->root;
}
}
else
{
w=x->parent->left;
if(w->color==Red)
{
w->color=Black;
x->parent->color=Red;
RB_Right_Rotate(T,x->parent);
w=x->parent->right;
}
if((w->right->color==Black)&&(w->left->color==Black))
{
w->color=Red;
x=x->parent;
}
else
{
if(w->left->color==Black)
{
w->right->color=Black;
w->color=Red;
RB_Left_Rotate(T,w);
w=x->parent->left;
}
w->color=x->parent->color;
x->parent->color=Black;
w->left->color=Black;
RB_Right_Rotate(T,x->parent);
x=T->root;
}
}
}
x->color=Black;
}
/*查找结点x的最左的孩子,并将其返回*/
RBNode *RB_Tree_Minimum(RBTree *T,RBNode *x)
{
while(x->left!=T->nil)
x=x->left;
return x;
}
/*查找结点x的后继结点*/
RBNode *RB_Tree_Successor(RBTree *T,RBNode *x)
{
RBNode *y;
if(x->right!=T->nil)
return RB_Tree_Minimum(T,x->right);
y=x->parent;
while((y!=T->nil)&&(x==y->right))
{
x=y;
y=y->parent;
}
return y;
}
/*
删除结点
以树和结点为输入
返回void
*/
void RB_Delete(RBTree *T,RBNode *z)
{
RBNode *x,*y;
if((z->left==T->nil)||(z->right==T->nil))
y=z;
else
y=RB_Tree_Successor(T,z);
if(y->left!=T->nil)
x=y->left;
else
x=y->right;
x->parent=y->parent;
if(y->parent==T->nil)
T->root=x;
else
{
if(y=y->parent->left)
y->parent->left=x;
else
y->parent->right=x;
}
if(y!=z)
z->key=y->key;
if(y->color==Black)
RB_Delete_Fixup(T,x);
}
/*按照规定要求打印顺序统计树
level 树的深度,初始根结点深度为0
*/
int level = 0;
void Print_RBTree(RBNode *node,RBNode *nil)
{
int i;
printf("\n");
for(i=0;i<level;i++)
printf(" ");
if(node==nil)
printf("NIL");
else
{
printf("(%d%c,",node->key,(node->color==Red)?'R':'B');//打印结点的关键字和颜色
level++;//到树的下一层
Print_RBTree(node->left,nil);
Print_RBTree(node->right,nil);
level--;//回到树的下一层
if(node->right==nil)//结点右孩子为nil,则打印
printf(")\n");
else
{
for(i=0;i<level;i++)
printf(" ");
printf(")\n");
}
}
}
/*计算黑高度*/
void Black_Height(RBNode *node,RBNode *nil,int BH)
{
/*
因为任意路径从根结点到哨兵的黑高度相同
这里遍历最左的路径的结点,颜色为黑则BH自增1
*/
if(node->color==Black)
BH++;
if(node!=nil)
Black_Height(node->left,nil,BH);
if(node==nil)
{
BH--;
printf("%d",BH);
}
}