红黑树完全指南：从五条性质到完整插入删除实现

引言在前面的树系列中我们学习了二叉搜索树BST和 AVL 树。AVL 树通过严格的平衡条件|BF| ≤ 1保证 O(log n) 的性能但代价是删除操作可能触发 O(log n) 次旋转。红黑树Red-Black Tree采用了一种更灵活的平衡策略——用颜色约束代替高度约束。它在插入和删除时最多只需要O(1)次旋转插入最多 2 次删除最多 3 次同时仍能保证树的高度不超过 2log(n1)整体性能优于 AVL 树。正因如此红黑树成为了实际工程中最广泛使用的平衡树——Java 的TreeMap/TreeSet、C 的std::map/std::set、Linux 内核的 CFS 调度器、epoll 的事件管理……底层都是红黑树。第一部分红黑树的五条性质一、五条性质红黑树是一棵满足以下五条性质的二叉搜索树1、每个节点要么是红色要么是黑色2、根节点是黑色3、每个叶子节点NIL是黑色4、如果一个节点是红色则它的两个子节点必须是黑色 即不允许连续两个红色节点5、从任意节点到其所有后代叶子节点的路径上 包含相同数量的黑色节点记忆口诀根黑叶黑红不连续黑高相等二、性质图解三、红黑树的高度上界定理一棵含有 n 个节点的红黑树其高度最多为2log₂(n1)。四、NIL 节点的作用红黑树通常使用一个哨兵 NIL 节点来代表所有空指针类似带头结点的链表第二部分节点结构与基本操作一、节点结构#include stdio.h #include stdlib.h #include stdbool.h typedef int ElemType; // 颜色定义 typedef enum { RED, BLACK } Color; typedef struct RBNode { ElemType data; Color color; struct RBNode* left; struct RBNode* right; struct RBNode* parent; // 父节点旋转和修复时需要 } RBNode; // 全局 NIL 哨兵所有空指针指向它 RBNode* NIL;二、初始化与辅助函数// 初始化 NIL 哨兵 void initNIL() { NIL (RBNode*)malloc(sizeof(RBNode)); NIL-color BLACK; NIL-left NIL-right NIL-parent NULL; } // 创建新节点默认红色 RBNode* createNode(ElemType val) { RBNode* node (RBNode*)malloc(sizeof(RBNode)); node-data val; node-color RED; // 新节点默认红色更容易修正 node-left NIL; node-right NIL; node-parent NULL; return node; } // 判断节点是否为红色 bool isRed(RBNode* node) { return node ! NIL node-color RED; } // 判断节点是否为黑色 bool isBlack(RBNode* node) { return node NIL || node-color BLACK; }为什么新节点默认是红色第三部分旋转操作红黑树使用与 AVL 树相同的两种基本旋转左旋和右旋区别在于需要维护parent指针和颜色。一、左旋void rotateLeft(RBNode** root, RBNode* A) { RBNode* C A-right; // C A 的右子 A-right C-left; // A 的右子 C 的左子 if (C-left ! NIL) { C-left-parent A; } C-parent A-parent; // 继承 A 的父节点 if (A-parent NULL) { *root C; // A 是根C 成为新根 } else if (A A-parent-left) { A-parent-left C; } else { A-parent-right C; } C-left A; // A 成为 C 的左子 A-parent C; }二、右旋void rotateRight(RBNode** root, RBNode* A) { RBNode* B A-left; // B A 的左子 A-left B-right; // A 的左子 B 的右子 if (B-right ! NIL) { B-right-parent A; } B-parent A-parent; // 继承 A 的父节点 if (A-parent NULL) { *root B; // A 是根B 成为新根 } else if (A A-parent-left) { A-parent-left B; } else { A-parent-right B; } B-right A; // A 成为 B 的右子 A-parent B; }第四部分插入操作一、插入流程二、三种修复情况插入后需要修复的情况取决于叔叔节点父节点的兄弟的颜色三、插入修复图解Case 1叔叔是红色只需变色Case 2叔叔黑色 X 是右子 → 转为 Case 3Case 3叔叔黑色 X 是左子 → 右旋 变色四、插入修复代码void insertFixUp(RBNode** root, RBNode* X) { // 只要父节点是红色需要修复 while (isRed(X-parent)) { RBNode* P X-parent; RBNode* G P-parent; // 祖父一定存在且为黑色 if (P G-left) { // 父节点是左子 RBNode* U G-right; // 叔叔是右子 // Case 1叔叔是红色 if (isRed(U)) { P-color BLACK; U-color BLACK; G-color RED; X G; // 上移继续检查 } else { // Case 2叔叔黑色X 是右子LR → 转 LL if (X P-right) { rotateLeft(root, P); X P; P X-parent; } // Case 3叔叔黑色X 是左子LL P-color BLACK; G-color RED; rotateRight(root, G); } } else { // 父节点是右子镜像对称 RBNode* U G-left; if (isRed(U)) { P-color BLACK; U-color BLACK; G-color RED; X G; } else { if (X P-left) { // RL → 转 RR rotateRight(root, P); X P; P X-parent; } P-color BLACK; G-color RED; rotateLeft(root, G); } } } (*root)-color BLACK; // 确保根是黑色 }五、插入主函数void rbInsert(RBNode** root, ElemType val) { // 1. 普通 BST 插入 RBNode* newNode createNode(val); RBNode* parent NULL; RBNode* cur *root; while (cur ! NIL cur ! NULL) { parent cur; if (val cur-data) cur cur-left; else if (val cur-data) cur cur-right; else return; // 不允许重复 } newNode-parent parent; if (parent NULL) { *root newNode; } else if (val parent-data) { parent-left newNode; } else { parent-right newNode; } newNode-left NIL; newNode-right NIL; // 2. 修复红黑树性质 insertFixUp(root, newNode); }第五部分删除操作一、删除流程红黑树删除流程① 像 BST 一样删除节点② 记录实际被删除节点的颜色③ 如果被删除的是黑色节点需要修复④ 修复从替代节点开始关键只有删除黑色节点才会破坏性质⑤二、四种删除修复情况修复的核心思想让替代节点多携带一层黑色双黑然后通过旋转和变色消除。三、删除修复代码void deleteFixUp(RBNode** root, RBNode* X) { while (X ! *root isBlack(X)) { RBNode* P X-parent; if (X P-left) { // X 是左子 RBNode* S P-right; // 兄弟 // Case 1兄弟是红色 if (isRed(S)) { S-color BLACK; P-color RED; rotateLeft(root, P); S P-right; // 新的兄弟 } // Case 2兄弟黑色且两个侄子都是黑色 if (isBlack(S-left) isBlack(S-right)) { S-color RED; X P; // 上移 } else { // Case 3兄弟黑色左侄子红右侄子黑 if (isBlack(S-right)) { S-left-color BLACK; S-color RED; rotateRight(root, S); S P-right; } // Case 4兄弟黑色右侄子红 S-color P-color; P-color BLACK; S-right-color BLACK; rotateLeft(root, P); X *root; // 修复完成退出 } } else { // X 是右子镜像对称 RBNode* S P-left; if (isRed(S)) { S-color BLACK; P-color RED; rotateRight(root, P); S P-left; } if (isBlack(S-left) isBlack(S-right)) { S-color RED; X P; } else { if (isBlack(S-left)) { S-right-color BLACK; S-color RED; rotateLeft(root, S); S P-left; } S-color P-color; P-color BLACK; S-left-color BLACK; rotateRight(root, P); X *root; } } } X-color BLACK; }四、删除主函数// 用子树 v 替换子树 u void 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; } v-parent u-parent; } // 找最小值节点 RBNode* minimum(RBNode* node) { while (node-left ! NIL) node node-left; return node; } void rbDelete(RBNode** root, ElemType val) { RBNode* Z *root; while (Z ! NIL) { if (val Z-data) break; else if (val Z-data) Z Z-left; else Z Z-right; } if (Z NIL) return; // 未找到 RBNode* Y Z; RBNode* X; Color Y_original_color Y-color; if (Z-left NIL) { X Z-right; transplant(root, Z, Z-right); } else if (Z-right NIL) { X Z-left; transplant(root, Z, Z-left); } else { Y minimum(Z-right); Y_original_color Y-color; X Y-right; if (Y-parent Z) { X-parent Y; } else { transplant(root, Y, Y-right); Y-right Z-right; Y-right-parent Y; } transplant(root, Z, Y); Y-left Z-left; Y-left-parent Y; Y-color Z-color; } free(Z); if (Y_original_color BLACK) { deleteFixUp(root, X); } }第六部分完整测试#include stdio.h #include stdlib.h #include stdbool.h // ... 上面所有代码 ... void inorder(RBNode* root) { if (root NIL) return; inorder(root-left); printf(%d(%c) , root-data, root-color RED ? R : B); inorder(root-right); } int main() { initNIL(); RBNode* root NULL; int values[] {10, 20, 30, 15, 25, 5, 1}; int n sizeof(values) / sizeof(values[0]); printf( 插入测试 \n); for (int i 0; i n; i) { rbInsert(root, values[i]); printf(插入 %d, values[i]); inorder(root); printf(\n); } printf(\n 删除测试 \n); int dels[] {20, 10, 30}; for (int i 0; i 3; i) { printf(删除 %d, dels[i]); rbDelete(root, dels[i]); inorder(root); printf(\n); } return 0; }第七部分红黑树 vs AVL 树对比项AVL 树红黑树平衡策略严格|BF| ≤ 1宽松颜色约束树高更矮最多高 1 倍查找稍快更矮稍慢插入旋转最多 2 次最多 2 次删除旋转可能 O(log n) 次最多 3 次实现复杂度中等较高适用场景查询多增删多实际应用红黑树应用更广因为实际系统中增删操作频繁红黑树的删除优势明显。总结一、核心要点要点内容五条性质根黑叶黑红不连续黑高相等新节点颜色默认红色更容易修正NIL 哨兵所有空指针指向同一个黑色 NIL插入修复最多 2 次旋转Case 1 只变色删除修复最多 3 次旋转应用std::map、TreeMap、epoll、内核二、插入修复记忆口诀三、一句话记忆红黑树用五条颜色约束代替 AVL 的高度约束插入删除最多 O(1) 次旋转。新节点默认红色通过叔父关系分情况修复最终保证树高不超过 2log(n1)是工程界最广泛使用的平衡树。