红黑树入门指南（C语言版）

红黑树入门指南（C语言版）

前言

红黑树是一种自平衡二叉搜索树，它通过额外的颜色规则保证在最坏情况下基本操作（插入、删除、查找）的时间复杂度为O(log n)。相比AVL树，红黑树的平衡条件更宽松，因此旋转操作更少，适合需要频繁修改的场景（如STL的map、set）。

一、红黑树的基本概念

1.1 核心定义

红黑树是每个节点带有颜色属性（红色或黑色）的二叉搜索树，需满足以下5条性质：

1. 节点颜色：每个节点要么是红色，要么是黑色。
2. 根节点：根节点是黑色。
3. 叶子节点（NIL）：所有叶子节点（空节点，通常用NIL表示）是黑色。
4. 红色节点的子节点：若一个节点是红色，则它的两个子节点必须是黑色（即不存在连续的红色节点）。
5. 黑高一致：从任一节点到其所有后代叶子节点的路径中，包含相同数量的黑色节点（称为该节点的黑高）。

1.2 关键特性

• 近似平衡：红黑树不追求严格的左右子树高度差≤1（如AVL树），但通过性质4和5确保最长路径不超过最短路径的2倍（最短路径全黑，最长路径红黑交替）。
• NIL节点：实际实现中，为了简化边界条件（如叶子节点无子节点），通常用一个统一的NIL节点代替所有空指针（颜色为黑）。

二、红黑树的操作

红黑树的核心操作包括查找、插入和删除。其中查找与普通二叉搜索树一致，插入和删除后可能破坏红黑树性质，需通过旋转和重新着色修复。

2.1 旋转（Rotation）

旋转是调整树结构的基础操作，分为左旋和右旋，用于保持二叉搜索树性质的同时调整节点位置。

左旋（Left Rotation）

以节点x为中心，将x的右子节点y提升为父节点，x成为y的左子节点，y的原左子节点成为x的右子节点。

右旋（Right Rotation）

与左旋对称，以节点y为中心，将y的左子节点x提升为父节点，y成为x的右子节点，x的原右子节点成为y的左子节点。

2.2 插入操作

插入步骤：

1. 按二叉搜索树规则插入新节点（初始颜色设为红色，避免破坏性质5）。
2. 若插入后父节点是黑色，无需调整；若父节点是红色（违反性质4），需通过重新着色或旋转修复。

插入修复的三种情况（父节点为红色时）：

假设新节点为z，父节点p(z)，祖父节点g(z)，叔节点u(z)（p(z)的兄弟节点）：

• 情况1：叔节点u(z)是红色 → 将p(z)和u(z)设为黑色，g(z)设为红色，然后递归检查g(z)。
• 情况2：叔节点u(z)是黑色，且z是p(z)的右子节点 → 对p(z)左旋，转化为情况3。
• 情况3：叔节点u(z)是黑色，且z是p(z)的左子节点 → 将p(z)设为黑色，g(z)设为红色，对g(z)右旋。

2.3 删除操作

删除步骤：

1. 按二叉搜索树规则删除节点（找到替代节点s，可能是后继或前驱）。
2. 若替代节点是黑色，删除后会破坏性质5（黑高减少），需通过重新着色和旋转修复。

删除修复的四种情况（替代节点s为黑色时）：

假设当前节点为x（替代节点），兄弟节点s：

• 情况1：s是红色 → 将s设为黑色，父节点设为红色，对父节点左旋，更新s为新兄弟节点。
• 情况2：s是黑色，且s的两个子节点都是黑色 → 将s设为红色，x上移至父节点。
• 情况3：s是黑色，左子红、右子黑 → 将s设为红色，左子设为黑色，对s右旋，更新s为新兄弟节点。
• 情况4：s是黑色，右子红 → 将s的颜色设为父节点颜色，父节点设为黑色，右子设为黑色，对父节点左旋，x设为根节点结束。

三、红黑树的C语言实现

以下是简化版的红黑树实现（仅包含插入和遍历，删除操作类似但更复杂）

3.1 数据结构定义

// 节点颜色枚举typedefenum{RED,BLACK}Color;// 红黑树节点（使用NIL节点简化边界处理）typedefstructNode{intdata;// 数据域Color color;// 颜色structNode*left;// 左子节点structNode*right;// 右子节点structNode*parent;// 父节点}Node;// 全局NIL节点（所有空指针指向它）Node*NIL;// 初始化NIL节点voidinitNIL(){NIL=(Node*)malloc(sizeof(Node));NIL->color=BLACK;NIL->left=NIL->right=NIL->parent=NULL;}

3.2 辅助函数（创建节点、打印树）

