最近因为要给ccache加入红黑树的支持, 找出来曾经实现的代码作为参考, 这才发现原来 的实现都是有问题的,也怪我的测试用例写的不好, 仅仅对插入操作进行了测试, 我向所有因 为阅读了这份代码而造成困惑的朋友表示道歉.
这次重新实现, 所有的代码推倒重新编写, 参考了linux内核中红黑树的实现算法, 并且 对测试用例进行了加强,希望这是最后一个对红黑树算法的修订版本.
/*-----------------------------------------------------------
RB-Tree的插入和删除操作的实现算法
参考资料:
1) <<Introduction to algorithm>>
2) http://lxr.linux.no/linux/lib/rbtree.c
作者：http://www.cppblog.com/converse/
您可以自由的传播，修改这份代码，转载处请注明原作者
红黑树的几个性质:
1) 每个结点只有红和黑两种颜色
2) 根结点是黑色的
3)空节点是黑色的（红黑树中，根节点的parent以及所有叶节点lchild、rchild都不指向NULL，而是指向一个定义好的空节点）。
4) 如果一个结点是红色的,那么它的左右两个子结点的颜色是黑色的
5) 对于每个结点而言,从这个结点到叶子结点的任何路径上的黑色结点
的数目相同
-------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int key_t;
typedef int data_t;
typedef enum color_t
{
RED = 0,
BLACK = 1
}color_t;
typedef struct rb_node_t
{
struct rb_node_t *left, *right, *parent;
key_t key;
data_t data;
color_t color;
}rb_node_t;
/* forward declaration */
rb_node_t* rb_insert(key_t key, data_t data, rb_node_t* root);
rb_node_t* rb_search(key_t key, rb_node_t* root);
rb_node_t* rb_erase(key_t key, rb_node_t* root);
int main()
{
int i, count = 900000;
key_t key;
rb_node_t* root = NULL, *node = NULL;
srand(time(NULL));
for (i = 1; i < count; ++i)
{
key = rand() % count;
if ((root = rb_insert(key, i, root)))
{
printf("[i = %d] insert key %d success!\n", i, key);
}
else
{
printf("[i = %d] insert key %d error!\n", i, key);
exit(-1);
}
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))
{
if ((root = rb_erase(key, root)))
{
printf("[i = %d] erase key %d success\n", i, key);
}
else
{
printf("[i = %d] erase key %d error\n", i, key);
}
}
}
return 0;
}
static rb_node_t* rb_new_node(key_t key, data_t data)
{
rb_node_t *node = (rb_node_t*)malloc(sizeof(struct rb_node_t));
if (!node)
{
printf("malloc error!\n");
exit(-1);
}
node->key = key, node->data = data;
return node;
}
/*-----------------------------------------------------------
| node right
| / \ ==> / \
| a right node y
| / \ / \
| b y a b
--- |
