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;
}

(0)

相关推荐

  • 数据结构之红黑树详解

    1.简介 红黑树是一种自平衡二叉查找树.它的统计性能要好于平衡二叉树(AVL树),因此,红黑树在很多地方都有应用.在C++ STL中,很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化,这些修改提供了更好的性能,以及对set操作的支持).它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除等操作. 本文介绍了红黑树的基本性质和基本操作. 2.红黑树

  • Linux内核中红黑树算法的实现详解

    一.简介 平衡二叉树(BalancedBinary Tree或Height-Balanced Tree) 又称AVL树.它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1.若将二叉树上结点的平衡因子BF(BalanceFactor)定义为该结点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有结点的平衡因子只可能是-1.0和1.(此段定义来自严蔚敏的<数据结构(C语言版)>) 红黑树 R-B Tree,全称是Red-B

  • 红黑树的使用详解

    (学习的参考资料主要是<算法导论>) 首先是红黑树的性质.一棵二叉查找树满足以下的红黑性质,则为一棵红黑树. 1)每个结点或是红的,或是黑的. 2)根结点是黑的. 3)每个叶结点(NIL)是黑的. 4)红结点的两个孩子都是黑的. 5)对任意结点,从它到其子孙结点所有路径上包含相同数目的黑结点. 初学时并不在意,但是仔细研究相关算法就会知道,算法都是围绕保持这些性质来进行的.性质5)保证了红黑树使用时的高效.定理证明了n个内结点的红黑树高度至多为2lg(n+1). 不同于一般二叉查找树,红黑树一

  • Linux内核模块和驱动的编写

    Linux内核是一个整体是结构,因此向内核添加任何东西,或者删除某些功能,都十分困难.为了解决这个问题引入了内核机制.从而可以动态的想内核中添加或者删除模块. 模块不被编译在内核中,因而控制了内核的大小.然而模块一旦被插入内核,他就和内核其他部分一样.这样一来就会曾家一部分系统开销.同时,如果模块出现问题,也许会带来系统的崩溃. 模块的实现机制: 启动时,由函数 void inti_modules() 来初始化模块,因为启动事很多时候没有模块.这个函数往往把内核自身当作一个虚模块. 如由系统需要

  • 详解Linux内核中的container_of函数

    前言 在linux 内核中,container_of 函数使用非常广,例如 linux内核链表 list_head.工作队列work_struct中. 在linux内核中大名鼎鼎的宏container_of() ,其实它的语法很简单,只是一些指针的灵活应用,它分两步: 第一步,首先定义一个临时的数据类型(通过typeof( ((type *)0)->member )获得)与ptr相同的指针变量__mptr,然后用它来保存ptr的值. 第二步,用(char *)__mptr减去member在结构体

  • SYN Cookie在Linux内核中的实现

    概述 在目前以IPv4为支撑的网络协议上搭建的网络环境中,SYN Flood是一种非常危险而常见的DoS攻击方式.到目前为止,能够有效防范SYN Flood攻击的手段并不多,而SYN Cookie就是其中最著名的一种.SYN Cookie原理由D. J. Bernstain和 Eric Schenk发明.在很多操作系统上都有各种各样的实现.其中包括Linux.本文就分别介绍一下SYN Flood攻击和SYN Cookie的原理,更重要的是介绍Linux内核中实现SYN Cookie的方式.最后,

  • Linux内核链表实现过程

    关于双链表实现,一般教科书上定义一个双向链表节点的方法如下: 复制代码 代码如下: struct list_node{stuct list_node *pre;stuct list_node *next;ElemType data; } 即一个链表节点包含:一个指向前向节点的指针.一个指向后续节点的指针,以及数据域共三部分.但查看linux内核代码中的list实现时,会发现其与教科书上的方法有很大的差别.来看看linux是如何实现双链表.双链表节点定义 复制代码 代码如下: struct lis

  • 图解红黑树及Java进行红黑二叉树遍历的方法

    红黑树 红黑树是一种数据结构与算法课堂上常常提到但又不会细讲的树,也是技术面试中经常被问到的树,然而无论是书上还是网上的资料,通常都比较刻板难以理解,能不能一种比较直观的方式来理解红黑树呢?本文将以图形的方式来解释红黑树的插入与删除操作. 对树结构的学习是一个递进的过程,我们通常所接触的树都是二叉树,二叉树简单来说就是每个非叶子节点都有且只有两个孩子,分别叫做左孩子和右孩子.二叉树中有一类特殊的树叫二叉查找树,二叉查找树是一种有序的树,对于每个非叶子节点,其左子树的值都小于它,其右子树的值都大于

  • Linux内核漏洞浅析

    与Windows相比,Linux被认为具有更好的安全性和其他扩展性能.这些特性使得Linux在操作系统领域异军突起,得到越来越多的重视.随着Linux应用量的增加,其安全性也逐渐受到了公众甚或黑客的关注.那么,Linux是否真的如其支持厂商们所宣称的那样安全呢?本期我们请到了启明星辰信息技术有限公司积极防御实验室工程师赵伟,对Linux进行专业的漏洞技术分析. Linux内核精短.稳定性高.可扩展性好.硬件需求低.免费.网络功能丰富.适用于多种cpu等特性,使之在操作系统领域异军突起.其独特的魅

  • Linux操作系统内核编译详解

    内核简介 内核,是一个操作系统的核心.它负责管理系统的进程.内存.设备驱动程序.文件和网络系统,决定着系统的性能和稳定性. Linux的一个重要的特点就是其源代码的公开性,所有的内核源程序都可以在/usr/src/linux下找到,大部分应用软件也都是遵循GPL而设计的,你都可以获取相应的源程序代码.全世界任何一个软件工程师都可以将自己认为优秀的代码加入到其中,由此引发的一个明显的好处就是Linux修补漏洞的快速以及对最新软件技术的利用.而Linux的内核则是这些特点的最直接的代表. 

随机推荐