C語言實現(xiàn)紅黑樹的實例代碼
因為看內核的時候感覺紅黑樹挺有意思的，所以利用周末的時間來實現(xiàn)一下玩玩。紅黑樹的操作主要是插入和刪除，而刪除的時候需要考慮的情況更多一些。具體的操作就不在這里羅嗦了，百度文庫里面有一個比較有好的文章，已經說的很明白了。
在看具體的操作的時候有的人可能感覺有些情況是沒有考慮到的（如果沒有這種感覺的人很有可能根本沒有仔細地想）。但是那些“遺漏”的情況如果存在的話，操作之前的紅黑樹將違反那幾個規(guī)則。
寫代碼的時候很多次因為少考慮情況而導致錯誤，細節(jié)比較多，剛開始rb_node中沒有指向父節(jié)點的指針，寫的快吐血，然后還是加上了。代碼具體的含義可以結合文章和注釋來看（還是很好理解的）。下面的代碼中可能還有沒有考慮到的細節(jié)，歡迎拍磚。
#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;
}
相關文章
Sublime Text 3 實現(xiàn)C語言代碼的編譯和運行(示例講解)
下面小編就為大家?guī)硪黄猄ublime Text 3 實現(xiàn)C語言代碼的編譯和運行(示例講解)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-09-09
c++調用windows鍵盤有好幾種方式，本文就根據(jù)列舉的例子對c++調用windows鍵盤詳細介紹并附上代碼說明,需要的朋友可以參考下面文章的具體內容2021-09-09
C++11的新特性--可變模版參數(shù)（variadic templates）是C++11新增的最強大的特性之一,它對參數(shù)進行了高度泛化，它能表示0到任意個數(shù)、任意類型的參數(shù),這篇文章主要給大家詳細介紹了關于c++11增加的變參數(shù)模板的相關資料,需要的朋友可以參考下2021-08-08
我最早接觸lambda的概念是在matlab中，那時候在做數(shù)值模擬的課題，lambda可以快速定義簡單的函數(shù)，當時覺得好方便。任何語言都有這個功能，下面來看看C++11新引入的lambda是如何使用的吧2023-04-04
C++中fstream,ifstream及ofstream用法淺析
這篇文章主要介紹了C++中fstream,ifstream及ofstream用法,適合C++初學者學習文件流的操作,需要的朋友可以參考下2014-08-08
這篇文章主要為大家詳細介紹了C++中的移動語義和完美轉發(fā)的相關知識,文中的示例代碼講解詳細,對我們深入掌握C++有一定的幫助,感興趣的小伙伴可以跟隨小編一起學習一下2023-12-12
指針和iterator都支持減法運算，指針-指針得到的是兩個指針之間的距離，迭代器-迭代器得到的是兩個迭代器之間的距離2013-10-10
對比C語言中memccpy()函數(shù)和memcpy()函數(shù)的用法
這篇文章主要介紹了對比C語言中memccpy()函數(shù)和memcpy()函數(shù)的用法,二者都是用于復制內存內容,注意區(qū)別,需要的朋友可以參考下2015-08-08
下面小編就為大家?guī)硪黄狢++派生訪問說明符小記(推薦)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-01-01
C++類與對象深入之構造函數(shù)與析構函數(shù)詳解
朋友們好,這篇播客我們繼續(xù)C++的初階學習，現(xiàn)在對我們對C++非常重要的一個知識點做出總結，整理出來一篇博客供我們一起復習和學習,如果文章中有理解不當?shù)牡胤?還希望朋友們在評論區(qū)指出,我們相互學習,共同進步2022-06-06