Tag: c

用 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 檔裡面類推...