欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言實現(xiàn)紅黑樹的實例代碼

 更新時間：2013年12月11日 15:43:05   作者：  
這篇文章主要介紹了C語言實現(xiàn)紅黑樹的實例代碼，有需要的朋友可以參考一下

因為看內(nèi)核的時候感覺紅黑樹挺有意思的，所以利用周末的時間來實現(xiàn)一下玩玩。紅黑樹的操作主要是插入和刪除，而刪除的時候需要考慮的情況更多一些。具體的操作就不在這里羅嗦了，百度文庫里面有一個比較有好的文章，已經(jīng)說的很明白了。

在看具體的操作的時候有的人可能感覺有些情況是沒有考慮到的（如果沒有這種感覺的人很有可能根本沒有仔細(xì)地想）。但是那些“遺漏”的情況如果存在的話，操作之前的紅黑樹將違反那幾個規(guī)則。

寫代碼的時候很多次因為少考慮情況而導(dǎo)致錯誤，細(xì)節(jié)比較多，剛開始rb_node中沒有指向父節(jié)點的指針，寫的快吐血，然后還是加上了。代碼具體的含義可以結(jié)合文章和注釋來看（還是很好理解的）。下面的代碼中可能還有沒有考慮到的細(xì)節(jié)，歡迎拍磚。

復(fù)制代碼 代碼如下:

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

相關(guān)文章

  • C++程序檢測內(nèi)存泄漏的方法分享

    C++程序檢測內(nèi)存泄漏的方法分享

    這篇文章主要介紹了C++程序檢測內(nèi)存泄漏的方法分享,本文講解了、對象計數(shù)、重載new和delete、Hook Windows系統(tǒng)API、使用DiagLeak檢測等內(nèi)容,需要的朋友可以參考下
    2015-03-03
  • Qt 使用 canon edsdk 實現(xiàn)實時預(yù)覽的示例代碼

    Qt 使用 canon edsdk 實現(xiàn)實時預(yù)覽的示例代碼

    這篇文章主要介紹了Qt 使用 canon edsdk 實現(xiàn)實時預(yù)覽的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-11-11
  • OpenCV4 實現(xiàn)背景分離的詳細(xì)步驟(背景減法模型)

    OpenCV4 實現(xiàn)背景分離的詳細(xì)步驟(背景減法模型)

    背景分離（BS）是一種通過使用靜態(tài)相機(jī)來生成前景掩碼（即包含屬于場景中的移動對象像素的二進(jìn)制圖像）的常用技術(shù)，本文給大家介紹OpenCV4 實現(xiàn)背景分離的詳細(xì)步驟，需要的朋友可以參考下
    2021-09-09
  • 基于C語言自制華容道游戲的示例代碼

    基于C語言自制華容道游戲的示例代碼

    這篇文章主要為大家詳細(xì)介紹了如何利用C語言自制華容道游戲，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)C語言有一定的幫助，感興趣的小伙伴可以跟隨小編一起了解一下
    2023-03-03
  • 利用Matlab制作一個賊簡單的粒子圣誕樹

    利用Matlab制作一個賊簡單的粒子圣誕樹

    圣誕節(jié)快到了,本文用Matlab繪制了圣誕樹祝你們圣誕節(jié)快樂,所以下面這篇文章主要給大家介紹了關(guān)于如何利用Matlab制作一個賊簡單的粒子圣誕樹,需要的朋友可以參考下
    2022-12-12
  • 使用C++一步步實現(xiàn)俄羅斯方塊后續(xù)

    使用C++一步步實現(xiàn)俄羅斯方塊后續(xù)

    本文主要給大家分享的是作者在使用C++制作俄羅斯方塊小游戲的時候所需要的常用的函數(shù)，有需要的小伙伴可以借鑒下，希望大家能夠喜歡。
    2017-12-12
  • VS2019配置opencv詳細(xì)圖文教程和測試代碼的實現(xiàn)

    VS2019配置opencv詳細(xì)圖文教程和測試代碼的實現(xiàn)

    這篇文章主要介紹了VS2019配置opencv詳細(xì)圖文教程和測試代碼的實現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-04-04
  • C語言中定義與聲明有哪些區(qū)別

    C語言中定義與聲明有哪些區(qū)別

    在C/C++中有一個基礎(chǔ)且重要的知識，什么是聲明？什么是定義？他們的區(qū)別是什么？本文將帶你理清其中的區(qū)別
    2022-07-07
  • C++實現(xiàn)反轉(zhuǎn)鏈表的兩種方法

    C++實現(xiàn)反轉(zhuǎn)鏈表的兩種方法

    本文主要介紹了C++實現(xiàn)反轉(zhuǎn)鏈表的兩種方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-02-02
  • C語言實現(xiàn)讀取CSV文件的方法詳解

    C語言實現(xiàn)讀取CSV文件的方法詳解

    這篇文章主要為大家詳細(xì)介紹了C語言如何實現(xiàn)讀取CSV文件，文中的示例代碼講解詳細(xì)，具有一定的借鑒價值，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2022-12-12

最新評論