从HashMap到红黑树：手把手带你用C语言实现一个简易版（附OpenHarmony源码分析）

从HashMap到红黑树：手把手带你用C语言实现一个简易版（附OpenHarmony源码分析）

在计算机科学领域，数据结构的选择往往决定了程序的性能边界。当我们使用各种高级语言中的Map或HashMap时，很少思考它们背后的魔法是如何实现的。实际上，这些高效数据结构的核心引擎之一就是红黑树——一种看似复杂却极其优雅的平衡二叉搜索树。

本文将带您深入工程实践，从HashMap的需求出发，逐步揭示红黑树的核心价值。不同于纯理论讲解，我们会结合OpenHarmony操作系统中的真实源码，最终用C语言实现一个支持基本操作的红黑树结构。您将看到算法理论如何转化为实际可用的代码，以及为什么红黑树会成为工业级系统的首选平衡树结构。

1. 为什么HashMap需要树结构

现代编程语言中的HashMap通常被实现为数组加链表的结构，这种设计在理想情况下能提供O(1)时间复杂度的访问性能。然而，当哈希冲突严重时，链表可能退化为线性结构，导致性能急剧下降。这时，将链表转换为平衡树就成为提升性能的关键策略。

以Java 8的HashMap实现为例，当链表长度超过阈值（默认为8）时，链表会自动转换为红黑树：

// 伪代码展示链表转树的逻辑 if (binCount >= TREEIFY_THRESHOLD - 1) { treeifyBin(tab, hash); break; }

这种混合设计结合了哈希表的最佳平均情况和树结构的最差情况保障。红黑树在此场景中的优势主要体现在：

• 最差情况下仍保持O(log n)操作复杂度
• 相对AVL树更少的旋转操作，适合频繁插入删除的场景
• 内存效率高，每个节点只需额外1bit存储颜色信息

在OpenHarmony的hashmap实现中，我们也能看到类似的设计思想。例如在kernel/linux/linux-5.10/lib/rbtree.c中，红黑树被广泛用于管理各种内核数据结构。

2. 红黑树核心原理剖析

红黑树通过五条简单的规则维持平衡，这些规则看似简单却蕴含着精妙的设计：

1. 节点非红即黑
2. 根节点必须为黑
3. 红色节点的子节点必须为黑（无连续红节点）
4. 从任一节点到其叶子的所有路径包含相同数量的黑节点
5. NIL节点视为黑色

这些规则确保了红黑树的关键特性：从根到最远叶子的路径不超过最近路径的两倍。下面是一个典型红黑树的结构示例：

B8 / \ R4 R12 / \ / \ B2 B6 B10 B14

与AVL树相比，红黑树的平衡要求更为宽松，这带来了实际性能优势：

在OpenHarmony的进程调度器中，红黑树被用来管理就绪队列。kernel/liteos_a/libs/libc/src/queue.c中的实现展示了如何利用红黑树高效管理动态任务。

3. 红黑树节点设计与基础操作

让我们从基础结构开始，定义一个红黑树节点：

typedef enum { RED, BLACK } Color; typedef struct RBNode { int key; Color color; struct RBNode *left; struct RBNode *right; struct RBNode *parent; } RBNode;

这个结构体包含了红黑树节点的所有必要信息。值得注意的是，我们显式存储了父节点指针，这在红黑树操作中至关重要。OpenHarmony的third_party/e2fsprogs/lib/ext2fs/rbtree.c中也采用了类似的设计。

初始化新节点的通用模式如下：

