用 C Macro 實作的紅黑樹 (Red-black tree) 很經典,不過每次都忘記怎麼用... XD
紅黑樹是平衡二元搜尋樹的一種,除了二元搜尋樹有的結構外,節點的資訊多了顏色。然後利用顏色達到平衡的特性。
先定義單一節點的資料結構:
struct element {
char *key;
int value1;
char *value2;
RB_ENTRY(element) meta;
};
紅黑樹的每個節點都需要紀錄母、左、右節點的指標,以及顏色,其中 RB_ENTRY()
所代表的資料結構會負責紀錄這些值。
再來是定義母節點的資料結構,這樣之後就可以使用 struct tree tree1;
、struct tree tree2;
、struct tree tree3;
產生許多 tree 了:
RB_HEAD(tree, element);
這樣就會產生 struct tree
這個資料結構。如果只用一次可以偷懶寫成:
RB_HEAD(tree, element) tree1;
定義完資料結構後,接著比較函數 (要如何在兩個元素之間挑出大的那個):
int element_cmp(struct element *a, struct element *b)
{
return strcmp(a->key, b->key);
}
接著就可以產生 C 語言的 function prototype,以及實際的 function:
RB_PROTOTYPE(tree, element, meta, element_cmp);
RB_GENERATE(tree, element, meta, element_cmp);
然後程式裡面就可以這樣初始化:
struct tree tree1;
RB_INIT(&tree1);
其中 tree1
就變成之後所有操作的基礎。
增加元素:
struct element *el;
el = malloc(sizeof(struct element));
el->key = strdup("key1");
el->value1 = 1;
el->value2 = strdup("value2");
RB_INSERT(tree, &tree1, el);
如果要尋找的話可以用 RB_FIND()
:
el->key = "key2";
pointer = RB_FIND(tree, &tree1, el);
其他的就翻 tree.h
檔裡面類推...