rbtree.h
#ifndef _RBTREE_H #define _RBTREE_H typedef int value_type; typedef bool color_type; const color_type red = true; const color_type black = false; typedef struct node { value_type value; color_type color; struct node * parent; struct node * left; struct node * right; } Node; typedef struct Tree { Node * root; } Tree; void rb_init(Tree * tree); void rb_insert(const value_type value, Tree * tree); void rb_remove(const int key, Tree * tree); void rb_treaverse(Tree * tree, void (*func)(Node * x) ); #endif //_RBTREE_H
rbtree.c
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include "rbtree.h" static Node * nil; static Node * make_node(); static Node * make_nil(); static Node * make_new(const value_type value); static Node * search_node(const int key, Tree * tree); static void treaverse_node(Node * x, void (*func)(Node * x) ); static void insert_fixup(Node * x, Tree * tree); static void remove_fixup(Node * x, Node * y, Tree * tree); static void left_rotate(Node * x, Tree * tree); static void right_rotate(Node * x, Tree * tree); static void assign(Node * x, Node * y); void rb_init(Tree * tree) { nil = make_nil(); tree->root = nil; } void rb_insert(const value_type value, Tree * tree) { Node * new_node;//新节点 Node * x = search_node(value, tree);//插入点 if ( x == nil ) { tree->root = make_new(value); tree->root->color = black;//根节点为黑色 } else { if ( x->value == value )//关键字不可重复 return; new_node = make_new(value); if ( value < x->value )//将新节点插入二叉树中 x->left = new_node; else x->right = new_node; new_node->parent = x;//设置新节点的父亲 if ( x->color == red )//如果新节点的父亲为红色,调整 insert_fixup(new_node, tree); } } void rb_remove(const int key, Tree * tree) { Node * x, * y, * z;//x是删除点,y是真正的删除点,z是y的子节点 x = search_node(key, tree); if ( x == nil || x->value != key ) return; if ( x->left != nil && x->right != nil )//找到真正的删除节点 { y = x->right; while ( y->left != nil ) y = y->left; } else y = x; if ( y->left != nil ) z = y->left; else z = y->right; if ( y == tree->root ) { tree->root = z; z->parent = nil; } else { if ( y == y->parent->left ) y->parent->left = z; else y->parent->right = z; if ( z != nil ) z->parent = y->parent; } assign(x, y); if ( y->color == black ) remove_fixup(z, y->parent, tree); free(y); } void rb_treaverse(Tree * tree, void (*func)(Node * x) ) { printf("root value = %10d ", tree->root->value); treaverse_node(tree->root, func); } static Node * make_nil() { Node * x = make_node(); x->color = black; return x; } static Node * make_new(const value_type value) { Node * x = make_node(); x->value = value; x->color = red; x->parent = x->left = x->right = nil; return x; } static Node * make_node() { Node * new_node; new_node = (Node *)malloc( sizeof(Node) ); assert( new_node != NULL ); new_node->parent = new_node->left = new_node->right = NULL; return new_node; } //根节点返回NULL,找到返回当前节点,否则返回x的父亲(x是节点所在的位置) static Node * search_node(const int key, Tree * tree) { Node * x, * y; x = tree->root; y = nil; while ( x != nil ) { y = x; if ( key < x->value ) x = x->left; else if ( key > x->value ) x = x->right; else break; } return y; } static void treaverse_node(Node * x, void (*func)(Node * x) ) { if ( x == nil || x == NULL ) return; else { treaverse_node(x->left, func); func(x); treaverse_node(x->right, func); } } static void insert_fixup(Node * x, Tree * tree) { Node * y;//y是x的伯父节点 while ( x != tree->root && x->parent->color == red ) { if ( x->parent == x->parent->parent->left )//父亲是祖父左孩子 { y = x->parent->parent->right; //case 1: 伯父是红色 //处理办法 // 1.将父亲,伯父变成黑色 // 2.将祖父变成红色 // 3.将祖父设为x，向上检查 if ( y->color == red ) { x->parent->color = black; y->color = black; x->parent->parent->color = red; x = x->parent->parent; } else { //case 2: x是父亲的右孩子 //处理办法: // 1.将x设为x的父亲 // 2.以x为旋转点,左旋 //经过上述操作,转换成case 3 if ( x == x->parent->right ) { x = x->parent; left_rotate(x, tree); } //case 3: x是父亲的左孩子 //处理办法: // 1.将x的父亲设为黑色 // 2.将x的祖父设为红色 // 3.以x的祖父为旋转点,右旋 x->parent->color = black; x->parent->parent->color = red; right_rotate(x->parent->parent, tree); } } else//与上述处理相同,只是将left与right互换 { y = x->parent->parent->left; if ( y->color == red ) { x->parent->color = black; y->color = black; x->parent->parent->color = red; x = x->parent->parent; } else { if ( x == x->parent->left ) { x = x->parent; right_rotate(x, tree); } x->parent->color = black; x->parent->parent->color = red; left_rotate(x->parent->parent, tree); } } }//while end tree->root->color = black; } static void remove_fixup(Node * x, Node * y, Tree * tree) { Node * z;//z是x的兄弟 while ( x != tree->root && x->color == black ) { if ( x == y->left ) { z = y->right; //case 1: 兄弟是红色 //处理方法: // 1.将兄弟设为黑色 // 2.将父亲设为红色 // 3.以父亲为旋转点,左旋 // 4.重置x的兄弟节点 // 变成case 2, 3, 4 if ( z->color == red ) { z->color = black; y->color = red; left_rotate(y, tree); z = y->right; } //case 2: 兄弟是黑色,并且两个孩子是黑色 //处理方法: // 1.将兄弟设为红色 // 2.将x设为父亲 if ( z->left->color == black && z->right->color == black ) { z->color = red; x = y; y = x->parent; } //case 3: 兄弟是黑色,左孩子是红色,右孩子是黑色 //处理方法; // 1.将兄弟的左孩子设为黑色 // 2.将兄弟设为红色 // 3.以兄弟为旋转点,右旋 // 4.重新设置兄弟节点 else { if ( z->right->color == black ) { z->left->color = black; z->color = red; right_rotate(z, tree); z = y->right; } //case 4: 兄弟是黑色,右孩子是红色 //处理方法: // 1.将兄弟的颜色设为父亲的颜色 // 2.将父亲的颜色设为黑色 // 3.将兄弟的右孩子设为黑色 // 4.以父亲为旋转点,左旋 z->color = y->color; y->color = black; z->right->color = black; left_rotate(y, tree); break; } } else { z = y->left; if ( z->color == red ) { y->color = red; z->color = black; right_rotate(y, tree); z = y->left; } if ( z->left->color == black && z->right->color == black ) { z->color = red; x = y; y = x->parent; } else { if ( z->left->color == black ) { z->right->color = black; z->color = red; left_rotate(z, tree); z = y->left; } z->color = y->color; y->color = black; z->left->color = black; right_rotate(y, tree); break; } } } if ( x != nil ) x->color = black; } //左旋 //1.将x的右孩子设为y的左孩子（如果y存在左孩子,将左孩子的父亲设为x) //2.将y的父亲设为x的父亲,将x的父亲的孩子设为y(根据x的情况,考虑左右孩子,是否是根节点) //3.将x的父亲设为y,将y的左孩子设为x static void left_rotate(Node * x, Tree * tree) { Node * y;//y是x的右孩子 y = x->right; x->right = y->left; if ( y->left != nil ) y->left->parent = x; y->parent = x->parent; if ( tree->root != x ) { if ( x == x->parent->left ) x->parent->left = y; else x->parent->right = y; } else tree->root = y; y->left = x; x->parent = y; } //与左旋相反 static void right_rotate(Node * x, Tree * tree) { Node * y; y = x->left; x->left = y->right; if ( y->right != nil ) y->right->parent = x; y->parent = x->parent; if ( tree->root != x ) { if ( x == x->parent->left ) x->parent->left = y; else x->parent->right = y; } else tree->root = y; y->right = x; x->parent = y; } static void assign(Node * x, Node * y) { x->value = y->value; }
main.c
#include <stdio.h> #include <stdlib.h> #include <time.h> #include "rbtree.h" void print(Node * x) { printf("%d ", x->value); if ( x->color == red ) printf("red "); else printf("black "); if ( x->parent ) printf("parent value = %d ", x->parent->value); else printf(" "); } int main(void) { Tree tree; int i; srand(time(NULL)); rb_init(&tree); for ( i = 0; i < 100; i++ ) { rb_insert(rand()%1000, &tree); } rb_treaverse(&tree, print); for ( i = 0; i < 100; i++ ) { rb_remove(rand()%1000, &tree); } // rb_insert(10, &tree); // rb_insert(7, &tree); // rb_insert(8, &tree); // rb_insert(15, &tree); // rb_insert(5, &tree); // rb_insert(6, &tree); // rb_insert(11, &tree); // rb_insert(13, &tree); // rb_insert(12, &tree); // rb_insert(2, &tree); // // rb_treaverse(&tree, print); // rb_remove(5, &tree); // rb_remove(7, &tree); // rb_remove(6, &tree); // rb_remove(8, &tree); // rb_treaverse(&tree, print); // rb_remove(2, &tree); // rb_remove(10, &tree); // rb_remove(11, &tree); // rb_remove(12, &tree); // rb_remove(15, &tree); // rb_remove(13, &tree); rb_treaverse(&tree, print); return 0; }
水平有限，不足之处请大家谅解。欢迎大家指正。