/*紅黑樹設計與實現
*參考算法導論
*http://www.shnenglu.com/converse/archive/2008/11/10/66530.html
插入時有三種情況（這里只考慮z的父節點是z的祖父節點的左孩子，z的父節點是z的祖父節點的右孩子對稱也一樣）
（1） z的叔叔y是紅色的（改變顏色,提升x）
（2） z的叔叔y是黑色的，而且z是右孩子（左旋）
（3） z的叔叔y是黑色的，而且z是左孩子（右旋加改變顏色）
刪除時有四種情況（這里只考慮z是z的父節點的左孩子，z是z的父節點的右孩子對稱也一樣）
（1）x的兄弟w是紅色的（左旋加改變顏色）
（2）x的兄弟w是黑色的，而且w的兩個孩子都是黑色的（改變顏色，提升x)
（3）x的兄弟w是黑色的，w的左孩子是紅色的，右孩子是黑色的(改變顏色加右旋)
（4）x的兄弟w是黑色的，而且w的右孩子是紅色的（改變顏色加左旋）
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/*定義顏色枚舉類型*/
typedef enum color_t
{
RED=0,
BLACK=1
}color_t;
/*定義結構體*/
typedef struct rb_node_t
{
int key;
color_t color;
struct rb_node_t *left,*right,*parent;
}rb_node_t;
/* 測試是否為紅黑樹*/
int isRedBlackTree(rb_node_t *root,int count)
{
if(root==NULL)
{
printf("黑高度為 %d\n",count);
if(count!=12)/*通過測試該測試用例黑高度為12，不具有普遍性*/
{
printf("not a redblack tree\n");
exit(1);
}
}else{
if(root->color==BLACK)
{
count++;
}
else{
if((root->left!=NULL &&root->left->color==RED)||
(root->right!=NULL && root->right->color==RED))
{
printf("child color RED\n");
}
}
isRedBlackTree(root->left,count);
isRedBlackTree(root->right,count);
}
}
/*中序打印節點用于測試*/
void midPrint(rb_node_t *root)
{
if(root!=NULL)
{
midPrint(root->left);
printf("%d ",root->key);
if(root->color==RED)
printf("RED ");
else
printf("BLACK ");
midPrint(root->right);
}
}
/*先序打印節點用于測試*/
void prePrint(rb_node_t *root)
{
if(root!=NULL)
{
printf("%d ",root->key);
if(root->color==RED)
printf("RED ");
else
printf("BLACK ");
prePrint(root->left);
prePrint(root->right);
}
}
/*創建節點*/
rb_node_t * createNode(int key)
{
rb_node_t *newNode;
if((newNode=malloc(sizeof(rb_node_t)))==NULL)
{
printf("malloc error");
return NULL;
}
newNode->color=RED;
newNode->left=NULL;
newNode->right=NULL;
newNode->key=key;
newNode->parent=NULL;
return newNode;
}
/*左旋*/
rb_node_t * leftRotate(rb_node_t *root,rb_node_t *node)
{
rb_node_t *right;
right=node->right;
if(node->right=right->left)
{
right->left->parent=node;
}
right->left=node;
if(right->parent=node->parent)
{
if(node->parent->left==node)
node->parent->left=right;
else
node->parent->right=right;
}else
root=right;
node->parent=right;
return root;
}
/*右旋*/
rb_node_t *rightRotate(rb_node_t *root,rb_node_t *node)
{
rb_node_t *left;
left=node->left;
if(node->left=left->right)
left->right->parent=node;
left->right=node;
if(left->parent=node->parent)
{
if(node->parent->left==node)
node->parent->left=left;
else
node->parent->right=left;
}else
root=left;
node->parent=left;
return root;
}
/*查找節點，若找到則返回該節點，若沒找到返回NULL并且將父節點保存到save中*/
rb_node_t * rb_search_auxiliary(int key,rb_node_t *root,rb_node_t **save)
{
rb_node_t *node,*parent;
node=root;
parent=NULL;
while(node)
{
parent=node;
if(node->key<key)
node=node->right;
else if(node->key>key)
node=node->left;
else
return node;
}
if(save)
*save=parent;
return NULL;
}
/*查找節點*/
rb_node_t * rb_search(int key,rb_node_t *root)
{
return rb_search_auxiliary(key,root,NULL);
}
/*插入節點后進行調整，使其滿足紅黑樹性質*/
rb_node_t * rb_insert_reblance(rb_node_t *root,rb_node_t *node)
{
rb_node_t *parent,*uncle,*grandParent,*temp;
while((parent=node->parent)&&(parent->color==RED))
{
grandParent=parent->parent;
if(parent==grandParent->left)
{
uncle=grandParent->right;
if(uncle!=NULL && uncle->color==RED)
{
parent->color=BLACK;
uncle->color=BLACK;
grandParent->color=RED;
node=grandParent;
}else{
if(node==parent->right)
{
root=leftRotate(root,parent);
temp=parent;
parent=node;
node=temp;
}
//printf("##########\n");
//print(root);
//printf("\n");
parent->color=BLACK;
grandParent->color=RED;
root=rightRotate(root,grandParent);
//printf("##########\n");
// print(root);
// printf("\n");
}
}else{
uncle=grandParent->left;
if(uncle!=NULL && uncle->color==RED)
{
parent->color=BLACK;
uncle->color=BLACK;
grandParent->color=RED;
node=grandParent;
}else{
if(node==parent->left)
{
root=rightRotate(root,parent);
temp=parent;
parent=node;
node=temp;
}
parent->color=BLACK;
grandParent->color=RED;
root=leftRotate(root,grandParent);
}
}
}
root->color=BLACK;
return root;
}
/*紅黑樹插入節點*/
rb_node_t * rb_insert(rb_node_t *root,int key)
{
rb_node_t *parent,*newNode;
newNode=createNode(key);
if(rb_search_auxiliary(key,root,&parent)!=NULL)
{
printf("already exixt\n");
return root;
}
if(parent==NULL)
{
root=newNode;
}else{
newNode->parent=parent;
if(parent->key<key)
parent->right=newNode;
else
parent->left=newNode;
}
// print(root);
// printf("\n");
root=rb_insert_reblance(root,newNode);
return root;
}
/*刪除黑節點后進行調整，使其滿足紅黑樹性質*/
rb_node_t *rb_delete_reblance(rb_node_t *root,rb_node_t *node,rb_node_t *parent)
{
rb_node_t *brother;
while((node==NULL ||node->color==BLACK)&&((node!=root)))
{
if(node==parent->left)
{
brother=parent->right;
if(brother->color==RED)
{
brother->color=BLACK;
parent->color=RED;
root=leftRotate(root,parent);
brother=parent->right;
}
if((!brother->left || brother->left->color==BLACK)&&
(!brother->right || brother->right->color==BLACK))
{
brother->color=RED;
node=parent;
parent=parent->parent;
}else{
if(!brother->right || brother->right->color==BLACK)
{
brother->color=RED;
brother->left->color=BLACK;
root=rightRotate(root,brother);
brother=parent->right;
}
brother->color=parent->color;
parent->color=BLACK;
brother->right->color=BLACK;
root=leftRotate(root,parent);
node=root;
}
}else{
brother=parent->left;
if(brother->color==RED)
{
brother->color=BLACK;
parent->color=RED;
root=rightRotate(root,parent);
brother=parent->left;
}
if((!brother->left ||brother->left->color==BLACK) &&
(!brother->right ||brother->right->color==BLACK))
{
brother->color=RED;
node=parent;
parent=parent->parent;
}else {
if(!brother->left || brother->left->color==BLACK)
{
brother->color=RED;
brother->right->color=BLACK;
root=leftRotate(root,brother);
brother=parent->left;
}
brother->color=parent->color;
parent->color=BLACK;
brother->left->color=BLACK;
root=rightRotate(root,parent);
node=root;
}
}
}
node->color=BLACK;
return root;
}
rb_node_t *rb_delete(rb_node_t *root,int key)
{
rb_node_t *node,*old,*child,*parent;
color_t color;
child=NULL;
if((node=rb_search(key,root))==NULL)
{
printf("not find the node\n");
return root;
}
old=node;
if(node->left!=NULL && node->right!=NULL)
{
node=node->right;
while(node->left!=NULL)
{
node=node->left;
}
child=node->right;
parent=node->parent;
if(child)
child->parent=parent;
if(parent->left==node)
parent->left=child;
else
parent->right=child;
if(node->parent==old)
{
parent=node;
}
color=node->color;
node->left=old->left;
node->right=old->right;
node->color=old->color;
node->parent=old->parent;
if(old->parent)
{
if(old->parent->left==old)
old->parent->left=node;
else
old->parent->right=node;
}else
root=node;
old->left->parent=node;
if(old->right)
old->right->parent=node;
free(old);
}else{
parent=node->parent;
if(node->left!=NULL)
child=node->left;
else
child=node->right;
if(child)
child->parent=parent;
if(parent)
{
if(parent->left==node)
parent->left=child;
else
parent->right=child;
}else
root=child;
color=node->color;
free(node);
}
if(color==BLACK)
rb_delete_reblance(root,child,parent);
return root;
}
int main()
{
int i,count=900000;
int key;
rb_node_t *root=NULL,*node=NULL;
srand(time(NULL));
int num=0;
for(i=1;i<count;++i)
{
key=rand()%count;
if(root=rb_insert(root,key))
{
printf("[i=%d] insert key %d,success!\n",i,key);
}else{
printf("[i=%d] insert key %d error!\n",i,key);
exit(1);
}
// printf("當前樹中節點\n");
// midPrint(root);
// printf("\n");
if((node=rb_search(key,root)))
{
printf("[i=%d] search key %d success!\n",i,key);
}else{
printf("[i=%d] search key %d error!\n",i,key);
exit(1);
}
if(!(i%10))
{
// prePrint(root);
if((root=rb_delete(root,key)))
{
printf("[i=%d] delete key %d success\n",i,key);
}else
{
printf("[i=%d] erase key %d error\n",i,key);
exit(1);
}
}
}
/*printf("#########線序遍歷\n");
prePrint(root);
printf("\n");
printf("$$$$$$$$$中序遍歷\n");
midPrint(root);
printf("\n");
*/
printf("the root color %d\n",root->color);
isRedBlackTree(root,0);
return 0;
}