看libuv源碼的時(shí)候能曾，發(fā)現(xiàn)不僅代碼中使用了雙向鏈表，還有一個(gè)伸展樹和紅黑樹的實(shí)現(xiàn)凌简，全部是linux內(nèi)核風(fēng)格的梗夸，數(shù)據(jù)和操作分開，通過宏封裝了指針的操作号醉，實(shí)現(xiàn)的非常精妙反症。
把樹的源碼copy出來，發(fā)現(xiàn)使用起來也非常的簡(jiǎn)單畔派∏Π看看如何使用的吧。
源碼在這里https://github.com/libuv/libuv/blob/v1.x/include/tree.h
由于紅黑樹比伸展樹牛逼线椰，libuv也沒有使用伸展樹胞谈，下面就只聊聊紅黑樹了。
如何使用libuv的紅黑樹
下面的代碼是一個(gè)完整的例子。測(cè)試了插入烦绳，遍歷卿捎，查找，刪除径密，逆向遍歷午阵。
#include "stdafx.h"
#include "tree.h"
#include <malloc.h>
struct node {
RB_ENTRY(node) entry;
int i;
};
int
intcmp(struct node *e1, struct node *e2)
{
return (e1->i < e2->i ? -1 : e1->i > e2->i);
}
RB_HEAD(inttree, node) head = RB_INITIALIZER(&head);
RB_GENERATE(inttree, node, entry, intcmp)
int testdata[] = {
20, 16, 17, 13, 3, 6, 1, 8, 2, 4, 10, 19, 5, 9, 12, 15, 18,
7, 11, 14,30,31,32,33
};
int main()
{
int i;
struct node *n;
for (i = 0; i < sizeof(testdata) / sizeof(testdata[0]); i++) {
if ((n = (struct node *)malloc(sizeof(struct node))) == NULL) {
printf("malloc return null!!!\n");
return -1;
}
n->i = testdata[i];
RB_INSERT(inttree, &head, n);
}
printf("====================RB_FOREACH=========================\n");
RB_FOREACH(n, inttree, &head) {
printf("%d\t", n->i);
}
printf("====================RB_NFIND=========================\n");
{
struct node theNode;
theNode.i = 28;
n = RB_NFIND(inttree, &head, &theNode);
printf("%d\n", n->i);
}
printf("====================RB_FIND=========================\n");
{
struct node theNode;
theNode.i = 20;
n = RB_FIND(inttree, &head, &theNode);
printf("%d\n", n->i);
}
printf("====================RB_REMOVE=========================\n");
{
struct node theNode;
theNode.i = 20;
n = RB_FIND(inttree, &head, &theNode);
printf("find %d first\n", n->i);
n = RB_REMOVE(inttree, &head, n);
printf("remove %d success\n", n->i);
}
printf("====================RB_FOREACH_REVERSE=========================\n");
RB_FOREACH_REVERSE(n, inttree, &head) {
printf("%d\t", n->i);
}
printf("\n");
getchar();
return (0);
}
程序運(yùn)行結(jié)果
可以注意以下幾點(diǎn)
- 數(shù)據(jù)結(jié)構(gòu)的定義
使用RB_ENTRY插入了樹的數(shù)據(jù)結(jié)構(gòu)，而自己的數(shù)據(jù)可以任意定義
struct node {
RB_ENTRY(node) entry;
int i;
};
比較函數(shù)
intcmp實(shí)現(xiàn)了整數(shù)的比較享扔，紅黑樹可以用來排序底桂，可以按優(yōu)先級(jí)取出數(shù)據(jù)，比隊(duì)列的查找速度快惧眠。libuv中的timer和signal都使用了rbt籽懦。RB_GENERATE產(chǎn)生代碼
由于c語言沒有模板，也不是面向?qū)ο蠓湛膊皇侨躅愋偷哪核常酝ㄟ^宏生成各個(gè)不同名字的紅黑樹代碼是非常巧妙的，實(shí)際上和cpp的模板是一個(gè)效果啊秀存。不過用宏來展開代碼沒法用斷點(diǎn)調(diào)試拖云，我想作者是先寫好測(cè)試用例，或者通過打印來調(diào)試应又，最后沒問題在轉(zhuǎn)成宏的吧。另外乏苦，這種方式導(dǎo)致生成的代碼比較多株扛，和模板的缺點(diǎn)是一樣的。宏的技巧
這里的宏都需要傳入名字汇荐，使用了字符串拼接的技術(shù)：比如RB_ENTRY(node) entry;
紅黑樹插入刪除算法
由于算法確實(shí)比較復(fù)雜洞就，以前研究過幾次，現(xiàn)在都記不清楚了掀淘，說明記住算法的步奏確實(shí)是沒有必要的旬蟋，如果想研究算法，確認(rèn)他的效率和正確性革娄，有興趣的可以去看看這篇文章倾贰，我覺得講的還是很清楚的。https://zh.wikipedia.org/wiki/紅黑樹
另外《算法導(dǎo)論》中也對(duì)紅黑樹講的比較多拦惋。
疑問
對(duì)源碼中一個(gè)無用的宏RB_AUGMENT感覺很奇怪匆浙，不知道干什么的。有知道的同學(xué)留言啊厕妖。
#ifndef RB_AUGMENT
#define RB_AUGMENT(x) do {} while (0)
#endif
