企业官网建设流程全解析

1. 引言

红黑树（Red-Black Tree）是一种自平衡的二叉查找树，通过在节点上附加一个颜色位（红或黑）以及一组约束条件，保证树的高度始终保持在 O(log n)。与 AVL 树相比，红黑树的平衡要求稍弱，因此在插入和删除时需要的旋转次数更少，适用于频繁修改的场景。

本文将带着你手撕一个完整的、泛型的红黑树 C 语言实现。代码支持任意类型的key和value，并提供了初始化、销毁、增删改查等标准接口。我们不仅会贴出核心代码，还会详细分析旋转、插入修复、删除修复等复杂逻辑。

代码文件：rbtree.h、rbtree.c

2. 红黑树性质回顾

红黑树必须满足以下 5 条性质：

1. 每个节点要么是红色，要么是黑色。
2. 根节点是黑色。
3. 所有叶子节点（NIL 哨兵）是黑色。
4. 如果一个节点是红色，那么它的两个子节点都是黑色（即不能出现连续的红色节点）。
5. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点（称为黑高一致）。

这些性质保证了树的最长路径不超过最短路径的两倍，从而保证 O(log n) 的高度。

3. 数据结构设计

3.1 头文件结构 (rbtree.h)

#ifndef RBTREE_H #define RBTREE_H #define RED 1 #define BLACK 2 // 巧妙的宏：为任意类型嵌入父、子、颜色指针 #define TREE_TEMPLATE(name, type) \ struct name { \ struct type *left; \ struct type *right; \ struct type *parent; \ unsigned char color; \ } typedef struct rbtree_node { void *key; void *value; TREE_TEMPLATE(, rbtree_node) tree; } rbtree_node_t; typedef struct rbtree { rbtree_node_t *root; rbtree_node_t *nil; // 哨兵节点，代替 NULL int (*cmp)(const void *, const void *); void (*free_key)(void *); void (*free_value)(void *); } rbtree_t; // 接口声明 int rbtree_init(rbtree_t *rbtree, int (*cmp)(const void *, const void *), void (*free_key)(void *), void (*free_value)(void *)); void rbtree_destory(rbtree_t *rbtree); rbtree_node_t *rbtree_search(rbtree_t *rbtree, void *key); int rbtree_mod(rbtree_t *rbtree, void *key, void *value); int rbtree_insert(rbtree_t *rbtree, void *key, void *value); int rbtree_del(rbtree_t *rbtree, void *key); #endif

设计亮点

• 泛型 key/value：使用void*，由调用者提供比较函数和释放函数。
• 哨兵节点nil：统一表示空节点，避免大量NULL判断，简化代码。
• TREE_TEMPLATE 宏：将左右孩子、父节点、颜色打包成一个结构体，便于维护。

3.2 节点与树的组织

每个rbtree_node_t包含key和value指针，以及一个tree子结构（内含 left/right/parent/color）。这种设计将树的拓扑信息与用户数据分离，清晰且易于扩展。

4. 辅助操作：旋转

旋转是红黑树维持平衡的基本操作，分为左旋和右旋。我们的实现中旋转函数返回int表示错误码（0 成功，负数表示参数错误）。

4.1 左旋

int rbtree_node_left_rotate(rbtree_t *rbtree, rbtree_node_t *x) { if(!rbtree || !x) return -1; rbtree_node_t *y = x->tree.right; if(y == rbtree->nil) return -2; x->tree.right = y->tree.left; if(y->tree.left != rbtree->nil) y->tree.left->tree.parent = x; y->tree.parent = x->tree.parent; if(x->tree.parent == rbtree->nil) rbtree->root = y; else if(x == x->tree.parent->tree.left) x->tree.parent->tree.left = y; else x->tree.parent->tree.right = y; y->tree.left = x; x->tree.parent = y; return 0; }

步骤解析

1. y为x的右孩子。
2. 将y的左子树过继给x的右子树。
3. 更新y的左子树的父指针。
4. 将y的父指针指向x的父节点，并修改祖父节点的孩子链接。
5. 最后将x挂在y的左子树上。

4.2 右旋

对称实现，不再赘述。关键点在于参数y是需要右旋的节点，其左孩子x不能为nil。

5. 插入操作

插入一个新节点分为两个阶段：

