|
- UID
- 1029342
- 性别
- 男
|
最后附上一个我自己用C写的红黑树操作。插入操作验证无误，删除操作验证次数有限，可能有bug存在。
复制代码 代码如下:
#include <stdlib.h>
#include <stdio.h>
#define T_nil -1
//T_nil is a key of nil[T] in the book.
#define RED 1
#define BLACK 0//T_nil is BLACK
//T_nil's p is itself. need to set.
struct rb_tree {
int color;
int key; //normally a positive number.
struct rb_tree *left;
struct rb_tree *right;
struct rb_tree *p;
};
int rb_walk(struct rb_tree *node) {
if (node->key != T_nil) {
rb_walk(node->left);
printf("%d, color is %s\n",node->key,(node->color?"RED":"BLACK"));
rb_walk(node->right);
}
return 1;
}
struct rb_tree* rb_search(struct rb_tree *node, int k) {
if ((node->key == T_nil) || (node->key == k))
return node;
if ( k < node->key )
return rb_search(node->left,k);
else
return rb_search(node->right,k);
}
struct rb_tree* tree_minimum(struct rb_tree *node) {
if (node->key == T_nil)
return node;
while (node->left->key != T_nil)
node = node->left;
return node;
}
struct rb_tree* tree_maximum(struct rb_tree *node) {
if (node->key == T_nil)
return node;
while (node->right->key != T_nil)
node = node->right;
return node;
}
struct rb_tree* tree_successor(struct rb_tree *node) {
struct rb_tree *y;
if (node->right->key != T_nil)
return tree_minimum(node->right);
y = node->p;
while ((y->key != T_nil) && (node == y->right)) {
node = y;
y = y->p;
}
return y;
}
//3 function of below is copy from tree.
struct rb_tree * left_rotate(struct rb_tree *rb, struct rb_tree *x) {
struct rb_tree *y;
//if (x->right->key == T_nil) {
// printf("have no right child,rotation cancel.\n");
// return rb;
//}
y = x->right;
x->right = y->left;
if (y->left->key != T_nil)
y->left->p = x;
y->p = x->p;
if (x->p->key == T_nil)
rb = y;
else if (x == x->p->left)
x->p->left = y;
else
x->p->right = y;
y->left = x;
x->p = y;
return rb;
}
struct rb_tree *right_rotate(struct rb_tree *rb, struct rb_tree *x) {
struct rb_tree *y;
//if (x->left->key == T_nil ) {
// printf("have no left child,rotation cancel.\n");
// return rb;
//}
y = x->left;
x->left = y->right;
if (y->right->key != T_nil )
y->right->p = x;
y->p = x->p;
if (x->p->key == T_nil)
rb = y;
else if (x == x->p->left)
x->p->left = y;
else
x->p->right = y;
y->right = x;
x->p = y;
return rb;
}
struct rb_tree* rb_insert_fixup(struct rb_tree *rb, struct rb_tree *z) {
struct rb_tree *y;
while (z->p->color == RED) {
if (z->p == z->p->p->left) {
y = z->p->p->right;
if (y->color == RED) {
z->p->color = BLACK;
y->color = BLACK;
z->p->p->color = RED;
z = z->p->p;
}
else {
if (z == z->p->right) {
z= z->p;
rb = left_rotate(rb,z);
}
z->p->color = BLACK;
z->p->p->color = RED;
rb = right_rotate(rb,z->p->p);
}
}
else {//same as right and left exchanged
y = z->p->p->left;
if (y->color == RED) {
z->p->color = BLACK;
y->color = BLACK;
z->p->p->color = RED;
z = z->p->p;
}
else {
if (z == z->p->left) {
z= z->p;
rb = right_rotate(rb,z);
}
z->p->color = BLACK;
z->p->p->color = RED;
rb = left_rotate(rb,z->p->p);
}
}
}
rb->color = BLACK;
return rb;
}
struct rb_tree* rb_insert(struct rb_tree *rb, int k) {
struct rb_tree *y = rb->p;
struct rb_tree *x = rb;
struct rb_tree *z;
z= (struct rb_tree *)malloc(sizeof(struct rb_tree));
z->key = k;
while (x->key != T_nil) {
y = x;
if (k< x->key)
x = x->left;
else
x = x->right;
}
z->p = y;
if (y->key == T_nil)
rb = z;
else if (z->key <y->key)
y->left = z;
else
y->right =z;
z->left = rb->p;
z->right = rb->p;
z->color = RED;
return rb_insert_fixup(rb,z);
}
struct rb_tree* rb_delete_fixup(struct rb_tree *rb, struct rb_tree *x) {
struct rb_tree *w;
while ((x !=rb)&&(x->color == BLACK)) {
if (x == x->p->left) {
w = x->p->right;
if (w->color == RED) {
w->color = BLACK;
x->p->color = RED;
left_rotate(rb,x->p);
w = x->p->right;
}
if ((w->left->color == BLACK)&&(w->right->color == BLACK)) {
w->color = RED;
x = x->p;
}
else if (w->right->color == BLACK) {
w->left->color = BLACK;
w->color = RED;
right_rotate(rb,w);
w = x->p->right;
}
w->color = x->p->color;
x->p->color = BLACK;
w->right->color = BLACK;
left_rotate(rb,x->p);
x = rb;
}
else { //same as right and left exchanged
w = x->p->left;
if (w->color == RED) {
w->color = BLACK;
x->p->color = RED;
right_rotate(rb,x->p);
w = x->p->right;
}
if ((w->right->color == BLACK)&&(w->left->color == BLACK)) {
w->color = RED;
x = x->p;
}
else if (w->left->color == BLACK) {
w->right->color = BLACK;
w->color = RED;
left_rotate(rb,w);
w = x->p->left;
}
w->color = x->p->color;
x->p->color = BLACK;
w->left->color = BLACK;
right_rotate(rb,x->p);
x = rb;
}
}
x->color = BLACK;
}
struct rb_tree* rb_delete(struct rb_tree *rb, struct rb_tree *z) {
struct rb_tree *x,*y;
if ((z->left->key == T_nil) || (z->right->key == T_nil))
y = z;
else y = tree_successor(z);
if (y->left->key != T_nil)
x = y->left;
else
x = y->right;
x->p = y->p;
if (y->p->key == T_nil)
rb = x;
else if (y==x->p->left)
y->p->left = x;
else
y->p->right = x;
if (y!=x) //copy y's data to z
z->key = y->key;
if (y->color == BLACK)
rb_delete_fixup(rb,x);
free(y);
return rb;
}
int main () {
struct rb_tree *p,*root;
struct rb_tree tree_nil = {BLACK,T_nil,&tree_nil,&tree_nil,&tree_nil};
root = &tree_nil;
root = rb_insert(root,15);
root = rb_insert(root,5);
root = rb_insert(root,16);
root = rb_insert(root,3);
root = rb_insert(root,12);
root = rb_insert(root,20);
root = rb_insert(root,10);
root = rb_insert(root,13);
root = rb_insert(root,6);
root = rb_insert(root,7);
root = rb_insert(root,18);
root = rb_insert(root,23);
rb_walk(root);
p = rb_search(root,18);
root = rb_delete(root,p);
rb_walk(root);
return 1;
} |
|
