紅黑樹 C 實現（含插入修正、中序遍歷、深度統計）

紅黑樹核心性質

1. 節點非紅即黑。
2. 根節點為黑。
3. 葉子節點（NIL）為黑。
4. 紅節點的子節點必為黑（無連續紅）。
5. 任一節點到其所有後代葉子的路徑含相同黑節點數（黑高一致）。

這些性質保證最長路徑不超過最短路徑 2 倍，實現 O(log n) 查找/插入/刪除。

資料結構定義

typedef enum { RED, BLACK } Color;

typedef struct Data { int value; } Data;

typedef struct RBNode {
    Color color;
    Data *data;
    struct RBNode *parent, *left, *right;
} RBNode;

typedef struct { RBNode *root; int size; } RBTree;

關鍵操作：旋轉

旋轉保持 BST 中序序列不變，只調整層級關係。

// 右旋：left 成為新父節點，right 下沉為右子
void rotate_right(RBNode *left, RBNode *right) {
    right->left = left->right;
    if (left->right) left->right->parent = right;
    left->right = right;
    left->parent = right->parent;
    if (right->parent) {
        if (right->parent->left == right) right->parent->left = left;
        else right->parent->right = left;
    }
    right->parent = left;
}

// 左旋：對稱
void rotate_left(RBNode *left, RBNode *right) {
    left->right = right->left;
    if (right->left) right->left->parent = left;
    right->left = left;
    right->parent = left->parent;
    if (left->parent) {
        if (left->parent->right == left) left->parent->right = right;
        else left->parent->left = right;
    }
    left->parent = right;
}

插入與修正

1. 按 BST 規則插入，新節點標紅。
2. 若父節點也為紅，違反性質 4，需 insert_fixup：

• Case 1：叔叔節點紅 → 父、叔變黑，祖父變紅，向上繼續檢查。
• Case 2：叔叔黑且「三角形」（LR 或 RL）→ 先對父旋轉變「直線」，再進 Case 3。
• Case 3：叔叔黑且「直線」（LL 或 RR）→ 父變黑，祖父變紅，對祖父反向旋轉，結束。

代碼中用 curnode、parent、grandparent 指標巡檢，旋轉後更新根節點指標。

遍列與驗證工具

// 中序遍歷：輸出有序序列
void mid_print(RBNode *root, int level) {
    if (!root) return;
    mid_print(root->left, level+1);
    printf("{color=%s, level=%d, val=%d} ",
           root->color==RED?"red":"black", level, root->data->value);
    mid_print(root->right, level+1);
}

// 計算樹深度
int depth(RBNode *root) {
    if (!root) return 0;
    int l = depth(root->left), r = depth(root->right);
    return (l > r ? l : r) + 1;
}

主程式測試

int main() {
    RBTree *tree = calloc(1, sizeof(RBTree));
    int vals[] = {12,24,25,9,4,91,2,100,29,888,10,22,5,11,111,7,13,1,99,222,98,17,8,55,44,33,21,77,199,2345,46,49,51,53,54,52,50,48,47,45,43,42,41,40,39,38,37,78,79,80,81,82,83,84,85};
    for (int i=0; ivalue = vals[i];
        insert(tree, d); // 省略 insert 完整代碼，見上文
    }
    printf("Tree depth: %d\n", depth(tree->root));
    mid_print(tree->root, 0); putchar('\n');
    return 0;
}

輸出深度約 7~8（理論上限 2*log2(65)≈12），中序序列嚴格遞增，驗證 BST 性質與紅黑平衡。

遺留課題：刪除修正

刪除比插入複雜得多（雙黑問題、兄弟節點顏色分析、多種旋轉組合）。建議參考《算法導論》第 13 章或成熟庫（如 Linux kernel rbtree.h、glibc __rb_tree）實現。本文專注插入與驗證框架，為完整實現奠基。