// 创建新节点（初始颜色为RED）Node*createNode(intdata){Node*node=(Node*)malloc(sizeof(Node));node->data=data;node->color=RED;// 新节点默认红色node->left=node->right=node->parent=NIL;returnnode;}// 中序遍历（验证二叉搜索树性质）voidinOrderTraversal(Node*root){if(root==NIL)return;inOrderTraversal(root->left);printf("%d(%s) ",root->data,root->color==RED?"R":"B");inOrderTraversal(root->right);}// 层序遍历（直观查看树结构）voidlevelOrderTraversal(Node*root){if(root==NIL){printf("Tree is empty\n");return;}Node*queue[100];intfront=0,rear=0;queue[rear++]=root;while(front<rear){Node*current=queue[front++];printf("%d(%s) ",current->data,current->color==RED?"R":"B");if(current->left!=NIL)queue[rear++]=current->left;if(current->right!=NIL)queue[rear++]=current->right;}printf("\n");}

3.3 旋转操作实现

// 左旋（x为旋转中心）voidleftRotate(Node**root,Node*x){Node*y=x->right;// y是x的右子节点x->right=y->left;// y的左子节点变为x的右子节点if(y->left!=NIL){y->left->parent=x;}y->parent=x->parent;// y继承x的父节点if(x->parent==NIL){*root=y;// x是根节点，y成为新根}elseif(x==x->parent->left){x->parent->left=y;// x是左子节点，y替换x的位置}else{x->parent->right=y;// x是右子节点，y替换x的位置}y->left=x;// x成为y的左子节点x->parent=y;}// 右旋（与左旋对称）voidrightRotate(Node**root,Node*y){Node*x=y->left;// x是y的左子节点y->left=x->right;// x的右子节点变为y的左子节点if(x->right!=NIL){x->right->parent=y;}x->parent=y->parent;// x继承y的父节点if(y->parent==NIL){*root=x;// y是根节点，x成为新根}elseif(y==y->parent->left){y->parent->left=x;// y是左子节点，x替换y的位置}else{y->parent->right=x;// y是右子节点，x替换y的位置}x->right=y;// y成为x的右子节点y->parent=x;}

3.4 插入与修复操作

// 插入修复（处理插入后可能的红红冲突）voidinsertFixup(Node**root,Node*z){while(z->parent->color==RED){// 父节点为红色时需修复if(z->parent==z->parent->parent->left){// 父节点是祖父的左子Node*y=z->parent->parent->right;// 叔节点if(y->color==RED){// 情况1：叔节点红z->parent->color=BLACK;y->color=BLACK;z->parent->parent->color=RED;z=z->parent->parent;// 检查祖父}else{if(z==z->parent->right){// 情况2：z是右子z=z->parent;leftRotate(root,z);}// 情况3：z是左子z->parent->color=BLACK;z->parent->parent->color=RED;rightRotate(root,z->parent->parent);}}else{// 父节点是祖父的右子（对称处理）Node*y=z->parent->parent->left;// 叔节点if(y->color==RED){z->parent->color=BLACK;y->color=BLACK;z->parent->parent->color=RED;z=z->parent->parent;}else{if(z==z->parent->left){z=z->parent;rightRotate(root,z);}z->parent->color=BLACK;z->parent->parent->color=RED;leftRotate(root,z->parent->parent);}}}(*root)->color=BLACK;// 确保根节点为黑}// 插入节点（返回根节点）Node*insert(Node*root,intdata){Node*z=createNode(data);Node*y=NIL;// y记录z的父节点Node*x=root;// 寻找插入位置（类似BST插入）while(x!=NIL){y=x;if(z->data<x->data){x=x->left;}else{x=x->right;}}z->parent=y;if(y==NIL){root=z;// 树为空，z成为根}elseif(z->data<y->data){y->left=z;}else{y->right=z;}// 修复红黑树性质insertFixup(&root,z);returnroot;}

3.5 测试代码

intmain(){initNIL();// 初始化NIL节点Node*root=NIL;// 插入测试数据inttestData[]={10,20,30,15,25,5};intn=sizeof(testData)/sizeof(testData[0]);for(inti=0;i<n;i++){root=insert(root,testData[i]);printf("插入 %d 后层序遍历: ",testData[i]);levelOrderTraversal(root);}// 验证中序遍历（应有序）printf("中序遍历结果: ");inOrderTraversal(root);printf("\n");return0;}

四、红黑树的应用场景

红黑树因其高效的动态操作性能，被广泛应用于需要快速查找、插入、删除的场景：

• C++ STL：map、set、multimap、multiset的底层实现（GCC使用红黑树）。
• Java集合：TreeMap、TreeSet基于红黑树。
• Linux内核：进程调度（CFS）、内存管理中的区间树。
• 数据库索引：部分数据库的索引结构（如MySQL的某些存储引擎）。

五、总结

红黑树通过颜色规则和旋转操作，在动态数据维护中实现了高效的平衡。其核心是理解插入/删除后的修复逻辑（尤其是各种情况的处理顺序）。尽管代码实现较复杂，但掌握红黑树能帮助我们理解许多高级数据结构的设计思想。