手撕红黑树 | 变色+旋转你真的明白了吗？【超用心超详细图文解释 | 一篇学会Red_Black_Tree】

news/2024/12/29 3:05:36/

说在前面

我们也很久没有更新数据结构系列了，半年前博主重新深入学习了红黑树这个数据结构，一直想更新呈现给大家，最近也一直没有时间，今天红黑树它来了！

博主为了这篇博客，做了很多准备，试了很多画图软件，就是为了让大家看得明白！希望大家不要吝啬一键三连啊！！

前言

那么这里博主先安利一下一些干货满满的专栏啦！

手撕数据结构https://blog.csdn.net/yu_cblog/category_11490888.html?spm=1001.2014.3001.5482这里包含了博主很多的数据结构学习上的总结，每一篇都是超级用心编写的，有兴趣的伙伴们都支持一下吧！
算法专栏https://blog.csdn.net/yu_cblog/category_11464817.html这里是STL源码剖析专栏，这个专栏将会持续更新STL各种容器的模拟实现。

STL源码剖析https://blog.csdn.net/yu_cblog/category_11983210.html?spm=1001.2014.3001.5482

什么是红黑树？

在学习红黑树之前，我们必须先了解和熟悉AVL树：

万字手撕AVL树 | 上百行的旋转你真的会了吗？【超用心超详细图文解释 | 一篇学会AVL】https://blog.csdn.net/Yu_Cblog/article/details/127698306?spm=1001.2014.3001.5501红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。

因此，红黑树不是直接通过检验【没有一条路径会比其他路径长出2倍】而维护平衡的，而是通过对根到叶子路径上节点的着色的限制！它不是像AVL一样直接控制平衡，而是间接控制平衡。

红黑树的性质

  • 每个结点不是红色就是黑色
  • 根节点是黑色的
  • 如果一个节点是红色的，则它的两个孩子结点是黑色的
  • 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
  • 每个叶子结点都是黑色的(此处的叶子结点指的是空结点（NIL节点）)

红黑树节点结构

同样，红黑树也是使用三叉链进行构造

enum Colour {RED,BLACK
};
template<class K,class V>
struct __Red_Black_TreeNode {__Red_Black_TreeNode<K, V>* _left;__Red_Black_TreeNode<K, V>* _right;__Red_Black_TreeNode<K, V>* _parent;pair<K, V>_kv;Colour _col;__Red_Black_TreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv) {}
};

红黑树的插入（重点）