1. 标准的 BST 插入（查找插入位置）。
2. 调用rbtree_insert_fixup恢复红黑树性质。

5.1 插入代码

int rbtree_insert(rbtree_t *rbtree, void *key, void *value) { if(!rbtree || !key || !value) return -1; int ret; rbtree_node_t *x = rbtree->root; rbtree_node_t *y = rbtree->nil; // 查找插入位置 while(x != rbtree->nil) { y = x; ret = rbtree->cmp(key, x->key); if(ret > 0) x = x->tree.right; else if(ret < 0) x = x->tree.left; else return 1; // key 已存在 } rbtree_node_t *node = (rbtree_node_t *)malloc(sizeof(rbtree_node_t)); if(!node) return -1; node->key = key; node->value = value; node->tree.parent = y; node->tree.left = rbtree->nil; node->tree.right = rbtree->nil; node->tree.color = RED; // 新节点总是红色 if(y == rbtree->nil) rbtree->root = node; else if(ret > 0) y->tree.right = node; else y->tree.left = node; rbtree_insert_fixup(rbtree, node); return 0; }

关键点

• 新节点染成红色，这样不会破坏黑高性质，但可能产生连续红色节点的冲突。
• 如果 key 已经存在，返回 1（表示冲突），不会覆盖。

5.2 插入修复 (rbtree_insert_fixup)

当新节点的父节点为红色时，需要修复。代码按照《算法导论》的三种情况处理：

void rbtree_insert_fixup(rbtree_t *rbtree, rbtree_node_t *node) { while(node->tree.parent->tree.color == RED) { if(node->tree.parent == node->tree.parent->tree.parent->tree.left) { rbtree_node_t *y = node->tree.parent->tree.parent->tree.right; if(y->tree.color == RED) { // Case 1: 叔叔是红色 -> 变色 y->tree.color = BLACK; node->tree.parent->tree.color = BLACK; node->tree.parent->tree.parent->tree.color = RED; node = node->tree.parent->tree.parent; } else { // Case 2: 叔叔是黑色，且当前节点是右孩子 -> 左旋 if(node == node->tree.parent->tree.right) { node = node->tree.parent; rbtree_node_left_rotate(rbtree, node); } // Case 3: 叔叔是黑色，当前节点是左孩子 -> 右旋 + 变色 node->tree.parent->tree.color = BLACK; node->tree.parent->tree.parent->tree.color = RED; rbtree_node_right_rotate(rbtree, node->tree.parent->tree.parent); } } else { // 对称处理（父节点是祖父的右孩子） rbtree_node_t *y = node->tree.parent->tree.parent->tree.left; if(y->tree.color == RED) { y->tree.color = BLACK; y->tree.parent->tree.color = RED; node->tree.parent->tree.color = BLACK; node = node->tree.parent->tree.parent; } else { if(node == node->tree.parent->tree.left) { node = node->tree.parent; rbtree_node_right_rotate(rbtree, node); } node->tree.parent->tree.color = BLACK; node->tree.parent->tree.parent->tree.color = RED; rbtree_node_left_rotate(rbtree, node->tree.parent->tree.parent); } } } rbtree->root->tree.color = BLACK; }

三种情况图解

最终根节点强制为黑色，保证性质 2。

6. 删除操作

删除是红黑树最复杂的操作。我们的实现遵循以下步骤：

1. 找到要删除的节点z。
2. 确定真正摘除的节点y（最多只有一个孩子）。
3. 用y的孩子x顶替y的位置。
4. 如果y不是z，则用y的数据覆盖z（并释放z的原数据）。
5. 若y是黑色，调用rbtree_delete_fixup修复。
6. 释放y节点。

6.1 删除主体函数

int rbtree_del(rbtree_t *rbtree, void *key) { if (!rbtree || !key) return -1; rbtree_node_t *z = rbtree_search(rbtree, key); if (z == rbtree->nil || !z) return 1; rbtree_node_t *y, *x; // 确定实际要删除的节点 y if (z->tree.left == rbtree->nil || z->tree.right == rbtree->nil) y = z; else { // 找右子树中的最左节点（后继） y = z->tree.right; while (y->tree.left != rbtree->nil) y = y->tree.left; } // x 是 y 的唯一子节点（可能是 nil） if (y->tree.left != rbtree->nil) x = y->tree.left; else x = y->tree.right; // 将 x 链接到 y 的父节点，移除 y x->tree.parent = y->tree.parent; if (y->tree.parent == rbtree->nil) rbtree->root = x; else if (y == y->tree.parent->tree.left) y->tree.parent->tree.left = x; else y->tree.parent->tree.right = x; // 如果 y 不是 z，则用 y 的数据替换 z 的数据 if (y != z) { if (rbtree->free_key) rbtree->free_key(z->key); if (rbtree->free_value) rbtree->free_value(z->value); z->key = y->key; z->value = y->value; y->key = NULL; y->value = NULL; } // 若删除的是黑色节点，需要修复 if (y->tree.color == BLACK) rbtree_delete_fixup(rbtree, x); // 释放 y if (rbtree->free_key && y->key) rbtree->free_key(y->key); if (rbtree->free_value && y->value) rbtree->free_value(y->value); free(y); return 0; }

6.2 删除修复 (rbtree_delete_fixup)

当被删除节点y是黑色时，会导致经过x路径的黑高减少 1。修复函数通过旋转和变色重新平衡。代码处理四种情况（对称处理）：

static void rbtree_delete_fixup(rbtree_t *rbtree, rbtree_node_t *x) { while (x != rbtree->root && x->tree.color == BLACK) { if (x == x->tree.parent->tree.left) { rbtree_node_t *w = x->tree.parent->tree.right; // 兄弟 if (w->tree.color == RED) { // Case 1: 兄弟红色 -> 变色+左旋，转为 Case 2/3/4 w->tree.color = BLACK; x->tree.parent->tree.color = RED; rbtree_node_left_rotate(rbtree, x->tree.parent); w = x->tree.parent->tree.right; } if (w->tree.left->tree.color == BLACK && w->tree.right->tree.color == BLACK) { // Case 2: 兄弟黑色且两个孩子都是黑色 -> 染红兄弟，x上移 w->tree.color = RED; x = x->tree.parent; } else { if (w->tree.right->tree.color == BLACK) { // Case 3: 兄弟黑色，左红右黑 -> 右旋+变色，转为 Case 4 w->tree.left->tree.color = BLACK; w->tree.color = RED; rbtree_node_right_rotate(rbtree, w); w = x->tree.parent->tree.right; } // Case 4: 兄弟黑色，右红 -> 左旋+变色，结束 w->tree.color = x->tree.parent->tree.color; x->tree.parent->tree.color = BLACK; w->tree.right->tree.color = BLACK; rbtree_node_left_rotate(rbtree, x->tree.parent); x = rbtree->root; } } else { // 对称处理（x 是右孩子） rbtree_node_t *w = x->tree.parent->tree.left; if (w->tree.color == RED) { w->tree.color = BLACK; x->tree.parent->tree.color = RED; rbtree_node_right_rotate(rbtree, x->tree.parent); w = x->tree.parent->tree.left; } if (w->tree.right->tree.color == BLACK && w->tree.left->tree.color == BLACK) { w->tree.color = RED; x = x->tree.parent; } else { if (w->tree.left->tree.color == BLACK) { w->tree.right->tree.color = BLACK; w->tree.color = RED; rbtree_node_left_rotate(rbtree, w); w = x->tree.parent->tree.left; } w->tree.color = x->tree.parent->tree.color; x->tree.parent->tree.color = BLACK; w->tree.left->tree.color = BLACK; rbtree_node_right_rotate(rbtree, x->tree.parent); x = rbtree->root; } } } x->tree.color = BLACK; }

删除修复的四种情况

7. 其它接口

7.1 初始化与销毁

int rbtree_init(rbtree_t *rbtree, int (*cmp)(const void *, const void *), void (*free_key)(void *), void (*free_value)(void *)) { if (!rbtree || !cmp) return -1; rbtree->nil = (rbtree_node_t *)malloc(sizeof(rbtree_node_t)); if(!rbtree->nil) return -2; memset(rbtree->nil, 0, sizeof(rbtree_node_t)); rbtree->nil->tree.color = BLACK; rbtree->root = rbtree->nil; rbtree->cmp = cmp; rbtree->free_key = free_key; rbtree->free_value = free_value; return 0; } void rbtree_destory(rbtree_t *rbtree) { if(!rbtree) return; postorder_traversal_destory_rbtree(rbtree, rbtree->root); free(rbtree->nil); rbtree->root = NULL; rbtree->nil = NULL; }

销毁时采用后序遍历递归释放所有节点，并调用用户提供的free_key和free_value释放数据。

7.2 搜索与修改

rbtree_node_t *rbtree_search(rbtree_t *rbtree, void *key) { rbtree_node_t *x = rbtree->root; while(x != rbtree->nil) { int cmp = rbtree->cmp(key, x->key); if(cmp < 0) x = x->tree.left; else if(cmp > 0) x = x->tree.right; else return x; } return rbtree->nil; } int rbtree_mod(rbtree_t *rbtree, void *key, void *value) { rbtree_node_t *x = rbtree_search(rbtree, key); if(x == rbtree->nil) return 1; if(rbtree->free_value) rbtree->free_value(x->value); x->value = value; return 0; }

rbtree_mod先查找，如果存在则释放旧 value 并更新为新值；否则返回 1。

8. 完整使用示例

下面演示如何使用这个红黑树来存储整数 key → 字符串 value。

#include "rbtree.h" #include <stdio.h> #include <stdlib.h> #include <string.h> int cmp_int(const void *a, const void *b) { int ia = *(int*)a; int ib = *(int*)b; return ia - ib; } void free_int(void *p) { free(p); } void free_str(void *p) { free(p); } void inorder_print(rbtree_t *rbtree, rbtree_node_t *node) { if(node == rbtree->nil) return; inorder_print(rbtree, node->tree.left); printf("%d -> %s\n", *(int*)node->key, (char*)node->value); inorder_print(rbtree, node->tree.right); } int main() { rbtree_t tree; // 初始化，比较函数必须提供，释放函数可以为 NULL（如果不需要释放内存） rbtree_init(&tree, cmp_int, free_int, free_str); // 插入若干节点 int *k1 = malloc(sizeof(int)); *k1 = 10; int *k2 = malloc(sizeof(int)); *k2 = 5; int *k3 = malloc(sizeof(int)); *k3 = 15; int *k4 = malloc(sizeof(int)); *k4 = 3; int *k5 = malloc(sizeof(int)); *k5 = 7; rbtree_insert(&tree, k1, strdup("ten")); rbtree_insert(&tree, k2, strdup("five")); rbtree_insert(&tree, k3, strdup("fifteen")); rbtree_insert(&tree, k4, strdup("three")); rbtree_insert(&tree, k5, strdup("seven")); printf("Inorder traversal:\n"); inorder_print(&tree, tree.root); // 查找并修改 int key = 5; rbtree_node_t *node = rbtree_search(&tree, &key); if(node != tree.nil) { printf("\nFound key %d -> %s\n", *(int*)node->key, (char*)node->value); // 修改 value char *new_val = strdup("FIVE"); rbtree_mod(&tree, &key, new_val); printf("After mod: %d -> %s\n", *(int*)node->key, (char*)node->value); } // 删除 key 10 int del_key = 10; rbtree_del(&tree, &del_key); printf("\nAfter deleting 10:\n"); inorder_print(&tree, tree.root); rbtree_destory(&tree); return 0; }

编译与运行

gcc -o rbtree_test rbtree.c main.c ./rbtree_test

输出示例：

Inorder traversal: 3 -> three 5 -> five 7 -> seven 10 -> ten 15 -> fifteen Found key 5 -> five After mod: 5 -> FIVE After deleting 10: 3 -> three 5 -> FIVE 7 -> seven 15 -> fifteen

9. 性能与总结

9.1 时间复杂度

由于红黑树的高度最多为2*log2(n+1)，所有动态操作都能在对数时间内完成。

9.2 与 AVL 树的对比

9.3 本实现的优缺点

优点

• 完全泛型，可存储任意数据类型。
• 哨兵节点简化了边界处理。
• 内存管理灵活（用户可自定义释放函数）。

可改进点

• 未提供迭代器接口。
• 未支持重复键（重复插入会失败）。
• 未实现红黑树验证函数（检验性质）。

10. 结束语

红黑树是计算机科学中优雅而强大的数据结构。通过本篇文章，我们一行行地实现了它的核心操作。希望这份代码和讲解能帮助你真正理解红黑树，并在自己的项目中灵活运用。

如果觉得文章对你有帮助，请点赞、分享，让更多同学一起手撕红黑树！