C语言实现红黑树的实例代码
因为看内核的时候感觉红黑树挺有意思的,所以利用周末的时间来实现一下玩玩。红黑树的操作主要是插入和删除,而删除的时候需要考虑的情况更多一些。具体的操作就不在这里罗嗦了,百度文库里面有一个比较有好的文章,已经说的很明白了。
在看具体的操作的时候有的人可能感觉有些情况是没有考虑到的(如果没有这种感觉的人很有可能根本没有仔细地想)。但是那些“遗漏”的情况如果存在的话,操作之前的红黑树将违反那几个规则。
写代码的时候很多次因为少考虑情况而导致错误,细节比较多,刚开始rb_node中没有指向父节点的指针,写的快吐血,然后还是加上了。代码具体的含义可以结合文章和注释来看(还是很好理解的)。下面的代码中可能还有没有考虑到的细节,欢迎拍砖。
#include <stdio.h>
#include <stdlib.h>
const int RED = 0;
const int BLACK = 1;
struct rb_node{
rb_node* lchild, *rchild, *parent;
int key, colour;
};
rb_node* root;
rb_node* get_node(rb_node* parent, int key);
void rb_insert(int key);
rb_node* rb_search(int key);
void rb_delete(int key);
rb_node* clock_wise(rb_node* node);
rb_node* counter_clock_wise(rb_node* node);
void show_rb_tree(rb_node* node);
rb_node* get_node(rb_node* parent, int key){
rb_node *tmp = (rb_node*)malloc(sizeof(rb_node));
tmp->key = key;
tmp->colour = RED;
tmp->parent = parent;
tmp->lchild = tmp->rchild = NULL;
return tmp;
}
rb_node* clock_wise(rb_node* node){
if(node == NULL || node->lchild == NULL)
return NULL;
rb_node *rb_1=node, *rb_2=node->lchild, *rb_3=node->lchild->rchild;
if(rb_1->parent != NULL){
if(rb_1->parent->lchild == rb_1)
rb_1->parent->lchild = rb_2;
else
rb_1->parent->rchild = rb_2;
}else if(rb_1 == root){
root = rb_2;
}
rb_2->parent = rb_1->parent;
rb_1->parent = rb_2;
rb_2->rchild = rb_1;
rb_1->lchild = rb_3;
if(rb_3 != NULL)rb_3->parent = rb_1;
return rb_2;
}
rb_node* counter_clock_wise(rb_node* node){
if(node == NULL || node->rchild == NULL)
return NULL;
rb_node *rb_1=node, *rb_2=node->rchild, *rb_3=node->rchild->lchild;
if(rb_1->parent != NULL){
if(rb_1->parent->lchild == rb_1)
rb_1->parent->lchild = rb_2;
else
rb_1->parent->rchild = rb_2;
}
else if(rb_1 == root){
root = rb_2;
}
rb_2->parent = rb_1->parent;
rb_1->parent = rb_2;
rb_2->lchild = rb_1;
rb_1->rchild = rb_3;
if(rb_3 != NULL)rb_3->parent = rb_1;
return rb_2;
}
rb_node* rb_search(int key){
rb_node *p = root;
while(p != NULL){
if(key < p->key)
p = p->lchild;
else if(key > p->key)
p = p->rchild;
else
break;
}
return p;
}
void rb_insert(int key){
rb_node *p=root, *q=NULL;
if(root == NULL){
root = get_node(NULL, key);
root->colour = BLACK;
return;
}
while(p != NULL){
q = p;
if(key < p->key)
p = p->lchild;
else if(key > p->key)
p = p->rchild;
else return;
}
if(key < q->key)
q->lchild = get_node(q, key);
else
q->rchild = get_node(q, key);
while(q != NULL && q->colour == RED){
p = q->parent;//p won't null, or BUG.
if(p->lchild == q){
if(q->rchild != NULL && q->rchild->colour == RED)
counter_clock_wise(q);
q = clock_wise(p);
q->lchild->colour = BLACK;
}
else{
if(q->lchild != NULL && q->lchild->colour == RED)
clock_wise(q);
q = counter_clock_wise(p);
q->rchild->colour = BLACK;
}
q = q->parent;
}
root->colour = BLACK;
}
void show_rb_tree(rb_node* node){
if(node == NULL)
return;
printf("(%d,%d)\n", node->key, node->colour);
if(node->lchild != NULL){
printf("[-1]\n");
show_rb_tree(node->lchild);
}
if(node->rchild != NULL){
printf("[1]\n");
show_rb_tree(node->rchild);
}
printf("[0]\n");
}
void rb_delete(int key){
rb_node *v = rb_search(key), *u, *p, *c, *b;
int tmp;
if(v == NULL) return;
u = v;
if(v->lchild != NULL && v->rchild != NULL){
u = v->rchild;
while(u->lchild != NULL){
u = u->lchild;
}
tmp = u->key;
u->key = v->key;
v->key = tmp;
}
//u is the node to free.
if(u->lchild != NULL)
c = u->lchild;
else
c = u->rchild;
p = u->parent;
if(p != NULL){
//remove u from rb_tree.
if(p->lchild == u)
p->lchild = c;
else
p->rchild = c;
}
else{
//u is root.
root = c;
free((void*)u);
return;
}
//u is not root and u is RED, this will not unbalance.
if(u->colour == RED){
free((void*)u);
return;
}
free((void*)u);
u = c;
//u is the first node to balance.
while(u != root){
if(u != NULL && u->colour == RED){
//if u is RED, change it to BLACK can finsh.
u->colour = BLACK;
return;
}
if(u == p->lchild)
b = p->rchild;
else
b = p->lchild;
printf("%d\n", b->key);
//b is borther of u. b can't be null, or the rb_tree is must not balance.
if(b->colour == BLACK){
//If b's son is RED, rotate the node.
if(b->lchild != NULL && b->lchild->colour == RED){
if(u == p->lchild){
b = clock_wise(b);
b->colour = BLACK;
b->rchild->colour = RED;
p = counter_clock_wise(p);
p->colour = p->lchild->colour;
p->lchild->colour = BLACK;
p->rchild->colour = BLACK;
}
else{
p = clock_wise(p);
p->colour = p->rchild->colour;
p->rchild->colour = BLACK;
p->lchild->colour = BLACK;
}
return;
}
else if(b->rchild != NULL && b->rchild->colour == RED){
if(u == p->rchild){
b = counter_clock_wise(b);
b->colour = BLACK;
b->lchild->colour = RED;
p = clock_wise(p);
p->colour = p->rchild->colour;
p->rchild->colour = BLACK;
p->lchild->colour = BLACK;
}
else{
p = counter_clock_wise(p);
p->colour = p->lchild->colour;
p->lchild->colour = BLACK;
p->rchild->colour = BLACK;
}
return;
}
else{//if b's sons are BLACK, make b RED and move up u.
b->colour = RED;
u = p;
p = u->parent;
continue;
}
}
else{
if(u == p->lchild){
p = counter_clock_wise(p);
p->colour = BLACK;
p->lchild->colour = RED;
p = p->lchild;
}
else{
p = clock_wise(p);
p->colour = BLACK;
p->rchild->colour = RED;
p = p->rchild;
}
}
}
root->colour = BLACK;
}
int main(){
int i;
root = NULL;
for(i = 1; i <= 10; i++){
rb_insert(i);
}
rb_delete(9);
rb_delete(3);
rb_delete(7);
show_rb_tree(root);
printf("\n");
return 0;
}
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25
C语言正则表达式详解 regcomp() regexec() regfree()用法详解
C语言处理正则表达式常用的函数有regcomp()、regexec()、regfree()和regerror(),这里就为大家介绍一下,需要的朋友可以参考一下啊...2020-04-25- 这篇文章主要介绍了c语言实现找最大值最小值位置查找,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-04