算法与数据结构：红黑树详解
创作时间:
作者:
@小白创作中心
算法与数据结构：红黑树详解
引用
CSDN
1.
https://blog.csdn.net/qq_58240849/article/details/139350282
红黑树是一种自平衡二叉查找树，它在插入和删除操作后能够保持相对平衡，从而确保搜索、最小值、最大值、前驱和后继操作的时间复杂度为O(log n)。本文将详细介绍红黑树的性质、插入和删除操作的平衡调整方法，以及相应的代码实现。
红黑树的性质
红黑树有以下5条性质：
- 每个节点是红色或黑色。
- 根节点是黑色。
- 所有叶子节点都是黑色（这里的叶子节点是指树中所有的空节点）。
- 每个红色节点的两个子节点都是黑色（从每个红色节点到叶子节点的路径上不能有两个连续的红色节点）。
- 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。
这些性质保证了红黑树的平衡性，使得树的高度保持在对数级别。
红黑树的难点
红黑树的难点主要在于插入和删除操作后的平衡调整。为了帮助理解，可以记住以下口诀：
- 插入调整时站在祖父节点看：如果插入的节点违反了性质4，需要找到祖父节点进行调整。
- 删除调整站在父节点看：通过父节点的视角进行调整操作。
插入操作
插入节点时，需要考虑以下问题：
- 插入节点应该是什么颜色？
答：插入节点应该为红色。因为如果插入黑色节点，一定会违反性质5；而插入红色节点，如果父节点是黑色则不需要调整，如果父节点是红色则需要调整，平衡的概率是50%，而插入黑色是100%需要调整。
插入调整分为两种情况：
- 叔叔节点是红色的情况：
将祖父节点变为红色，叔叔节点和父节点变为黑色。
通过调整，这颗子树已经变得平衡。
- 叔叔节点是黑色的情况：
这种情况类似于AVL树中的LL类型，需要进行旋转和颜色调整。
先对祖父节点进行右旋，然后调整节点颜色，确保每条路径的黑色节点数量相同。
对于LR类型，可以通过父节点的左旋将其转换为LL类型处理。
删除操作
删除操作需要考虑以下情况：
- 删除红色节点且度为0：直接删除，不会影响平衡。
- 删除黑色节点且度为0：用NIL虚拟空节点代替，并将NIL节点的颜色变为双重黑。
- 删除红色节点且度为1：这种情况不存在，因为红色节点只能接两个黑色节点或不接节点。
- 删除黑色节点且度为1：将唯一子节点（必为红色）提升到当前位置，并将其颜色改为黑色。
- 删除度为2的节点：通过二叉排序树的删除操作，将其转换为删除度为0或1的节点。
对于双重黑的处理，有以下几种情况：
- 兄弟节点及其子节点都是黑色：
将双重黑节点减去一重黑，父节点增加一重黑，兄弟节点变为红色。
- RR类型：
父节点左旋，调整节点颜色，保持每条路径的黑色节点数量相同。
- RL类型：
先对兄弟节点右旋，再按照RR类型处理。
- 兄弟节点为红色：
兄弟节点变黑，父节点变红，然后左旋，转化为其他情况处理。
代码实现
以下是红黑树的C语言实现代码：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define RED 0
#define BLACK 1
#define DBLACK 2
#define NIL (&__NIL)
#define K(n) (n->key)
#define L(n) (n->lchild)
#define R(n) (n->rchild)
#define C(n) (n->color)
typedef struct Node {
int key, color; // 0 red, 1 black, 2 double black
struct Node *lchild, *rchild;
} Node;
Node __NIL;
__attribute__((constructor))
void init_NIL() {
NIL->key = -1;
NIL->color = BLACK;
NIL->lchild = NIL->rchild = NIL;
return ;
}
Node *getNewNode(int key) {
Node *p = (Node *)malloc(sizeof(Node));
p->key = key;
p->color = RED;
p->lchild = p->rchild = NIL;
return p;
}
bool has_red_node(Node *root) {
return root->lchild->color == RED || root->rchild->color == RED;
}
Node *left_rotate(Node *root) {
Node *new_root = root->rchild;
root->rchild = new_root->lchild;
new_root->lchild = root;
return new_root;
}
Node *right_rotate(Node *root) {
Node *new_root = root->lchild;
root->lchild = new_root->rchild;
new_root->rchild = root;
return new_root;
}
Node *insert_maintain(Node *root) {
int flag = 0;
if (C(L(root)) == RED && has_red_node(L(root))) flag = 1;
if (C(R(root)) == RED && has_red_node(R(root))) flag = 2;
if (flag == 0) return root;
if (C(L(root)) == RED && C(R(root)) == RED) goto red_up_maintain;
if (flag == 1) {
if (C(R(L(root))) == RED) {
L(root) = left_rotate(L(root));
}
root = right_rotate(root);
}
else {
if (C(L(R(root))) == RED) {
R(root) = right_rotate(R(root));
}
root = left_rotate(root);
}
red_up_maintain:
C(root) = RED;
C(L(root)) = C(R(root)) = BLACK;
return root;
}
Node *__insert(Node *root, int key) {
if (root == NIL) return getNewNode(key);
if (root->key == key) return root;
if (key < root->key) root->lchild = __insert(root->lchild, key);
else root->rchild = __insert(root->rchild, key);
return insert_maintain(root);
}
Node *insert(Node *root, int key) {
root = __insert(root, key);
root->color = BLACK;
return root;
}
Node *predecessor(Node *root) {
Node *temp = root->lchild;
while (temp->rchild != NIL) temp = temp->rchild;
return temp;
}
Node *erase_maintain(Node *root) {
if (C(L(root)) != DBLACK && C(R(root)) != DBLACK) return root;
if (has_red_node(root)) {
root->color = RED;
if (root->lchild->color == RED) {
root = right_rotate(root);
root->rchild = erase_maintain(root->rchild);
} else {
root = left_rotate(root);
root->lchild = erase_maintain(root->lchild);
}
root->color = BLACK;
return root;
}
if ((root->lchild->color == DBLACK && !has_red_node(root->rchild))
|| (root->rchild->color == DBLACK && !has_red_node(root->lchild))) {
root->color += 1;
root->lchild->color -= 1;
root->rchild->color -= 1;
return root;
}
if (root->rchild->color == DBLACK) {
root->rchild->color = BLACK;
if (root->lchild->lchild->color != RED) {
root->lchild = left_rotate(root->lchild);
}
root->lchild->color = root->color;
root = right_rotate(root);
} else {
root->lchild->color = BLACK;
if (root->rchild->rchild->color != RED) {
root->rchild = right_rotate(root->rchild);
}
root->rchild->color = root->color;
root = left_rotate(root);
}
root->lchild->color = root->rchild->color = BLACK;
return root;
}
Node *__erase(Node *root, int key) {
if (root == NIL) return root;
if (key < root->key) {
root->lchild = __erase(root->lchild, key);
} else if (key > root->key) {
root->rchild = __erase(root->rchild, key);
} else {
if (root->lchild == NIL || root->rchild == NIL) {
Node *temp = root->lchild == NIL ? root->rchild : root->lchild;
temp->color += root->color;
free(root);
return temp;
}
Node *temp = predecessor(root);
root->key = temp->key;
root->lchild = __erase(root->lchild, temp->key);
}
return erase_maintain(root);
}
Node *erase(Node *root, int key) {
root = __erase(root, key);
root->color = BLACK;
return root;
}
void clear(Node *root) {
if (root == NIL) return ;
clear(root->lchild);
clear(root->rchild);
free(root);
return ;
}
void output(Node *root) {
if (root == NIL) return ;
printf("(%d| %d; %d, %d)\n",
C(root), K(root),
K(L(root)), K(R(root))
);
output(root->lchild);
output(root->rchild);
return ;
}
int main() {
srand(time(0));
#define MAX_N 10
Node *root = NIL;
for (int i = 0; i < MAX_N; i++) {
int x = rand() % 100;
printf("\ninsert %d to red black tree : \n", x);
root = insert(root, x);
output(root);
}
int x;
while (~scanf("%d", &x)) {
printf("\nerase %d from red black tree\n", x);
root = erase(root, x);
output(root);
}
return 0;
}
这段代码实现了红黑树的基本操作，包括插入、删除和平衡调整。通过这些操作，可以确保红黑树在动态变化中保持良好的平衡性。
热门推荐
癫痫患者可以运动健身吗？
三道堰景区：成都近郊的AAAA级水乡古镇
白头发会“拔一根长十根”吗？
“Block”一词的多重含义及其在生活中的应用与应对策略
十类适合新手摆摊的产品推荐 新手摆地摊卖什么好
处理非本人名下机动车违法记录，这样做
梦见别人盖房子的吉凶周公解梦-梦见别人盖房子怎么回事
驾驶证到期如何办理换照
健脾丸吃多久可以治疗脾虚
Mac清理DNS缓存，这样快准狠
夫妻间如何沟通效果最好
金吉拉的生活习性揭秘（了解金吉拉的习性，助你更好地照顾它们）
航空CRM系统：功能、优势与未来发展趋势
定期清理厨房，告别过期食品
Steam关闭开机自动启动的详细步骤
如何进行房产中介的规范管理？这种管理模式有哪些改进空间？
助听器怎么配比较好
老年性聋和助听器：科学应对听力损失的实用指南
手机呼叫转移提示网络异常怎么办？6个常见原因及解决方案
实现工作与生活平衡的5种方法
科学家揭示植物生长与胁迫反应平衡机制
英语学习：系动词的分类、常见形式
氨氮吹脱法的原理、优缺点及影响因素
江苏宜兴旅游攻略：探秘陶都美景与茶文化
小细胞肺癌（SCLC）治疗策略全解析：局限期、广泛期与复发性患者的精准治疗方案
午睡后心跳加快感到心慌如何处理
如何在Excel中将字体变成竖着的，让你的表格更具吸引力！
Unity DOTS技术深度解析：ECS、Job System与Burst编译器
亚洲杯：巴林与日本的16强交锋实力对比
HIIT运动：高强度间歇训练的全面指南