手撕红黑树（红黑树介绍 + 红黑树插入代码详细讲解）
前引
呼呼呼呼 在我大概测试了30多组插入后 都发现插入正确后 我们的红黑树插入部分的正确性 基本也就验证正确了
说到为什么要手撕红黑树 主要我是一个实践派 不自己手动写一下 或者自己实现一下就一直觉得心里面空落落的 要谈起为什么开始手撕数据结构了 就要讲到昨天发布的手撕AVL树了
手撕AVL树（含旋转代码讲解 + 例题）
在进入下面的红黑树讲解部分 尤其对于想要自己实现一下红黑树的hxd们 我强烈强烈建议 先去手撕一遍AVL树 手撕完了 再来看红黑树 就会发现 只不过是两个亲兄弟而已 一个有强迫症、一个性格温和 能包容万物 但是身上一块红一块黑的 实现起来只不过多了个颜色变化 还有情况变化而已 没什么难的
我们这部分 只讲解 插入的实现 对于删除的实现 应该是比插入的实现要困难不少的 这里也就不介绍了（我其实也没有实现删除部分 : ( )
上面也做了说明了 我强烈建议在实现红黑树前 先去实现一遍AVL树 因为旋转的原理是一模一样的 搞懂了AVL树 红黑树的话 也就八九不离十了 那就先写到这里
手撕数据结构 总结博客链接
手撕数据结构（最小堆 + 二叉树前中后非递归遍历 + 快排归并排序 + KMP匹配算法 + AVL + 红黑树）
推荐数据结构可视化网址
下面这个链接超级好用 可以用来看红黑树 各种数据结构插入的过程 下面放个使用图 我用来检查我的红黑树究竟是不是对的 而且可以自己用来分析旋转过程（强烈推荐）
Data Structure Visualizations（数据结构可视化）
推荐讲解红黑树的博客与视频
强烈推荐最后一个视频 前两篇博客 第一篇没怎么看 第二篇看了部分 写的还是挺好的 但是没有视频的话 感觉还是没有那么立体
强烈推荐最后一个视频！我大概看完视频后 花了不到三个小时左右就自己把红黑树插入给实现了
【算法】手撕红黑树（上）—— 基本性质以及插入实现（附带代码实现 JAVA）
30张图带你彻底理解红黑树（强烈推荐）
Bilibili UP主：Free-Coder 红黑树视频讲解（强烈推荐）
红黑树介绍
1、接触红黑树的原因
说来惭愧 我第一次接触红黑树的时候 应该是在浙大数据结构里面 接触过的 那个时候只不过老师肯定是没有讲的 应该是当时提了一嘴 但当时对于
BSTAVL树 什么是什么我都没有搞清 觉得一切的一切都好复杂 好陌生 但当时我记得还是完成了 PTA里面的AVL树的构建 那个时候我只觉得 根本不可能自己以后能够 在面试或者机试的压力环境下写出来 因为那个时候写出来 都是凭着给的旋转图纸 自己一点点硬凑 把节点的情况全部列出来 然后自己去尝试 反正对于当时刚学数据结构的我 是无比的困难
红黑树 我也是前两天看数据库 想着把数据库在重新看一遍 结果发现书籍里面讲了B+树 忽然发觉自己很多面试常考的树 自己都没有做一个梳理 现在刚好遇到了 自己就重新开始手撕一遍吧 当然对于B+树 手撕就算了 - -
我也是这两天才系统的去接触红黑树 之前《算法第四版》出现过 但是自己那时就想着什么都自己实现一遍 看到红黑树 一点挑战的勇气都没有 所以当然 自己也就跳过去了 现在也算是终于把原来欠的东西还了 自己心里也舒坦了一些 哈哈
好了 上面聊了些最开始接触红黑树的历程 那下面正式聊聊红黑树吧 因为我系统接触 到现在时间也没有多久 所以下面的很多东西我会用方便各位理解的话说 如果有误希望各位指出 并谅解🙏
2、二叉搜索树的介绍
相信了解树的hxd 应该知道 红黑树的应用范围是相对广的
红黑树 是 二叉自平衡搜索树的一种 二叉搜索树的特点是：左侧节点的值比当前节点的值小 右侧节点的值比当前节点的值大 那讲到二叉搜索树 此时不介绍一下就不太合适吧 本着刨根问到底的精神 我们就挨个挨个把它的好兄弟们都一个个梳理一遍吧
1、二叉搜索树BST（不自平衡）
对于一个不会自平衡的二叉搜索树BST(Binary Search Tree) 我们方便一点 就叫BST（这里指代不会自平衡）
对于BST 就是最普通的链表 使用范围不广 如果对于插入分布比较均匀的话 那么性能还是相对不错的 这个时候可以稍微考虑一下BST 插入和删除的时间复杂度都是log(n) 当然这是理想情况 我们不可以什么时候都往好的地方想 得考虑最差的情况 好的情况的lgn 是因为我们搜寻的时候是按照二分来搜索的 那最差的情况呢
很容易就能想到 如果当插入的时候 我们如果按照顺序
1、2、3、4、5来插入 我们的二叉搜索树 就会退化为搜索时间复杂度为n的单向链表了
最后就导致 我们查找的时间复杂度还要根据我们输入的顺序来 输入顺序得当 时间复杂度log(n)不得当n那也真让人无语 - -
所以对于不会自平衡的BST 显然使用范围有限 无法得人心 那有没有比BST更好的呢 那肯定啊 我们都说了前提 这个是不会自平衡的 那缺点也就是在这里
2、AVL树（完美自平衡二叉搜索树）
好了 终于到了我们AVL树 登场了 看到我给AVL取的小名字了吗 完美自平衡二叉搜索树 当然这里的完美不是指其性能完美 不是指各处都是完美的 这里的完美的意思是 其高度差 每次插入删除后 树都努力的往满二叉树上面靠 也可以用稍微术语一点说 任一节点到其叶子节点的高度差绝对值小于等于1
看下面的图 就能明白AVL树是干嘛的了
针对
AVL树 我之前写过手撕AVL树 里面也有对AVL树的解析 想要手撕它的hxd可以看下面的链接
手撕AVL树（含旋转代码讲解 + 例题）
当然 这篇博客里面还是要不能偷懒 需要再讲讲它
之所以AVL树 能够达成完美高度差 是因为每次插入 如果不符合其规定 任一节点到其叶子节点高度差小于等于1时 就需要旋转其局部节点 从而完成这样的要求
对于AVL树的旋转 我就不详细讲了 但是需要以上览下的再说说AVL树AVL的完美 是建立在每次插入后 需要花费一定时间的旋转的代价的注意每次插入后 需要花费一定的时间旋转节点满足其完美的要求 我们可以理解为AVL树每次插入都花了比较多的时间代价来做旋转
这样插入旋转的好处有吗 当然有！好处在于 我们每次搜索节点的时候 时间复杂度严格遵守log(n)也就是 我们每次搜寻的时间时间下界是log(n)这比我们的不会自旋的BST下界由线性时间复杂度 变为了对数时间复杂度 可喜可贺
那这样 我们以后就用AVL树 充当数据的存放 和 搜寻工具 可以吗？可以！ 但是使用范围同样有限！你可能觉得很无语 为什么这样一个完美平衡的二叉树（且是最早发明的二叉平衡搜索树）不能大范围使用
你可能 没有想到 它应以为傲的优点 有没有可能是缺点 正是其完美特性 限制了它的应用 你可能没有考虑到 它的完美 是需要建立在 如果不满足条件时 就需要旋转局部节点的高昂时间花销 而且每个局部都需要满足条件 这样严苛的条件 我们也分析了 它的优势也在于搜索
所以我们认为AVL树 应用场景限于 插入数据不是很频繁、搜索数据远比插入数据频繁的场景 才是它发挥的地方 如果我们既需要插入数据 搜索数据 两者频率没有很大差别的 我们就选择用红黑树终于来了
3、红黑树（综合性能强劲 不平凡的二叉弱平衡搜索树）
这个 二叉弱平衡搜索树 是我之前不知道在哪看到过的名字 那是印象特别深刻 这个名字不是官方取的 只是比较好的概括了他的特点
我们费了好大的力气 才介绍完了他的两个好兄弟 现在终于到他上场的时候了
可能你对这个名字有些疑惑 什么是弱平衡搜索树 哈哈 他的弱搜索树 只是相对
AVL而言的 其实我认为还是不弱的 只是它的束缚条件比AVL树要求低一些 所以我们才叫他是 二叉弱平衡搜索树
那为什么这样的一个树 大家会把他复刻一遍又一遍 C++里面的set的底层实现就是红黑树linux的进程管理、内存管理里面也使用了红黑树 还有很多很多地方的应用场景里面 关于有序数据的存放 并有 搜索的需求的 绝大部分都是用了红黑树来存储并搜索 搜索并无任何特点 和任何二叉搜索树一样 都是老套路
那他究竟神在什么地方呢 从不考究其特性的地方出发 我们可以这样的描述他
在大量的删除、插入操作下 时间花销相对AVL树 要小的多 而搜索性能 较AVL树基本可以保持在一个lgn的时间复杂度下完成
我们就可以对红黑树有一个这样的客观印象 维护成本较低、插入删除性能不俗、搜索时间保持在一个可以说优秀的程度 他不像AVL树这样偏袒搜索性能 牺牲的是插入维护的性能 红黑树把各方面都综合的很平均 而且都是不错的表现 在各种场景下都能很好的适应 这些理由也足够让我们去使用它了
3、红黑树的特性
好了 上面都很客观的评价了 我们接触的比较多的树 针对B与B+树 可能后面也会单开一篇博客 但肯定不在手撕系列里面了 也是一篇对B树 B+树理解的博客 之后会再写的 现在我们把视角再转到红黑树身上
红黑树有以下5个特性 使它能够有如此不俗的性能 当然我们调整红黑树时 也是按照树必须满足下面五个特性去调整的
注意 红黑树不是只有带有数据的节点才算节点 我们认为
nullptr指针算是叶子节点 只不过不带有数据 但算是叶子节点
1、红黑树中节点都带有颜色 只能是黑色和红色其中一种
2、根节点颜色是黑色的
3、红色节点的下方左右两子节点一定是黑色的
4、叶子节点（这里NULL或者叫做NIL节点算是叶子节点）一定是黑色的
5、任一节点到自己的叶子节点简单路径上所经过的黑色节点数目相同
可能有小伙伴不了解 或者搞不懂这五条规则 我们看规则的时候 也依据下方的图看就看得懂了 下面的叶子节点 原本的红黑树是不存在的 是我单独加上去的 但是我们认为那些黑色节点就是叶子节点 只不过是不带数据的 而带数据的才是真实存在的
4、红黑树的属性介绍
上方推荐的第二篇博客 对红黑树写的相当相对好了了 个人也是从第二篇博客那里深受启发 最后自己完成红黑树插入也是看了第三篇推荐视频而个人完成的 所以希望各位再返回去看看 : )
这部分属性介绍 也是额外加的一部分 不是官方说的 第二篇推荐博客里面写的 红黑树其实本质上 就是
黑色完美平衡二叉树也就是特性五 我们任一结点到叶子节点的任一简单路径中 经过的黑色节点数目永远相等 我们根据这个特性 从而维持了某种平衡 进而使我们的红黑树保持了一个状态的平衡 从而我们的树以至于不会退化成链表
我觉得确实是这个样子的 我们通过一些规则 对红黑树进行束缚 以至于其保持一种相对的平衡 维持到某种状态 但又不像AVL树那样要求完美平衡 我们的红黑树其实是放宽了条件的 所以才导致 我们的维护代价低了一点 也正是我们的红黑树放宽了条件 我们的红黑树搜搜时间复杂度 最高是2*log(n)具体证明烦请各位去其他地方看一下
我们红黑树的最低要求是 一条边的高度 绝对小于 一条最短的边的两倍 这个是我在视频中看到的
口头上的证明可以笼统的说一下 由于红色节点不能互相挨着 所以插入在只能在黑色节点间 黑色节点则无所谓 可以任意挨着 假设一种极端情况 所有的红黑树删除了红色节点了 那么就只剩下了黑色节点（包含null）每条黑色节点的边是等长的（根据特性五可得）对于最长的一条边插入红色节点 红色节点最多两黑节点间插入一个 那么最长的一条边 也最多是最短的一条边的两边 且要小
维持了这种相对平衡 所以才是二叉树没有退化为链表 而又不像AVL那样严格要求 导致每次维护的时候 时间代价比较高
5、红黑树的插入代码解析
上面写了很多 我认为写的还是挺详尽了 在进入插入代码解析之前 下面还是放一下 那个我极其强烈推荐看的视频链接 讲的真的很清晰
Bilibili UP主：Free-Coder 红黑树视频讲解（强烈推荐）
终于进入到了 插入代码的解析了 相信看完视频后 如果对
AVL手撕过 或者了如执掌的hxd 一定可以马上开始对红黑树插入代码的编写当中了 在一些时间的调试后 就可以成功完成代码编写辣
红黑树的插入情况 无非就是六种情况 视频中很清楚 我还是自己写一份吧
上面的表格 已经对插入的情况全部总结了 其实变色地方 都是我自己在草稿纸上画一下 就能明白怎么变色了 至于旋转操作 除了我们在旋转时 相较于
AVL以外就是需要把parent指针给改了 其他旋转操作一模一样
本着负责到底的态度 我挨个挨个的解析以上的操作吧
1、没有根节点（直接插入）
这可以说是最简单的了 没什么好说的 直接插入 并返回插入节点即可
2、父节点黑色、叔节点任意（直接插入）
如果父节点黑色的 那么直接插入即可 用图这样表示
3、父节点红色、叔节点黑色（LL、LR、RL、RR）
1、LL旋转
后面都以图代文了
2、LR旋转
3、RL旋转
4、RR旋转
4、父节点红色、叔节点红色（递归）
其实这部分之后 就到了val为3的节点递归继续往上处理了 但是由于3节点是根节点 根据特性 最后又变成了黑色 如果上面还有的话 就需要再继续向上递归处理旋转
最后3号因为是根节点 变为黑色
红黑树代码实现（插入）
下面这部分就来到了 代码部分了 说实话 写这篇博客的时间可能是我写代码的两倍多了 hhh 但是记下来一些东西属于自己 还是挺好的
对于情况四 递归处理 这部分我才用了二级指针来处理的递归情况 ^^
如果出现了 叔 父两节点变红 则把处理指针 变为祖父指针 继续向上 代码部分我就不再详细介绍了 大家自己看代码吧 做了一点点注释 代码写的还是很清晰的
#include <iostream>
using namespace std;
#define red 1 //节点颜色
#define black 0
#define LL_rota 1 //操作
#define LR_rota 2
#define RL_rota 3
#define RR_rota 4
#define print_color(color) (color == red ? "Red " : "Black")
class node
{
private:
int val;
char color;
node* left;
node* right;
node* parent;
friend class RBTree; //友元类
public:
node(int val): val(val),color(red),left(nullptr),right(nullptr),parent(nullptr) {}
void change_color(char color)
{
if(!this) return;
this->color = color;
}
void swap_color(node* node) //颜色变换函数
{
if(!node) return;
char tmp_color = this->color;
this->change_color(node->color);
node->change_color(tmp_color);
}
void print_color_val() //递归中序遍历
{
if(!this) return;
left->print_color_val();
cout << "Val: " << (this->val) << ",Color: " << print_color(this->color) << ",Parent: " << (parent ? to_string(parent->val) : "Root") << endl;
right->print_color_val();
}
node* LLrotation() //LL转向
{
node* root = this->left,*left = this->left->left,*right = this,*root_right = root->right;
root->left = left;left->parent = root;
root->right = right;right->parent = root;
root->parent = nullptr;
right->left = root_right;
if(root_right) root_right->parent = right;
return root;
}
node* LRrotation() //LR转向
{
node* root = this->left->right,*left = this->left,*right = this,*root_left = root->left,*root_right = root->right;
root->left = left;left->parent = root;
root->right = right;right->parent = root;
root->parent = nullptr;
left->right = root_left;
if(root_left) root_left->parent = left;
right->left = root_right;
if(root_right) root_right->parent = right;
return root;
}
node* RRrotation() //RR转向
{
node* root = this->right,*left = this,*right = root->right,*root_left = root->left;
root->left = left;left->parent = root;
root->right = right;right->parent = root;
root->parent = nullptr;
left->right = root_left;
if(root_left) root_left->parent = left;
return root;
}
node* RLrotation() //RL转向
{
node* root = this->right->left,*left = this,*right = this->right,*root_left = root->left,*root_right = root->right;
root->left = left;left->parent = root;
root->right = right;right->parent = root;
root->parent = nullptr;
left->right = root_left;
if(root_left) root_left->parent = left;
right->left = root_right;
if(root_right) root_right->parent = right;
return root;
}
void insert_color_change(node** ptr) //二级指针方便递归时更改
{
if(this) color = red;
if(parent && parent->color == red && parent->parent && parent->parent->right && parent->parent->right->color == red)
{
node* pp = parent->parent;
pp->right->color = black;
pp->left->color = black;
pp->color = red;
*ptr = pp;
}
}
node* insert(node** tmp)
{
if(!this) return *tmp; //递归调用
node* ret = this;
int judge = 0;
if((*tmp)->val < val)
{
left = left->insert(tmp);
left->parent = this;
node* ptr = *tmp;
if(left->left == ptr) judge = LL_rota;
if(left->right == ptr) judge = LR_rota;
if(!judge || !ptr || ptr->parent->color == black) return ret;
if(right && right->color == red)
{
ptr->insert_color_change(tmp);
return ret;
}
if(judge == LL_rota)
{
swap_color(left);
ret = LLrotation();
*tmp = nullptr;
}
else
{
swap_color(ptr);
ret = LRrotation();
*tmp = nullptr;
}
}
else
{
right = right->insert(tmp);
right->parent = this;
node* ptr = *tmp;
if(right->left == ptr) judge = RL_rota;
if(right->right == ptr) judge = RR_rota;
if(!judge || ptr->parent->color == black) return ret;
if(left && left->color == red)
{
ptr->insert_color_change(tmp);
return ret;
}
if(judge == RR_rota)
{
swap_color(right);
ret = RRrotation();
*tmp = nullptr;
}
else
{
swap_color(ptr);
ret = RLrotation();
*tmp = nullptr;
}
}
return ret;
}
};
class RBTree
{
private:
node* root;
public:
RBTree():root(nullptr){}
void print()
{
if(!this) return;
root->print_color_val();
}
void insert_node(node* ptr)
{
node* tmp = ptr;
root = root->insert(&tmp);
if(root->color == red) root->color = black;
}
};
int main()
{
int insert_val;
RBTree rbtree;
cout << "the val inserts(ctrl+z stops,0 print rbtree):" << endl;
while((cin >> insert_val))
{
if(insert_val == 0)
rbtree.print();
else
{
node* new_node = new node(insert_val);
rbtree.insert_node(new_node);
}
}
return 0;
}
1、验证数据1（10个随机数数据）
31
42
23
9
75
5
10
65
81
26
0（0为输出）
1、验证结果（验证正确）
2、验证数据2（15位随机数数据）
41
144
769
849
972
1
78
75
61
517
527
718
319
96
43
0（0位输入数据）
2、验证结果（验证正确）
3、验证数据3（包含大量重复数据）
11
8
10
12
50
10
29
30
5
8
12
29
100
200
1
3
29
384
2882
2
2923
55
223
22
21
0（0为输出）
3、验证结果（验证正确）
结束语
终于把红黑树写完了 写完的时候忽然自己看了看时间 都晚上八点钟辣 还没吃晚饭 是时候去吃晚饭了 那就写到这里
我觉得这篇还是写的很详细很详细啦 希望能够offer u some help 自己也梳理了一遍二叉搜索树 及其好兄弟 对红黑树的历程到这里就算结束啦 后面还有对B树和B+树的分析 后面再花时间写了
那各位后面的博客再见啦 IT人也是需要去吃饭了 先走一步ε=ε=ε=┏(゜ロ゜;)┛
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
7
0- 0
已为社区贡献7条内容
所有评论(0)