红黑树入门指南（C语言版）
·
红黑树入门指南（C语言版）
文章目录
前言
红黑树是一种自平衡二叉搜索树，它通过额外的颜色规则保证在最坏情况下基本操作（插入、删除、查找）的时间复杂度为 O(log n)。相比AVL树，红黑树的平衡条件更宽松，因此旋转操作更少，适合需要频繁修改的场景（如STL的map、set）。
一、红黑树的基本概念
1.1 核心定义
红黑树是每个节点带有颜色属性（红色或黑色）的二叉搜索树，需满足以下5条性质：
- 节点颜色：每个节点要么是红色，要么是黑色。
- 根节点：根节点是黑色。
- 叶子节点（NIL）：所有叶子节点（空节点，通常用NIL表示）是黑色。
- 红色节点的子节点：若一个节点是红色，则它的两个子节点必须是黑色（即不存在连续的红色节点）。
- 黑高一致：从任一节点到其所有后代叶子节点的路径中，包含相同数量的黑色节点（称为该节点的黑高）。
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 插入操作
插入步骤：
- 按二叉搜索树规则插入新节点（初始颜色设为红色，避免破坏性质5）。
- 若插入后父节点是黑色，无需调整；若父节点是红色（违反性质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 删除操作
删除步骤：
- 按二叉搜索树规则删除节点（找到替代节点
s，可能是后继或前驱）。 - 若替代节点是黑色，删除后会破坏性质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 数据结构定义
// 节点颜色枚举
typedef enum { RED, BLACK } Color;
// 红黑树节点（使用NIL节点简化边界处理）
typedef struct Node {
int data; // 数据域
Color color; // 颜色
struct Node *left; // 左子节点
struct Node *right; // 右子节点
struct Node *parent;// 父节点
} Node;
// 全局NIL节点（所有空指针指向它）
Node *NIL;
// 初始化NIL节点
void initNIL() {
NIL = (Node*)malloc(sizeof(Node));
NIL->color = BLACK;
NIL->left = NIL->right = NIL->parent = NULL;
}
3.2 辅助函数（创建节点、打印树）
// 创建新节点（初始颜色为RED）
Node* createNode(int data) {
Node *node = (Node*)malloc(sizeof(Node));
node->data = data;
node->color = RED; // 新节点默认红色
node->left = node->right = node->parent = NIL;
return node;
}
// 中序遍历（验证二叉搜索树性质）
void inOrderTraversal(Node *root) {
if (root == NIL) return;
inOrderTraversal(root->left);
printf("%d(%s) ", root->data, root->color == RED ? "R" : "B");
inOrderTraversal(root->right);
}
// 层序遍历（直观查看树结构）
void levelOrderTraversal(Node *root) {
if (root == NIL) {
printf("Tree is empty\n");
return;
}
Node *queue[100];
int front = 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为旋转中心）
void leftRotate(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成为新根
} else if (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;
}
// 右旋（与左旋对称）
void rightRotate(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成为新根
} else if (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 插入与修复操作
// 插入修复（处理插入后可能的红红冲突）
void insertFixup(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, int data) {
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成为根
} else if (z->data < y->data) {
y->left = z;
} else {
y->right = z;
}
// 修复红黑树性质
insertFixup(&root, z);
return root;
}
3.5 测试代码
int main() {
initNIL(); // 初始化NIL节点
Node *root = NIL;
// 插入测试数据
int testData[] = {10, 20, 30, 15, 25, 5};
int n = sizeof(testData) / sizeof(testData[0]);
for (int i = 0; i < n; i++) {
root = insert(root, testData[i]);
printf("插入 %d 后层序遍历: ", testData[i]);
levelOrderTraversal(root);
}
// 验证中序遍历（应有序）
printf("中序遍历结果: ");
inOrderTraversal(root);
printf("\n");
return 0;
}
四、红黑树的应用场景
红黑树因其高效的动态操作性能，被广泛应用于需要快速查找、插入、删除的场景：
- C++ STL：
map、set、multimap、multiset的底层实现（GCC使用红黑树）。 - Java集合：
TreeMap、TreeSet基于红黑树。 - Linux内核：进程调度（
CFS）、内存管理中的区间树。 - 数据库索引：部分数据库的索引结构（如MySQL的某些存储引擎）。
五、总结
红黑树通过颜色规则和旋转操作，在动态数据维护中实现了高效的平衡。其核心是理解插入/删除后的修复逻辑（尤其是各种情况的处理顺序）。尽管代码实现较复杂，但掌握红黑树能帮助我们理解许多高级数据结构的设计思想。
更多推荐
26
0- 0
已为社区贡献1条内容
所有评论(0)