从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. 红黑树核心原理剖析红黑树通过五条简单的规则维持平衡这些规则看似简单却蕴含着精妙的设计节点非红即黑根节点必须为黑红色节点的子节点必须为黑无连续红节点从任一节点到其叶子的所有路径包含相同数量的黑节点NIL节点视为黑色这些规则确保了红黑树的关键特性从根到最远叶子的路径不超过最近路径的两倍。下面是一个典型红黑树的结构示例B8 / \ R4 R12 / \ / \ B2 B6 B10 B14与AVL树相比红黑树的平衡要求更为宽松这带来了实际性能优势特性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); }这种实现虽然节省了内存但增加了算法复杂度适合内存极度受限的嵌入式场景。
从HashMap到红黑树：手把手带你用C语言实现一个简易版（附OpenHarmony源码分析）
发布时间：2026/6/7 6:13:39
从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. 红黑树核心原理剖析红黑树通过五条简单的规则维持平衡这些规则看似简单却蕴含着精妙的设计节点非红即黑根节点必须为黑红色节点的子节点必须为黑无连续红节点从任一节点到其叶子的所有路径包含相同数量的黑节点NIL节点视为黑色这些规则确保了红黑树的关键特性从根到最远叶子的路径不超过最近路径的两倍。下面是一个典型红黑树的结构示例B8 / \ R4 R12 / \ / \ B2 B6 B10 B14与AVL树相比红黑树的平衡要求更为宽松这带来了实际性能优势特性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); }这种实现虽然节省了内存但增加了算法复杂度适合内存极度受限的嵌入式场景。
