C语言实现红黑树的实例代码_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;
}

时间： 2024-09-14 04:46:17

C语言实现红黑树的实例代码_C 语言的相关文章

基于C语言实现五子棋游戏完整实例代码_C 语言

本文实例讲述了基于C语言实现五子棋游戏的方法,代码备有比较完整的注释,可以帮助读者更好的加以理解. 五子棋游戏代码如下: /* * 使用键盘的上下左右键移动棋盘,空格键表示下棋,ESC键退出程序 */ #include <stdio.h> #include <stdlib.h> #include <bios.h> #include <graphics.h> #include<malloc.h> /* * 对应键盘键的十六进制数字 */ #defi

C语言选择排序算法及实例代码_C 语言

选择排序是排序算法的一种,这里以从小到大排序为例进行讲解. 基本思想及举例说明 选择排序(从小到大)的基本思想是,首先,选出最小的数,放在第一个位置:然后,选出第二小的数,放在第二个位置:以此类推,直到所有的数从小到大排序. 在实现上,我们通常是先确定第i小的数所在的位置,然后,将其与第i个数进行交换. 下面,以对 3  2  4  1 进行选择排序说明排序过程,使用min_index 记录当前最小的数所在的位置. 第1轮 排序过程 (寻找第1小的数所在的位置) 3  2  4  1(最初, m

基于C语言实现的贪吃蛇游戏完整实例代码_C 语言

本文以实例的形式讲述了基于C语言实现的贪吃蛇游戏代码,这是一个比较常见的游戏,代码备有比较详细的注释,对于读者理解有一定的帮助. 贪吃蛇完整实现代码如下: #include <graphics.h> #include <conio.h> #include <stdlib.h> #include <dos.h> #define NULL 0 #define UP 18432 #define DOWN 20480 #define LEFT 19200 #defi

C语言之实现控制台光标随意移动的实例代码_C 语言

原理引入windows.h,首先是要获得输入的东西,然后通过判断: 1.方向键:执行上下左右的移动功能 2 .回车键:执行换行的功能. 3.普通键:输入功能. 终点就是要获取到屏幕上的坐标,当按下了方向键以后,坐标值+1,或者减一,从而实现了光标的自由移动. //C语言实现控制台中光标随意移动 #include <stdio.h> #include <windows.h> #include <conio.h> HANDLE hout; //获得输入 char getIn

C 语言快速排序实例代码_C 语言

快速排序是对冒泡法排序的一种改进. 快速排序算法 的基本思想是:将所要进行排序的数分为左右两个部分,其中一部分的所有数据都比另外一 部分的数据小,然后将所分得的两部分数据进行同样的划分,重复执行以上的划分操作,直 到所有要进行排序的数据变为有序为止. 可能仅根据基本思想对快速排序的认识并不深,接下来以对n个无序数列A[0], A[1]-, A[n-1]采用快速排序方法进行升序排列为例进行讲解. (1)定义两个变量low和high,将low.high分别设置为要进行排序的序列的起始元素和最后一个元

使用C++的string实现高精度加法运算的实例代码_C 语言

对于超大数字的运算,用long long int仍然不能解决,这时候就需要考虑通过模拟运算和数组存储来实现高精度运算. 本文讨论借助C++的string来实现高精度的运算. 首先输入的量直接存储为string,设为s1和s2. 接下来设计一个反转函数,用于把整个字符串反转(为了方便后续计算). string reverseStr(string input){ string output = ""; for(int i = 0; i < input.length(); i++){

C++ 继承详解及实例代码_C 语言

C++继承可以是单一继承或多重继承,每一个继承连接可以是public,protected,private也可以是virtual或non-virtual.然后是各个成员函数选项可以是virtual或non-virtual或pure virtual.本文仅仅作出一些关键点的验证. public继承,例如下: 1 class base 2 {...} 3 class derived:public base 4 {...} 如果这样写,编译器会理解成类型为derived的对象同时也是类型为base的对象

c语言实现输入一组数自动从大到小排列的实例代码_C 语言

如下所示: #include <stdio.h> main() { int x; printf("请输入要排序数字个数:"); scanf("%d",&x); int i,j,k,a,b,num[x]; printf("输入数据:"); for(i=0;i<x;i++) scanf("%d",&num[i]); for(j=0;j<x;j++) { for(k=j+1;k<x;k+

VC++简单实现关机、重启计算机实例代码_C 语言

本文以一个实例形式介绍了VC++简单实现关机.重启计算机的方法,代码比较实用,有一定的参考价值.完整实例代码如下: void CWebBrowserView::OnMenuShutdown() { // TODO: 在此添加命令处理程序代码 if (AfxMessageBox("确定要关机吗?",MB_YESNO) == IDYES) { HANDLE hToken; TOKEN_PRIVILEGES tkp; // Get a token for this process. if (