数据结构学习——红黑树
红黑树是一种高效的自平衡的二叉查找树，在创建初期被称为平衡二叉B树(symmetric binary B-trees)，后来才 修改为如今的红黑树。红黑树具有良好的效率，它可在O(logN) 时间内完成查找、增加、删除等操作。对于二叉搜索树，如果插入的数据是随机的，那么它就是接近平衡的二叉树，平衡的二叉树，它的操作效率（查询，插入，删除）效率较高，时间复杂度是O（logN）。但是可能会出现一种极端
目录
前言：
既完成了二叉搜索树、平衡二叉树的学习了解后，终于来到了传说中的红黑树。了解到AVL树的性质，其实其最大的作用就是查找。平衡二叉树的一系列相关操作即使是最坏情况下也可以达到O（logn）的效率。如果在AVL树中插入或删除节点后，使得高度之差大于1。此时，AVL树的平衡状态就被破坏，它就不再是一棵二叉树；为了让它重新维持在一个平衡状态，就需要对其进行旋转处理。因此，红黑树的理论就被创建出来，比如C++ STL中的map就是是基于红黑树结构实现的。那么红黑树到底比AVL树好在哪里？
一、红黑树简介
红黑树是一种高效的自平衡的二叉查找树，在创建初期被称为平衡二叉B树(symmetric binary B-trees)，后来才 修改为如今的红黑树。红黑树具有良好的效率，它可在O(logN) 时间内完成查找、增加、删除等操作。
对于二叉搜索树，如果插入的数据是随机的，那么它就是接近平衡的二叉树，平衡的二叉树，它的操作效率（查询，插入，删除）效率较高，时间复杂度是O（logN）。但是可能会出现一种极端的情况，那就是插入的数据是有序的，导致整棵树变得不那么平衡，从而退化，那么所有的节点都会在根节点的同一侧。此时，二叉搜索树就变为了一个链表，它的操作效率就降低，时间复杂度为O(N)，所以可以认为二叉搜索树的时间复杂度介于O（logN）和O(N)之间。为了应对这种极端情况，红黑树就出现了。其具备了某些二叉搜索树的特性，能解决非平衡树问题，红黑树是一种接近平衡的二叉树，因其并不具备同平衡二叉树一样的所谓平衡因子，而是依靠红黑结点的性质维持，所以其本身并不像二叉搜索树->平衡二叉树这种，存在所谓类似继承的关系。
二、红黑树的概念及性质
每棵树都具有以下特点，首先的是基本构造：
parent：父结点
sibling：兄弟结点
uncle：叔父结点（ parent 的兄弟结点）
grand：祖父结点（ parent 的父结点）
首先，红黑树是一个二叉搜索树，它在每个节点增加了一个存储位记录结点的颜色，可以是红，也可以是黑；通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡
它同时满足以下特性：
1.结点是红色或黑色
2.根是黑色
3.叶子结点（外部结点，空结点）都是黑色，这里的叶子结点指的是最底层的空节点（外部结点），null结点的父结点在红黑树里不看作叶子结点
4.不能同时连续出现两个红结点
5.从任一节点到叶子节点的所有路径都包含相同数目的黑色节点
在进行判断是否满足性质时，一定需要注意，真正的叶子结点是NULL结点，而非具实质性键值的结点。
三、红黑树的等价变换
红黑树是一种自平衡二叉搜索树，通过颜色标记（红 / 黑）和特定规则保持平衡。等价变换是指在不破坏红黑树性质（如颜色规则、平衡特性）的前提下，对树结构进行的局部调整操作，主要通过 旋转（Rotation）和 颜色重涂（Recoloring）实现。
1. 旋转操作
旋转是红黑树调整平衡的核心手段，分为左旋（Left Rotation）和右旋（Right Rotation），目的是通过改变节点的父子关系，在保持二叉搜索树性质的同时调整树的高度。
左旋示例：
- 场景：当某个节点的右子节点高度过高，破坏平衡。
- 操作：将该节点作为左子节点，其右子节点成为新的父节点，并重新连接子树。
- 效果：降低右子树高度，提升左子树高度，保持搜索树性质。
2. 颜色重涂
通过改变节点颜色（红→黑或黑→红），配合旋转操作，恢复红黑树的颜色规则（如 “红节点的子节点必须为黑”“根节点为黑” 等）。
- 典型场景：插入或删除节点后，可能违反颜色规则，需通过颜色重涂和旋转组合调整。
等价变换的重要性：
1. 维持树的平衡：
① 红黑树通过等价变换将树的高度控制在O(log n)级别，避免退化为链表。
② 这使得搜索、插入、删除等操作的时间复杂度稳定为O(log n)，适用于高频动态数据操作场景（如 Java 的 TreeMap、C++ 的 std::map）。
2. 遵守红黑树性质：
红黑树有 5 条核心性质（如根黑、红子黑、黑高相等），等价变换是唯一能在调整结构时不破坏这些性质的手段。
3. 高效处理动态数据
① 在进行一系列操作时，红黑树只需进行局部变换，无需重构整个树，效率远高于其他平衡树（如 AVL 树的全局调整）。
② 这使其在数据库索引、内存数据结构等场景中广泛应用。
四、红黑树的操作
红黑树的基本操作和其他树形结构一样，一般都包括查找、插入、删除等操作。前面说到，红黑树是一种自平衡的二叉查找树，既然是二叉查找树的一种，那么查找过程和二叉查找树一样，较为简单。相对于查找操作，红黑树的插入和删除操作就要复杂的多
0、基础结构
//宏定义颜色
#define red 0
#define black 1
//数据类型Datatype
typedef char Datatype;
//红黑树节点存储结构
typedef struct node {
Datatype data;
int color;
int key;//排序键值，根据key大小排序
struct node* par;//父节点指针
struct node* left, * right;//左右子节点指针
}Node;
//红黑树的定义rbtree
typedef struct tree {
Node* root;//指向根节点指针
Node* nil;//叶子节点（哨兵）
}rbtree;1、旋转操作
旋转操作分为左旋和右旋，左旋是将某个节点旋转为其右孩子的左孩子，而右旋是节点旋转为其左孩子的右孩子。
① 左旋
左旋是一种将某个节点的右子节点旋转上来的操作。也就是说当前节点的右子节点顶替了自己，然后自己变为右子节点的左子节点，以保持树的平衡。
操作如下：
1、将当前节点的右子节点设为新的父节点。
2、将新的父节点的左子节点设为当前节点的右子节点。
3、如果当前节点有父节点，将新的父节点替代当前节点的位置。
4、将当前节点设为新的父节点的左子节点。
//左旋（以x为旋转点，向左旋转）
void left_rotate(rbtree* T, Node* x) {
Node* y = x->right;//标记到右子节点
x->right = y->left;//y的左子节点代替x的右子节点
if (x->right != T->nil)
x->right->par = x;//如果不为空（nil）其父节点指向x
y->par = x->par;//把y的父节点指向x的父节点，此时x与y没有直接联系了
if (x->par == T->nil) {//判断x的父节点是否为根结点
T->root = y;//如果是的话，y就变为根结点
}
else {
//y顶替x的位置
if (x == x->par->left)
x->par->left = y;//如果x是父节点的左边，那y就代替x成为左子节点
else
x->par->right = y;//如果x是父节点的右边，那y就代替x成为右子节点
}
//y的左子节点指向x，x的父节点指向y
y->left = x;
x->par = y;
}② 右旋
同样的右旋也是将左子节点顶替自己成为父节点， 然后自己成为左子节点的右子节点。
操作如下：
1、将当前节点的左子节点设为新的父节点
2、将新的父节点的右子节点设为当前节点的左子节点
3、如果当前节点有父节点，将新的父节点替代当前节点的位置
4、将当前节点设为新的父节点的右子节点
//右旋（以x为旋转点，向右旋转）
void right_rotate(rbtree* T, Node* x) {
Node* y = x->left;//标记到左子节点y
x->left = y->right;//y的右子节点代替x的左子节点
if (x->left != T->nil)
x->left->par = x;
y->par = x->par;//y的父节点指向x的父节点
if (x->par == T->nil)
T->root = y;//如果x是根结点的话，那么y代替x成为根结点
else {
if (x == x->par->left)
x->par->left = y;
else
x->par->right = y;
}
//y的右子节点指向x，x的父节点为y
y->right = x;
x->par = y;
}2、插入操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：
1、按照二叉搜索的树规则插入新节点
2、检测新节点插入后，红黑树的性质是否造到破坏
因为新节点的默认颜色是红色，因此：
如果其双亲节点的颜色是黑色，没有违反红黑树任何
性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了不能有连
在一起的红色节点，此时需要对红黑树分情况来讨论：
约定 :cur 为当前节点， p 为父节点， g 为祖父节点， u 为叔叔节点
情况一: cur为红，p为红，g为黑，u存在且为红
情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑
情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑
① cur为红，p为红，g为黑，u存在且为红
解决方式：
将p,u改为黑，g改为红，然后把g当成cur，继续向上调整
1、如果g是根节点，调整完后要将g变为黑色
2、如果g不是根节点，继续向上调整
② cur为红，p为红，g为黑，u不存在/u存在且为黑
解决方式：
p为 g 的左孩子， cur 为 p 的左孩子，则对g进行右单旋转；相反，p为g 的右孩子， cur 为 p的右孩子，则对g进行左单旋转p、g 变色 --p 变黑， g 变红
③ cur为红，p为红，g为黑，u不存在/u存在且为黑
解决方式：
p为 g 的左孩子， cur 为 p 的右孩子，则针对 p做左单旋转，再对g进行右单旋转；相反，p为g 的右孩子， cur 为 p 的左孩子，则针对 p做右单旋转，再对g进行左单旋转
代码示例
#include <stdlib.h>
#include <stdbool.h>
// 定义颜色枚举
typedef enum { RED, BLACK } Color;
// 定义键值对结构
typedef struct {
void* key;
void* value;
} Pair;
// 定义节点结构
typedef struct Node {
Pair kv;
struct Node* left;
struct Node* right;
struct Node* parent;
Color col;
} Node;
// 定义红黑树结构
typedef struct {
Node* root;
// 比较函数指针
int (*compare)(const void*, const void*);
} RBTree;
// 创建新节点
Node* createNode(Pair kv) {
Node* node = (Node*)malloc(sizeof(Node));
if (node == NULL) return NULL;
node->kv = kv;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
node->col = RED;
return node;
}
// 左旋函数
void RotateL(RBTree* tree, Node* x) {
Node* y = x->right;
x->right = y->left;
if (y->left != NULL) {
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == NULL) {
tree->root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
// 右旋函数
void RotateR(RBTree* tree, Node* y) {
Node* x = y->left;
y->left = x->right;
if (x->right != NULL) {
x->right->parent = y;
}
x->parent = y->parent;
if (y->parent == NULL) {
tree->root = x;
} else if (y == y->parent->right) {
y->parent->right = x;
} else {
y->parent->left = x;
}
x->right = y;
y->parent = x;
}
// 插入函数
bool RBTree_Insert(RBTree* tree, Pair kv) {
if (tree == NULL) return false;
Node* parent = NULL;
Node* cur = tree->root;
// 查找插入位置
while (cur != NULL) {
int cmp = tree->compare(kv.key, cur->kv.key);
if (cmp > 0) {
parent = cur;
cur = cur->right;
} else if (cmp < 0) {
parent = cur;
cur = cur->left;
} else {
// 键已存在
return false;
}
}
// 创建新节点
Node* newNode = createNode(kv);
if (newNode == NULL) return false;
// 插入新节点
if (parent == NULL) {
tree->root = newNode;
newNode->col = BLACK; // 根节点为黑色
return true;
}
int cmp = tree->compare(kv.key, parent->kv.key);
if (cmp > 0) {
parent->right = newNode;
} else {
parent->left = newNode;
}
newNode->parent = parent;
// 调整红黑树
while (parent != NULL && parent->col == RED) {
Node* grandfather = parent->parent;
if (parent == grandfather->left) {
Node* uncle = grandfather->right;
if (uncle != NULL && uncle->col == RED) {
// 情况1：叔叔节点为红色
parent->col = BLACK;
uncle->col = BLACK;
grandfather->col = RED;
// 继续向上调整
cur = grandfather;
parent = cur->parent;
} else {
// 情况2或3：叔叔节点为黑色
if (cur == parent->right) {
// 情况2：需要左旋
RotateL(tree, parent);
// 交换指针
Node* temp = parent;
parent = cur;
cur = temp;
}
// 情况3：右旋
parent->col = BLACK;
grandfather->col = RED;
RotateR(tree, grandfather);
break;
}
} else {
// 镜像对称情况
Node* uncle = grandfather->left;
if (uncle != NULL && uncle->col == RED) {
// 情况1：叔叔节点为红色
parent->col = BLACK;
uncle->col = BLACK;
grandfather->col = RED;
// 继续向上调整
cur = grandfather;
parent = cur->parent;
} else {
// 情况2或3：叔叔节点为黑色
if (cur == parent->left) {
// 情况2：需要右旋
RotateR(tree, parent);
// 交换指针
Node* temp = parent;
parent = cur;
cur = temp;
}
// 情况3：左旋
parent->col = BLACK;
grandfather->col = RED;
RotateL(tree, grandfather);
break;
}
}
}
// 确保根节点为黑色
tree->root->col = BLACK;
return true;
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
22
0- 0
已为社区贡献3条内容
所有评论(0)