红黑树实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
typedef struct node
{
int data;
int color;
struct node * parent;
struct node * left;
struct node * right;
}node_t, *node_tp;
static node_tp rb_tab_p = NULL;
void free_tab_s(node_tp node)
{
if(!node)
return;
free_tab_s(node->left);
free_tab_s(node->right);
printf("\nfree data=%d", node->data);
free(node);
}
void free_tab(void)
{
free_tab_s(rb_tab_p);
}
int node_depth(node_tp node, int * blance)
{
int l,r;
if(!node || !node->left || !node->right)
return 0;
l = node_depth(node->left, blance);
r = node_depth(node->right,blance);
if(l - r > 1 || l - r < -1)
{
printf("\n data=%d depth=%d", node->data, r - l);
if(blance && *blance*(*blance) < (r - l)*(r-l))
*blance = r - l;
}
return (l > r? l: r) + 1;
}
int travesal_mid_s(node_tp node)
{
int l,r,depth = node_depth(node,NULL);
if(!node || !node->left || !node->right)
return 0;
l = travesal_mid_s(node->left );
printf(" %d(%d, %d) ", node->data, node->color, depth);
r = travesal_mid_s(node->right);
return l + r + 1;
}
void travesal_mid(void)
{
int count, depth, blance = 0;
depth = node_depth(rb_tab_p, &blance);
printf("\n---------tree is-------------\n");
count = travesal_mid_s(rb_tab_p);
printf("\n-----count=%d--depth=%d--blance=%d----------", count, depth, blance);
}
node_tp find_node(node_tp node, int data)
{
if(!node || !node->left || !node->right)
return node;
else if(node->data > data)
return find_node(node->left, data);
else if(node->data < data)
return find_node(node->right, data);
else
return node;
}
node_tp max_node(node_tp node)
{
if(!node || !node->right || !node->right->right)
return node;
return max_node(node->right);
}
void init_node(node_tp node, int data, int color)
{
if(!node)
return;
node->data = data;
node->color = color;
node->parent = node->left = node->right = NULL;
}
void left_rotate(node_tp node)
{
node_tp p;
int itmp;
if(node && node->right)
{
if(node->right->color == -1 )
node->right->right->color = -1;
itmp = node->color;
node->color = node->right->color;
node->right->color = itmp;
p = node->right;
node->right = p->left;
p->left = node;
p->parent = node->parent;
if(!p->parent)
rb_tab_p = p;
else
{
if(p->parent->left == node)
p->parent->left = p;
else
p->parent->right = p;
}
node->parent = p;
if(node->right)
node->right->parent = node;
}
}
void right_rotate(node_tp node)
{
node_tp p;
int itmp;
if(node && node->left)
{
if(node->left->color == -1)
node->left->left->color = -1;
itmp = node->color;
node->color = node->left->color;
node->left->color = itmp;
p = node->left;
node->left = p->right;
p->right = node;
p->parent = node->parent;
if(!p->parent)
rb_tab_p = p;
else
{
if(p->parent->left == node)
p->parent->left = p;
else
p->parent->right = p;
}
node->parent = p;
if(node->left)
node->left->parent = node;
}
}
void left_right_rotate(node_tp node)
{
node_tp p;
int itmp;
if(node && node->left && node->left->right)
{
itmp = node->color;
node->color = node->left->right->color;
node->left->right->color = itmp;
node->color = node->left->color;
p = node->left->right;
node->left->right = p->left;
p->left = node->left;
node->left = p->right;
p->right = node;
p->parent = node->parent;
if(!p->parent)
rb_tab_p = p;
else
{
if(p->parent->left == node)
p->parent->left = p;
else
p->parent->right = p;
}
p->left->parent = p;
p->right->parent = p;
if(p->left->right)
p->left->right->parent = p->left;
if(p->right->left)
p->right->left->parent = p->right;
}
}
void right_left_rotate(node_tp node)
{
node_tp p;
int itmp;
if(node && node->right && node->right->left)
{
itmp = node->color;
node->color = node->right->left->color;
node->right->left->color = itmp;
node->color = node->right->color;
p = node->right->left;
node->right->left = p->right;
p->right = node->right;
node->right = p->left;
p->left = node;
p->parent = node->parent;
if(!p->parent)
rb_tab_p = p;
else
{
if(p->parent->left == node)
p->parent->left = p;
else
p->parent->right = p;
}
p->left->parent = p;
p->right->parent = p;
if(p->left->right)
p->left->right->parent = p->left;
if(p->right->left)
p->right->left->parent = p->right;
}
}
int insert_rotate_type(node_tp node)
{
if(node && node->parent->right == node && node->parent->parent->right ==node->parent)
return -1;
else if(node && node->parent->left == node && node->parent->parent->left ==node->parent)
return 1;
else if(node && node->parent->right == node && node->parent->parent->left ==node->parent)
return -2;
else if(node && node->parent->left == node && node->parent->parent->right ==node->parent)
return 2;
else
return 0;
}
void rb_rotate(node_tp node, int type)
{
switch(type)
{
case -1:
left_rotate(node);
break;
case 1:
right_rotate(node);
break;
case -2:
left_right_rotate(node);
break;
case 2:
right_left_rotate(node);
break;
default:
break;
}
}
void insert_rb_rotate(node_tp node)
{
printf("\n11");
rb_rotate(node->parent->parent, insert_rotate_type(node));
}
void insert_color_adjust(node_tp node)
{
node_tp p;
if(!node)
return;
else if(!node->parent)
{
node->color = -1;
return;
}
if(node->color == 1 && node->parent->color == 1)
{
p = node->parent->parent;
if(p->left->color == p->right->color)
{
p->left->color = p->right->color = -1;
p->color = 1;
node = p;
insert_color_adjust(node);
}
else
insert_rb_rotate(node);
}
}
int insert_node_s(node_tp node, int data)
{
node_tp cur_p, p;
cur_p = find_node(node, data);
if(cur_p && cur_p->left && cur_p->right)
return -1;
if(!cur_p)
{
cur_p = (node_tp)malloc(sizeof(node_t));
assert(cur_p != NULL);
init_node(cur_p, data, -1);
rb_tab_p = cur_p;
}
p = (node_tp)malloc(sizeof(node_t));
assert(p != NULL);
init_node(p, 0,-1);
cur_p->left = p;
p->parent = cur_p;
p = (node_tp)malloc(sizeof(node_t));
assert(p != NULL);
init_node(p, 0,-1);
cur_p->right = p;
p->parent = cur_p;
cur_p->data = data;
cur_p->color = 1;
insert_color_adjust(cur_p);
return 0;
}
int insert_node(int data)
{
return insert_node_s(rb_tab_p, data);
}
int del_rotate_type(node_tp black_p)
{
node_tp parent_p, brother_p;
if(black_p && black_p->parent)
{
parent_p = black_p->parent;
if(parent_p->left == black_p)
brother_p = parent_p->right;
else
brother_p = parent_p->left;
if(brother_p->color == 1 && brother_p == parent_p->right)
return -1;
else if(brother_p->color == 1 && brother_p == parent_p->left)
return 1;
else if(brother_p->color == -1 && brother_p == parent_p->right &&
brother_p->right->color == 1)
return -1;
else if(brother_p->color == -1 && brother_p == parent_p->left &&
brother_p->left->color == 1)
return 1;
else if(brother_p->color == -1 && brother_p == parent_p->right && brother_p->left->color == 1 && brother_p->right->color == -1)
return 2;
else if(brother_p->color == -1 && brother_p == parent_p->left && brother_p->left->color == -1 && brother_p->right->color == 1)
return -2;
}
return 0;
}
void del_rb_rotate(node_tp node)
{
rb_rotate(node->parent, del_rotate_type(node));
}
void del_color_adjust(node_tp black_p)
{
node_tp parent_p, brother_p;
if(!black_p)
return;
else if(black_p == rb_tab_p || black_p->color == 1)
{
black_p->color = -1;
return;
}
parent_p = black_p->parent;
if(parent_p->left == black_p)
brother_p = parent_p->right;
else
brother_p = parent_p->left;
if(brother_p->color == -1 && brother_p->left->color == -1 && brother_p->right->color == -1)
{
brother_p->color = 1;
black_p = black_p->parent;
}
else if(brother_p->color == 1)
{
del_rb_rotate(black_p);
}
else
{
del_rb_rotate(black_p);
black_p = NULL;
}
del_color_adjust(black_p);
}
int del_node_s(node_tp node, int data)
{
node_tp pre_p, cur_p, black_p = NULL;
cur_p = find_node(node, data);
if(!cur_p || !cur_p->left || !cur_p->right)
return -1;
if(!cur_p->left->left)
{
if(cur_p->color == -1)
black_p = cur_p->right;
if(!cur_p->parent)
{
rb_tab_p = cur_p->right;
rb_tab_p->parent = NULL;
}
else
{
if(cur_p->parent->left == cur_p)
cur_p->parent->left = cur_p->right;
else
cur_p->parent->right = cur_p->right;
cur_p->right->parent = cur_p->parent;
}
printf("\nfree data=%d", cur_p->data);
free(cur_p->left);
free(cur_p);
if(!rb_tab_p->left || !rb_tab_p->right)
{
free(rb_tab_p);
rb_tab_p = NULL;
black_p = NULL;
}
}
else
{
pre_p = max_node(cur_p->left);
if(pre_p->color == -1)
black_p = pre_p->left;
cur_p->data = pre_p->data;
if(pre_p->parent->left == pre_p)
pre_p->parent->left = pre_p->left;
else
pre_p->parent->right = pre_p->left;
pre_p->left->parent = pre_p->parent;
printf("\nfree data=%d", pre_p->data);
free(pre_p->right);
free(pre_p);
}
del_color_adjust(black_p);
return 0;
}
int del_node(int data)
{
return del_node_s(rb_tab_p, data);
}
void input_data(void)
{
char str[20];
int data;
int ret;
int i;
for(i = 0; i < 255; i++)
insert_node(i);
while(1)
{
/*
printf("\n\nenter data=");
scanf("%s", str);
if(strncmp(str, "ok", 2) == 0)
break;
ret = sscanf(str, "%d", &data);
if(ret == 1)
{
travesal_mid();
ret = insert_node(data);
if(ret == 0)
printf("\ninsert %d successful", data);
travesal_mid();
}
*/
travesal_mid();
printf("\n\ndel data=");
scanf("%s", str);
if(strncmp(str, "ok", 2) == 0)
break;
ret = sscanf(str, "%d", &data);
if(ret == 1)
{
ret = del_node(data);
if(ret == 0)
printf("\ndel %d successful", data);
travesal_mid();
}
}
free_tab();
}
int main(int argc, char **argv)
{
input_data();
return 0;
}