算法与数据结构：红黑树详解
创作时间:
作者:
@小白创作中心
算法与数据结构：红黑树详解
引用
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;
}
这段代码实现了红黑树的基本操作，包括插入、删除和平衡调整。通过这些操作，可以确保红黑树在动态变化中保持良好的平衡性。
热门推荐
王维五言律诗赏析：送别、秋宵、冬雪与闲居
健康饮食指南：远离三大有害烹饪习惯！
半挂车的倒车技巧有哪些？这些技巧如何提升驾驶安全性？
汉斯·季默的生日：一位电影音乐大师的艺术人生
海带的价值在哪里？②吃它，能减肥！
保和丸和加味保和丸的区别 保和丸与健脾丸的区别
多名前国脚加盟国字号梯队教练组，足协“精英青训”从强化师资做起
AI赋能下，文学翻译如何艺术再现？
亚麻衣服的优缺点及选购指南
揭秘祖国最北端和最东极的城市风采
清明扫墓“十大禁忌”千万要谨记！这些细节一定要注意
进入壁垒如何进行全面分析？这种分析方法有哪些实际应用？
硬膜外镇痛与严重孕产妇并发症风险显著降低35%
参松养心胶囊和稳心颗粒哪个更好
农村老式瓦房漏雨怎么修复
“津液”为啥很重要
干煸豆角：一道让你欲罢不能的家常经典
光圈和景深，摄影中的这两个知识你得了解下！
一文掌握血浆置换（PE）：原理、处方、抗凝及指南适应证推荐
白银价格大涨！比黄金来的猛...…
林昀儒挑战梁靖崑，新加坡站半决赛落败，《5连败，仍有收获》。
AI教你高考如何填志愿：9个免费AI填志愿神器
详解：耶稣用过的杯子——圣杯是什么
最新研究发现：高盐饮食可以增强免疫细胞抗癌能力，但是弊大于利
专家提醒：腌制食品虽美味，老年人食用需谨慎
劳务派遣与劳务外包的区别及认定标准
忘记苹果手机锁屏密码的解决方法与预防建议
传统零售业创新破局路径：识变、应变、求变
荀彧是忠于汉室的，他为何不去投靠刘备呢
如何正确选择购买英国短毛猫