RBNode* create_node(int key) { RBNode* node = (RBNode*)malloc(sizeof(RBNode)); node->key = key; node->color = RED; // 新节点默认为红色 node->left = node->right = node->parent = NULL; return node; }

新节点初始为红色，这可能会违反红黑树规则，需要通过后续调整来修复。这种设计减少了需要处理的平衡情况，是红黑树高效的关键之一。

4. 红黑树插入算法实现

红黑树的插入过程分为两个阶段：标准BST插入和平衡修复。让我们通过具体代码实现这一过程。

4.1 标准BST插入

首先实现标准的二叉搜索树插入逻辑：

void rb_insert(RBNode** root, int key) { RBNode* node = create_node(key); RBNode* parent = NULL; RBNode* current = *root; // 查找插入位置 while (current != NULL) { parent = current; if (node->key < current->key) current = current->left; else current = current->right; } node->parent = parent; if (parent == NULL) { *root = node; // 树为空 } else if (node->key < parent->key) { parent->left = node; } else { parent->right = node; } // 调整红黑树平衡 rb_insert_fixup(root, node); }

4.2 红黑树平衡修复

插入后的平衡修复是红黑树最复杂的部分，需要考虑多种情况：

void rb_insert_fixup(RBNode** root, RBNode* node) { while (node != *root && node->parent->color == RED) { if (node->parent == node->parent->parent->left) { RBNode* uncle = node->parent->parent->right; // Case 1: 叔叔节点为红色 if (uncle != NULL && uncle->color == RED) { node->parent->color = BLACK; uncle->color = BLACK; node->parent->parent->color = RED; node = node->parent->parent; } else { // Case 2: 节点是右孩子 if (node == node->parent->right) { node = node->parent; left_rotate(root, node); } // Case 3: 节点是左孩子 node->parent->color = BLACK; node->parent->parent->color = RED; right_rotate(root, node->parent->parent); } } else { // 对称情况处理... } } (*root)->color = BLACK; }

旋转操作是维持平衡的关键，下面是左旋的实现：

void left_rotate(RBNode** root, RBNode* x) { RBNode* y = x->right; x->right = y->left; if (y->left != NULL) y->left->parent = x; y->parent = x->parent; if (x->parent == NULL) *root = y; else if (x == x->parent->left) x->parent->left = y; else x->parent->right = y; y->left = x; x->parent = y; }

OpenHarmony的kernel/linux/linux-5.10/lib/rbtree.c中实现了类似的旋转逻辑，但更加优化，考虑了各种边界条件。

5. 红黑树删除操作详解

删除操作比插入更为复杂，因为它可能同时影响树的平衡和颜色属性。我们分步骤实现这一过程。

5.1 标准BST删除

首先实现替换节点的辅助函数：

void rb_transplant(RBNode** root, RBNode* u, RBNode* v) { if (u->parent == NULL) *root = v; else if (u == u->parent->left) u->parent->left = v; else u->parent->right = v; if (v != NULL) v->parent = u->parent; }

然后是主要的删除逻辑：

void rb_delete(RBNode** root, int key) { RBNode* z = rb_search(*root, key); if (z == NULL) return; RBNode* y = z; Color y_original_color = y->color; RBNode* x; if (z->left == NULL) { x = z->right; rb_transplant(root, z, z->right); } else if (z->right == NULL) { x = z->left; rb_transplant(root, z, z->left); } else { y = tree_minimum(z->right); y_original_color = y->color; x = y->right; if (y->parent == z) { if (x != NULL) x->parent = y; } else { rb_transplant(root, y, y->right); y->right = z->right; y->right->parent = y; } rb_transplant(root, z, y); y->left = z->left; y->left->parent = y; y->color = z->color; } if (y_original_color == BLACK) rb_delete_fixup(root, x); free(z); }

5.2 删除后的平衡修复

删除黑色节点后，需要通过复杂的修复过程恢复红黑树性质：

void rb_delete_fixup(RBNode** root, RBNode* x) { while (x != *root && (x == NULL || x->color == BLACK)) { if (x == x->parent->left) { RBNode* w = x->parent->right; // Case 1: 兄弟节点为红色 if (w->color == RED) { w->color = BLACK; x->parent->color = RED; left_rotate(root, x->parent); w = x->parent->right; } // Case 2: 兄弟节点的两个子节点都是黑色 if ((w->left == NULL || w->left->color == BLACK) && (w->right == NULL || w->right->color == BLACK)) { w->color = RED; x = x->parent; } else { // Case 3: 兄弟节点的右子节点为黑色 if (w->right == NULL || w->right->color == BLACK) { if (w->left != NULL) w->left->color = BLACK; w->color = RED; right_rotate(root, w); w = x->parent->right; } // Case 4 w->color = x->parent->color; x->parent->color = BLACK; if (w->right != NULL) w->right->color = BLACK; left_rotate(root, x->parent); x = *root; } } else { // 对称情况处理... } } if (x != NULL) x->color = BLACK; }

OpenHarmony中的实现（如third_party/mtd-utils/jffsX-utils/rbtree.c）处理了更多边界情况，值得参考。

6. 红黑树在OpenHarmony中的实际应用

OpenHarmony作为现代操作系统，大量使用了红黑树来管理各种内核资源。让我们分析几个典型应用场景：

6.1 进程调度

在kernel/liteos_a/libs/libc/src/queue.c中，红黑树被用来管理就绪队列：

struct ProcessControlBlock { int pid; int priority; RBNode rb_node; // 嵌入红黑树节点 // 其他字段... };

调度器可以根据优先级快速找到最高优先级的就绪进程，时间复杂度仅为O(log n)。

6.2 内存管理

OpenHarmony的内存管理系统使用红黑树跟踪内存块：

struct MemoryChunk { size_t size; void* start_addr; RBNode size_node; // 按大小组织的红黑树 RBNode addr_node; // 按地址组织的红黑树 };

这种双重索引结构使得系统可以：

• 快速找到足够大的空闲块（最佳适配）
• 快速合并相邻空闲块

6.3 文件系统

在third_party/e2fsprogs/lib/ext2fs/rbtree.c中，红黑树被用于：

• 目录项缓存
• 文件块映射管理
• 磁盘配额跟踪

以下是一个简化的文件块管理示例：

struct FileBlock { unsigned long block_no; RBNode node; // 其他元数据... }; // 按块号查找 struct FileBlock* find_block(RBNode* root, unsigned long block_no) { RBNode* current = root; while (current != NULL) { struct FileBlock* fb = container_of(current, struct FileBlock, node); if (block_no < fb->block_no) current = current->left; else if (block_no > fb->block_no) current = current->right; else return fb; } return NULL; }

7. 性能优化与实践建议

在实际工程中实现红黑树时，有几个关键优化点值得注意：

7.1 内存布局优化

现代CPU对缓存命中率极为敏感。我们可以优化节点结构：

// 优化后的节点结构 typedef struct RBNode { int key; RBNode* left; RBNode* right; RBNode* parent; uintptr_t color; // 利用指针最低位存储颜色 } RBNode;

这种设计：

• 将颜色信息嵌入父指针的最低有效位（LSB）
• 减少内存占用（从至少12字节降到8字节）
• 提高缓存局部性

OpenHarmony的kernel/linux/linux-5.10/lib/rbtree.c采用了类似的技巧。

7.2 迭代器实现

为红黑树实现迭代器可以大大简化遍历操作：

typedef struct { RBNode* current; RBNode* root; } RBIterator; RBNode* rb_iter_next(RBIterator* iter) { RBNode* current = iter->current; if (current == NULL) return NULL; // 中序遍历 if (current->right != NULL) { current = current->right; while (current->left != NULL) current = current->left; iter->current = current; return current; } RBNode* parent = current->parent; while (parent != NULL && current == parent->right) { current = parent; parent = parent->parent; } iter->current = parent; return parent; }

7.3 无父指针实现

在某些受限环境中，可以牺牲部分性能实现无父指针的红黑树：

void rb_insert_no_parent(RBNode** root, int key) { RBNode** current = root; RBNode* parent = NULL; while (*current != NULL) { parent = *current; if (key < parent->key) current = &parent->left; else current = &parent->right; } *current = create_node(key); rb_insert_fixup_no_parent(root, *current, parent); }

这种实现虽然节省了内存，但增加了算法复杂度，适合内存极度受限的嵌入式场景。