C語言紅黑樹工程庫封裝與簡繁字典實戰

編輯：關於C語言

C語言紅黑樹工程庫封裝與簡繁字典實戰

紅黑樹是高性能關聯容器的核心數據結構（如 Linux 內核 rbtree、STL map/set、Nginx、Redis 等均採用）。本文展示如何從 Linux 內核源碼提煉出一個**可復用、泛型、生產級**的 C 語言紅黑樹庫，並構建一個簡繁中文轉換字典作為實戰演示。

紅黑樹庫設計亮點

侵入式設計：用戶結構體只需在頭部嵌入 struct rbnode __node（宏 _HEAD_RBTREE），零額外內存開銷；
顏色壓縮存儲：利用指針低 2 位對齊特性，將父指針與顏色合併為單一 unsigned long parent_color，節省內存；
行為注冊機制：通過函數指針 new_f/cmp_f/die_f 實現節點創建、比較、銷毀的自定義，極具彈性；
完整操作集：rb_new/insert/remove/get/die，涵蓋生命週期全過程。

核心數據結構（`rbtree.h`）

struct rbnode {
    unsigned long parent_color;  // 父指針 | 顏色(bit0)
    struct rbnode *right, *left;
};

#define _HEAD_RBTREE struct rbnode __node  // 嵌入用戶結構體頭部

typedef void* (*new_f)(void*);   // 節點創建
typedef int   (*cmp_f)(const void*, const void*); // 比較
typedef void  (*die_f)(void*);   // 節點銷毀

typedef struct {
    struct rbnode *root;
    new_f new; cmp_f cmp; die_f die;
} *rbtree_t;

關鍵算法實現節選（`rbtree.c`）

左旋/右旋

static void _rbtree_left_rotate(rbtree_t t, struct rbnode *x) {
    struct rbnode *y = x->right;
    x->right = y->left;
    if (y->left) rb_set_parent(y->left, x);
    rb_set_parent(y, rb_parent(x));
    if (!rb_parent(x)) t->root = y;
    else if (x == rb_parent(x)->left) rb_parent(x)->left = y;
    else rb_parent(x)->right = y;
    y->left = x; rb_set_parent(x, y);
}

插入修正（經典 Case 1/2/3）

static void _rbtree_insert_fixup(rbtree_t t, struct rbnode *z) {
    while (rb_is_red(rb_parent(z))) {
        if (rb_parent(z) == rb_parent(rb_parent(z))->left) { // 父在左
            struct rbnode *y = rb_parent(rb_parent(z))->right; // 叔叔
            if (rb_is_red(y)) { rb_set_black(y); rb_set_black(rb_parent(z)); rb_set_red(rb_parent(rb_parent(z))); z = rb_parent(rb_parent(z)); continue; }
            if (z == rb_parent(z)->right) { z = rb_parent(z); _rbtree_left_rotate(t, z); }
            rb_set_black(rb_parent(z)); rb_set_red(rb_parent(rb_parent(z))); _rbtree_right_rotate(t, rb_parent(rb_parent(z)));
        } else { /* 鏡像對稱 */ }
    }
    rb_set_black(t->root);
}

實戰：簡繁字典（`main.c`）

用戶節點定義

struct dict {
    _HEAD_RBTREE;           // 嵌入 rbnode
    char key[4];   // 簡體（2字節GBK/3字節UTF-8）
    char value[4]; // 繁體
};

行為函數注冊

static void* _dict_new(void *arg) { 
    struct dict *n = malloc(sizeof(struct dict)); 
    *n = *(struct dict*)arg; return n; 
}
static int _dict_cmp(const void *a, const void *b) {
    return strcmp(((struct dict*)a)->key, ((struct dict*)b)->key);
}
static void _dict_die(void *arg) { free(arg); }

構建字典樹

rbtree_t tree = rb_new(_dict_new, _dict_cmp, _dict_die);
FILE *f = fopen("常用漢字簡繁對照表.txt", "rb");
struct dict kv;
while ((c = fgetc(f)) != EOF) {
    kv.key[0] = c; kv.key[1] = fgetc(f); /* 處理製表符、換行符差異 */
    kv.value[0] = fgetc(f); kv.value[1] = fgetc(f); /* 同理 */
    rb_insert(tree, &kv);
}
fclose(f);

查詢演示

const char* dict_get(rbtree_t t, const char *key) {
    struct dict kv; strncpy(kv.key, key, 4);
    struct dict *p = rb_get(t, &kv);
    return p ? p->value : NULL;
}

printf("你好嗎 -> %s%s%s\n", dict_get(tree, "你"), dict_get(tree, "好"), dict_get(tree, "嗎"));