首先插入节点，前面的部分和搜索树和AVL一样，找位置插入即可：

	bool insert(const pair<K, V>& kv) {if (_root == nullptr) {_root = new Node(kv);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur) {if (cur->_kv.first < kv.first) {parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first) {parent = cur;cur = cur->_left;}else return false;}cur = new Node(kv);cur->_col = RED;//一开始尽量先变红if (parent->_kv.first < kv.first) {parent->_right = cur;}else {parent->_left = cur;}cur->_parent = parent;//判断是否需要调整颜色或旋转while (...) {//...}//根据规则，最后的根节点一定是黑色的_root->_col = BLACK;//最后无论根是红是黑 -- 都处理成黑return true;}

在插入这部分，我们要牢牢记住红黑树的两个规则，这是我们插入节点最根本的根据！

  • 规则三:如果一个节点是红色的，那它的孩子是黑色的
  • 规则四:对于每一个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点

插入的新节点默认是红色

现在我们要插入一个新的节点

我们可以分为两种情况：

  • 插入节点的父亲是黑色的
  • 插入节点的父亲是红色的 

如果插入节点的父亲是黑色的，我们插入黑色节点就会违反规则4，插入红节点并不违反规则，所以我们应该插入的节点应该设置成红色。

如果插入节点的父亲是红色的，我们插入黑色节点就会违反规则4，插入红节点违反规则3。此时我们应该插入什么颜色的节点呢？

答案是我们应该插入红色节点，再做后续的变色工作。

原因：如果插入黑色节点，我们违反规则4，相当于整棵树违法了规则。而我们违反规则3，我们可以通过局部的调整颜色或者旋转解决问题，因此我们选择先把新节点设置成红色，再做变色（+旋转）的处理。

因此，在红黑树中插入一个新节点，无论什么情况，先设置成红色！

变色和旋转

当我们插入一个红节点之后，我们就要检查这颗红黑树是否符合规则了。

如果插入节点的父亲是黑色，是不违反红黑树规则的，我们不需要做处理。

下面我们重点讨论：插入节点的父亲为红色的情况。

红黑树处理情况分类所要关注的节点：父亲、祖父和叔叔（叔叔为父亲的兄弟节点）

我们把握好父亲祖父和叔叔，就能处理红黑树的所有状况。其中，叔叔的颜色最为关键！

下面是红黑树调整的三种情况：

约定cur为当前节点，p为父亲节点，g为祖父节点，u为叔叔节点。

情况一：cur为红，p为红，g为黑，u存在且为红

处理如下：

tips：我们可以发现，这个情况是不需要看左右的，cur在p的左或右，处理的方式其实都是一样的。

情况二: cur为红，p为红，g为黑，u不存在/u为黑（且cur,p,g在同一直线上）

在情况一中，我们把父亲变黑的时候，可以把叔叔一起拉下水，让叔叔也变黑，这样我们就能保证路径上的黑色节点个数保持一致。

但是现在，叔叔不存在或叔叔已经是黑色的了，此时只能旋转了。

 

说明: u的情况有两种

  1. 如果u节点不存在，则cur一定是新插入节点，因为如果cur不是新插入节点则cur和p一定有一个节点的颜色是黑色，就不满足性质4: 每条路径黑色节点个数相同
  2. 如果u节点存在，则其一定是黑色的，那么cur节点原来的颜色一定是黑色的现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色。

p为g的左孩子，cur为p的左孩子，则进行右单旋转;

相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转

p、g变色--p变黑，g变红 

因为cur,p,g在同一直线上，所以情况二只需要单旋！下面这种情况就需要双旋了！

情况三: cur为红，p为红，g为黑，u不存在/u为黑（且cur,p,g不在同一直线上）

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，
p为g的右孩子，cur为p的左孩子，则针对p做右单旋转
则转换成了情况2 

红黑树的删除等

讲到这里有伙伴可能会问,为什么讲红黑树,不讲删除那些接口呢?

因为,校招,公司面试,以后工作中都基本不会考察到AVL树和红黑树的删除接口，我们只需要掌握插入接口就行了。

AVL树,红黑树我们都是做了解性学习,我们并不需要去手撕它的全部代码,这样时间成本很大,意义不大.我们学习红黑树,我们需要深入的去理解它的结构,学习一个插入接口,我们已经可以很好的做到这一点了。

检查红黑树是否合法

思路：找到最左向下路径的黑色节点数作为基准值，检查每条路径黑色节点数目是否与基准值相等。

    bool prev_check(Node* root, int blackNum,int bench_mark) {if (root == nullptr) {if (blackNum != bench_mark)return false;return true;}if (root->_col == BLACK) {blackNum++;}if (root->_col == RED && root->_parent->_col == RED) {//存在连续的红节点，return falsereturn false;}return prev_check(root->_left, blackNum, bench_mark) &&prev_check(root->_right, blackNum, bench_mark);}bool is_balance() {if (_root == nullptr)return true;if (_root->_col == RED)return false;//黑色节点数量基准值int bench_mark = 0;Node* cur = _root;while (cur) {if (cur->_col == BLACK)++bench_mark;cur = cur->_left;}return prev_check(this->_root, 0, bench_mark);}

RBTree.h

#pragma once
//#include<map>
#include<iostream>
#include<assert.h>
using namespace std;enum Colour {RED,BLACK
};
template<class K,class V>
struct __Red_Black_TreeNode {__Red_Black_TreeNode<K, V>* _left;__Red_Black_TreeNode<K, V>* _right;__Red_Black_TreeNode<K, V>* _parent;pair<K, V>_kv;Colour _col;__Red_Black_TreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv) {}
};template<class K, class V>
struct RBTree {typedef __Red_Black_TreeNode<K, V>Node;
private:Node* _root = nullptr;
private://左单旋void rotate_left(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL) {subRL->_parent = parent;}Node* ppNode = parent->_parent;//记录一下原先parent的parentsubR->_left = parent;parent->_parent = subR;if (_root == parent) {_root = subR;subR->_parent = nullptr;}else {//如果ppNode==nullpt，是不会进来这里的if (ppNode->_left == parent) {ppNode->_left = subR;}else {ppNode->_right = subR;}subR->_parent = ppNode;}}//右单旋void rotate_right(Node* parent) {Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR) {subLR->_parent = parent;}Node* ppNode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent) {_root = subL;subL->_parent = nullptr;}else {if (ppNode->_left == parent) {ppNode->_left = subL;}else {ppNode->_right = subL;}subL->_parent = ppNode;}}void _inorder(Node* root) {if (root == nullptr)return;_inorder(root->_left);cout << root->_kv.first << endl;_inorder(root->_right);}bool prev_check(Node* root, int blackNum,int bench_mark) {if (root == nullptr) {if (blackNum != bench_mark)return false;return true;}if (root->_col == BLACK) {blackNum++;}if (root->_col == RED && root->_parent->_col == RED) {//存在连续的红节点，return falsereturn false;}return prev_check(root->_left, blackNum, bench_mark) &&prev_check(root->_right, blackNum, bench_mark);}
public:bool is_balance() {if (_root == nullptr)return true;if (_root->_col == RED)return false;//黑色节点数量基准值int bench_mark = 0;Node* cur = _root;while (cur) {if (cur->_col == BLACK)++bench_mark;cur = cur->_left;}return prev_check(this->_root, 0, bench_mark);}
public:void inorder() {this->_inorder(this->_root);cout << "\n";}//前面插入的过程和搜索树一样的bool insert(const pair<K, V>& kv) {if (_root == nullptr) {_root = new Node(kv);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur) {if (cur->_kv.first < kv.first) {parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first) {parent = cur;cur = cur->_left;}else return false;}cur = new Node(kv);cur->_col = RED;//一开始尽量先变红if (parent->_kv.first < kv.first) {parent->_right = cur;}else {parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED) {Node* grandparent = parent->_parent;assert(grandparent && grandparent->_col == BLACK);//关键看叔叔//判断一下左右if (parent == grandparent->_left) {Node* uncle = grandparent -> _right;//情况1（不看方向）if (uncle && uncle->_col == RED) {parent->_col = uncle->_col = BLACK;grandparent->_col = RED;//继续向上处理cur = grandparent;parent = cur->_parent;}//情况2+3//uncle不存在/存在且为黑else {//情况2//   g//  p  u// c//右单旋+变色if (cur == parent->_left) {rotate_right(grandparent);parent->_col = BLACK;//父亲变黑grandparent->_col = RED;//祖父变红}//情况3//   g//  p  u//   c//左右双旋+变色else {rotate_left(parent);rotate_right(grandparent);//看着图写就行了cur->_col = BLACK;grandparent->_col = RED;}break;}}else {Node* uncle = grandparent->_left;//情况1（不看方向）if (uncle && uncle->_col == RED) {parent->_col = uncle->_col = BLACK;grandparent->_col = RED;//继续向上处理cur = grandparent;parent = cur->_parent;}else {//情况2//   g//  u  p//      c //左单旋+变色if (cur == parent->_right) {rotate_left(grandparent);parent->_col = BLACK;//父亲变黑grandparent->_col = RED;//祖父变红}//情况3//   g//  u  p//    c//右左双旋+变色else {rotate_right(parent);rotate_left(grandparent);//看着图写就行了cur->_col = BLACK;grandparent->_col = RED;}break;}}}_root->_col = BLACK;//最后无论根是红是黑 -- 都处理成黑return true;}
};void test1() {int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };RBTree<int, int>t1;for (auto e : a) {t1.insert(make_pair(e, e));}t1.inorder();cout << "is_balance():" << t1.is_balance() << endl;
}
void test2() {size_t N = 10000;srand((unsigned)time(nullptr));RBTree<int, int>t1;for (size_t i = 0; i < N; ++i) {int x = rand();t1.insert(make_pair(x, i));}cout << "is_balance():" << t1.is_balance() << endl;
}

总结

看到这里,大家应该对红黑树的实现,重点是它的旋转有了比较深入的了解了。这篇博客博主花了很多心思在画图上，也投入了很多时间到画图上。下期给大家带来map/set的封装。希望大家可以多多支持，一键三连，点赞关注收藏评论后在离开哦!

( 转载时请注明作者和出处。未经许可，请勿用于商业用途 )
更多文章请访问我的主页

@背包https://blog.csdn.net/Yu_Cblog?type=blog


http://www.ppmy.cn/news/2184.html

相关文章

redis常用数据类型以及命令详细介绍

redis常用数据类型以及命令详细介绍

查询redis的命令&#xff1a;http://www.redis.cn/commands.html Redis键(key) keys *查看当前库所有key (匹配&#xff1a;keys *1) exists key判断某个key是否存在 type key 查看你的key是什么类型 del key 删除指定的key数据 unlink key 根据value选择非阻塞删除 仅将keys…
阅读更多...
基于训练和推理场景下的MindStudio高精度对比

基于训练和推理场景下的MindStudio高精度对比

摘要&#xff1a;MindStudio提供精度比对功能&#xff0c;支持Vector比对能力。本文分享自华为云社区《【MindStudio训练营第一季】MindStudio 高精度对比随笔》&#xff0c;作者&#xff1a;Tianyi_Li。 训练场景下&#xff0c;迁移原始网络 (如TensorFlow、PyTorch) &#x…
阅读更多...
8年三届世界杯，8年前端开发，梅西一共踢没了我八千八

8年三届世界杯，8年前端开发，梅西一共踢没了我八千八

转眼2022年即将过去&#xff0c;我已经做了那么久的开发了&#xff0c;一路走来&#xff0c;不断的工作&#xff0c;换工作&#xff0c;找工作&#xff0c;不断的学习新知识。 同时也看着梅西参加了3届世界杯了&#xff0c;逝者如斯夫&#xff0c;不舍昼夜啊。 在这8年里&#…
阅读更多...
INS 、AHRS、VRU、IMU的区别与联系

INS 、AHRS、VRU、IMU的区别与联系

这篇博客主要是想自己理一下这几个概念&#xff0c;从简单到复杂进行阐述。 IMU&#xff08;Inertial Measurement Unit&#xff09;&#xff1a; 即“惯性测量单元”&#xff0c;一般来说IMU仅包含陀螺仪和加速度计。陀螺仪输出载体相对于惯性系的旋转角速率或者角增量&#…
阅读更多...
基于RRT算法的最优动力学路径规划（Matlab代码实现）

基于RRT算法的最优动力学路径规划（Matlab代码实现）

目录 &#x1f4a5;1 概述 &#x1f4da;2 运行结果 &#x1f389;3 参考文献 &#x1f468;‍&#x1f4bb;4 Matlab代码 &#x1f4a5;1 概述 RRT是Steven M. LaValle和James J. Kuffner Jr.提出的一种通过随机构建Space Filling Tree实现对非凸高维空间快速搜索的算法。…
阅读更多...
openGauss数据库的安装部署

openGauss数据库的安装部署

目录前言1. 安装环境准备2. 创建用户和用户组3. 正式安装4. 启动数据库实例并测试前言 这里主要结合官网的文档&#xff0c;安装系统环境是官网推荐的openEuler 20.03LTS,openGauss数据库版本是openGauss 2.0.0&#xff08;这里没有使用最新的3.0.1版本&#xff09;&#xff0…
阅读更多...
Android11 有线网Score分析流程

Android11 有线网Score分析流程

Android 11 有线网Score分析流程 本文只对有线网score分值流程做详细分析。 一、前言&#xff1a; 之前搞Android 有线网络和wifi&#xff0c;同时连通&#xff0c;并且设置优先级。已实现可以随时切换网络优先级。 刚开始是生效的&#xff0c;系统合入新TAG后&#xff0c;发…
阅读更多...
jsp528口腔牙医诊所预约挂号ssm+mysql Springboot

jsp528口腔牙医诊所预约挂号ssm+mysql Springboot

随着科学技术的飞速发展&#xff0c;社会的方方面面、各行各业都在努力与现代的先进技术接轨&#xff0c;通过科技手段来提高自身的优势&#xff0c;口腔管理平台当然也不能排除在外。口腔管理平台是以实际运用为开发背景&#xff0c;运用软件工程原理和开发方法&#xff0c;采…
阅读更多...
最新文章

Copyright @ 2022~2023