【红黑树 -- 理论与实现】

news/2024/12/30 2:47:53/

目录：

前言

打怪升级：第88天
在这里插入图片描述

红黑树，可以说是树中的绝对大佬了，它和我们前一篇讲解的avl树一样，都属于二叉排序树，
avl树中我们通过记录平衡因子以及旋转来保证一棵树的绝对平衡，而今天所讲的红黑树则是通过给各个节点添加颜色属性来保证一棵树的平衡，那么下面我们就一起揭开红黑树神奇的面纱吧~。

注：三叉树的旋转操作在avl树中进行了讲解，此篇文章不再赘述，有需要的朋友可以跳转观看。

红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。
通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

在这里插入图片描述

红黑树的性质

  1. 每个节点不是红色就是黑色；
  2. 根节点是黑色的；
  3. 红色节点的两个孩子都是黑色；
  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点；
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)；

通过上面的五条性质我们可以得到那些信息呢？

  1. 红色节点的孩子只能是黑色的，黑色节点的孩子可以是红色也可以是黑色
  2. 从一个节点到其所有后代节点的路径上，均包含相同数目的黑色节点
    从这里我们是否可以得出最长路径与最短路径？
    – 答案是可以的，
    最短路径：全部都是黑色节点
    最长路径：每个黑色节点之间插入一个红色节点
    那么从这里我们就论证了红黑树的概念描述：没有一条路径会比其余路径长出两倍。
  • 红黑树节点的定义
enum Color  // 颜色枚举
{RED,BLACK
};// 1. 节点 -- 三叉链
template<class T>
struct _RBTree_Node
{_RBTree_Node(const T& val):_left(nullptr), _right(nullptr), _parent(nullptr), _val(val), _col(RED){}typedef _RBTree_Node<T> Node;Node* _left;Node* _right;Node* _parent;T _val;Color _col;
};

提一个小问题：节点初始化时为什么默认是红色的，黑色的可以吗？
– 要回答这个问题，我们就需要从五条性质出发来对比初始化为红色和黑色的影响；
首先我们看到，对于性质1，2，5都是没有任何影响的，
那么对于性质3：默认为红色，如果新插入节点的父节点是黑色，这次就插入成功了，但是如果新插入节点的父亲也是红色就会产生冲突，我们需要改变这两个节点的颜色，具体的下面我们会分析；
默认为黑色则不会出现两个节点都为红色的情况；
对于性质4：默认为红色，不会影响黑色节点的数量；
默认为黑色，那么每次新增节点都会影响这个分支上的黑色节点个数，我们每次都需要进行调整，使得各个支路黑色节点个数相同。

由此我们决定选择调整次数少的情况 – 也就是默认为红色节点的初始化方案。

插入过程遇到的情况

情况1 – 根节点

在这里插入图片描述

此时是一个空树，插入节点就是这棵树的根节点，插入结束后就要更改节点的颜色，保证根节点为黑色。

情况2 – parent为黑色

在这里插入图片描述

情况3 – parent为红色

当parent为红色的时候我们就要更改新增节点（cur）或者parent的颜色，以满足红黑树的性质3，
那么，我们到底是改变cur的颜色还是改变parent的颜色呢？
假设我们改变cur，那么此时和我们直接将节点初始化为黑色岂不是一样的，我们初始化为红色就没有意义了，
因此我们要来改变parent的颜色，把它变为黑色后这个分支好像又多了一个黑色节点，
那么我们想要让它减少一个黑色节点我们是不是就要进行往上调节啊，
我们再把在这里插入图片描述节点（爷爷 ，grand）改为红色，
如果这样改过之后该分支黑色节点该好了，但是，grand的另外一棵子树上就都少了一个黑色节点，
现在，我们还要让叔叔节点（父亲的兄弟 ， uncle）变为黑色即可，
说着很简单，但是谁说叔叔节点就一定是红色的，而且，叔叔存不存在还两说呢；
所以在这里就分出了很多中情况；

–
我们来理一理上面的思路：
1.parent为红色，那么我们一定有grand，因为根节点一定为黑色，parent为红色就一定不是根节点，所以一定存在祖先，并且祖先一定是黑色节点；
2.但是我们不一定有uncle，因此这里需要判断的就是nucle不存在、nucle为红色、以及uncle为黑色三种情况；
下面我们逐个分析。

uncle为红色

变色放案：新增节点不变色，parent与uncle变为黑色，grand变为红色；

上方变色方案走过一轮后grand的左右子树都调整结束了，但是grand变成了红色，我们就需要判断grand的parent是否为红色，继续往上走。。。

注：下方示例特殊了一些，往上迭代时uncle不一定还是红色的。
在这里插入图片描述

uncle为黑色

我们的变色规律为：parent、uncle变为黑色，uncle变为红色，当uncle也为红色的情况下我们可以保证各个分支的黑色节点个数不变，
但是，当uncle为黑色时，再进行变色就会使得nucle分支的黑色节点个数减少，如下图第二次变色：
那么为了使parent与uncle分支节点个数相同我们就需要保持parent不变，uncle分支黑色加一，
或者uncle分支不变，parent黑色节点个数减一，
但是我们就是从第二种情况下变换过来的，因此第二种丢弃，选择使uncle分支黑色节点加一，
这里我们就需要用到旋转，由于左边黑色节点个数多，我们就进行右旋。

情况1：
在这里插入图片描述
上方，我们之所以进行右旋，是因为左边的黑色节点个数多，因此我们就需要判断到底是哪个子树黑色节点多，也就是parent到底在grand的左边还是右边；

情况2：
那么下方这种情况，我们看到parent在grand的右边，右边黑色节点多，因此我们进行一次左旋，
但是左旋之后我们并没有得到预期的结果，如果大家继续按照“变色，旋转”的方法往后画会发现这是一个死循环，这里就不再一一画出。
在这里插入图片描述
那么为什么会出现这种情况，这里和上方第一种情况有何不同呢？ – cur 与parent的相对位置，与 parent与grand的相对位置不同！
第一种：cur为parent的左，parent为grand的左，因此进行旋转后parent变为新的根，cur与grand两个红色节点分别在他两侧；
上方这种：cur为parent的左，parent为grand的右，经过旋转后parent变为了新的根，但是cur和grand两个红色节点又连在了一起，
那么我们就需要避免这种情况的发生，如果我们将这种情况转换为第一种情况就可以将两者分开了，所以我们要对parent进行一次右旋，使得新的cur是parent的右，新的parent成为grand的右。
如图：
在这里插入图片描述
当出现双旋的情况时我们就要改变变色方案了，至于怎么更改就需要我们旋转之后往可以达到颜色平衡的情况下改变。

下方为单旋的详细流程图：
在这里插入图片描述

uncle不存在

uncle不存在的情况和uncle为黑的分析情况完全相同 – 变色方案是要将uncle变为黑色，而uncle不存在与uncle本就为黑时uncle都不需要改变，都会使得uncle分支少一个黑色节点。

在这里插入图片描述
在这里插入图片描述

插入过程代码实现

		// 插入bool Insert(const T& val){// 空树if (_root == nullptr){_root = new Node(val);_root->_col = BLACK; // 根节点为黑色++_node_const;return true;}// 查找是否存在Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_val < val){parent = cur;cur = cur->_right;}else if (cur->_val > val){parent = cur;cur = cur->_left;}elsereturn false; // 插入失败}cur = new Node(val);if (parent->_val < val)parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;++_node_const;// 调整节点while (parent && parent->_col == RED){Node* grand = parent->_parent;Node* uncle = nullptr;if (parent == grand->_left)uncle = grand->_right;elseuncle = grand->_left;if (uncle && uncle->_col == RED) // uncle 存在且为红色，uncle与parent变为黑色，grand变为红色{// 更新颜色uncle->_col = parent->_col = BLACK;grand->_col = RED;//  继续向上更新节点cur = grand;parent = grand->_parent;}else // uncle不存在 或者 uncle为黑色 ，依然采用上方的变色方案，特殊的是要进行旋转 -- 因为uncle分支黑色节点减少了{// 判断旋转策略if (cur == parent->_left){if (parent == grand->_left) // 右旋{//       g//    p     u// cRotateR(grand);parent->_col = BLACK;grand->_col = RED;}else // 右左双旋{//       g//   u       p     //        cRotateR(parent);RotateL(grand);cur->_col = BLACK;//parent->_col = BLACK;grand->_col = RED;}}else // cur == parent->_right{if (parent == grand->_right) // 左旋{//         g//     u      p  //		    cRotateL(grand);parent->_col = BLACK;grand->_col = RED;}else // 左右双旋{//          g//      p       u  //		  cRotateL(parent);RotateR(grand);cur->_col = BLACK;//parent->_col = BLACK;grand->_col = RED;}}}}// 根节点为黑色_root->_col = BLACK;return true;}// 旋转void RotateL(Node* cur) // 左旋{// 三组关系，四个节点Node* curR = cur->_right; Node* curRL = curR->_left;Node* curP = cur->_parent;curR->_left = cur;cur->_parent = curR;cur->_right = curRL;if (curRL) curRL->_parent = cur;if(curP){if (cur == curP->_left)curP->_left = curR;elsecurP->_right = curR;}else{_root = curR;}curR->_parent = curP;}void RotateR(Node* cur)  // 右旋{// 三组关系，四个节点Node* curL = cur->_left;Node* curLR = curL->_right;Node* curP = cur->_parent;curL->_right = cur;cur->_parent = curL;cur->_left = curLR;if (curLR) curLR->_parent = cur;if (curP){if (cur == curP->_left)curP->_left = curL;elsecurP->_right = curL;}else{_root = curL;}curL->_parent = curP;}

分析红黑树是否构建成功

  1. 中序遍历是否为排序树
		void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr) return;_InOrder(root->_left);cout << root->_val << ' ';_InOrder(root->_right);}
  1. 判断是否符合红黑树性质
		void IsRBTree() // 判断是否符合红黑树的条件{if (_root->_col == RED) // 跟节点为黑色cerr << "_root color error" << endl;_IsRBTree(_root);}void _IsRBTree(Node* root) // 检测是否红黑树{if (root == nullptr) return;// 1. 左右子树高度差 -- 2倍int lenL = Height(root->_left);int lenR = Height(root->_right);if (lenL < lenR) swap(lenL, lenR);if (lenL > lenR * 2) cerr <<"节点" << root->_val  << ", height error" << endl;// 2. 红色节点的孩子不能为红色TowRed(root);// 3. 黑色节点个数相同BlackCnt(root);_IsRBTree(root->_left);_IsRBTree(root->_right);}int Height(Node* root){if (root == nullptr) return 1; // 空节点算作黑节点int lenL = Height(root->_left);int lenR = Height(root->_right);return (lenL > lenR ? lenL : lenR) + 1;}void TowRed(Node* root){if (root->_col == RED){if (root->_left && root->_left->_col == RED)cerr << "节点" << root->_val << ", left color error" << endl;if (root->_right && root->_right->_col == RED)cerr << "节点" << root->_val << ", right color error" << endl;}}void BlackCnt(Node* root){Node* lnode = root->_left;Node* rnode = root->_right;int lcnt = 0;int rcnt = 0;while (lnode){if (lnode->_col == BLACK) ++lcnt;lnode = lnode->_left;}while (rnode){if (rnode->_col == BLACK) ++rcnt;rnode = rnode->_right;}if (lcnt != rcnt)cerr << "节点" << root->_val << ", black count error" << endl<< lcnt << " " << rcnt << endl;}
  1. 测试
void Test_rbTree1()
{srand((unsigned int)time(0));kz::RBTree<int> t;for (int i = 0; i < 20; ++i){t.Insert(rand() % 100);}t.InOrder(); // 中序遍历打印结果t.IsRBTree(); // 判断是否为红黑树
}void Test_rbTree2()
{srand(time(0));kz::RBTree<int> t;for (int i = 0; i < 10000; ++i){t.Insert(rand());}t.IsRBTree();
}int main()
{Test_rbTree1();cout << "------------------ - " << endl;Test_rbTree2();return 0;
}

这里是引用

总结

以上就是我们关于红黑树概念以及变色、旋转的全部内容，红黑树的旋转和avl的旋转都是一样的，不一样的一点就是红黑树旋转更新节点颜色，avl旋转更新节点的平衡因子。
红黑树是近似平衡，avl则是绝对平衡，而为了达到绝对的平衡自然就需要进行更多的旋转操作，所以avl在插入过程中会消耗大量的时间，
而因为是绝对平衡的，树的高度接近完全二叉树，查找的效率自然就会提高很多，
不过由于二叉树查找效率为logN，
在10亿个数据中进行查找也只需要查找30次，由于红黑树允许1倍左右的高度差，因此10亿个数据最多可能需要查找60次，
而这中间的30次查找对于cpu来说简直可以忽略不计，由于绝对平衡调整时间消耗大而且查找优势也并不明显，因此我们平时很少使用avl，而更多的使用红黑树。

  • 红黑树的应用
  1. C++ STL库 – map/set、mutil_map/mutil_set
  2. Java 库
  3. linux内核
  4. 其他一些库

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

相关文章

202313读书笔记|《山居七年》——我只想在广袤璀璨的星河里享受生的鲜活，独自飞，游走

202313读书笔记|《山居七年》——我只想在广袤璀璨的星河里享受生的鲜活，独自飞，游走

202313读书笔记|《山居七年》——我只想在广袤璀璨的星河里享受生的鲜活&#xff0c;独自飞&#xff0c;游走 《山居七年》 作者张二冬&#xff0c;选择隐士山居是一种很自由随性的生活态度&#xff0c;我觉得这不是普通人可以拥有的&#xff0c;比如我&#xff0c;并未入世也…
阅读更多...
小航编程题库蓝桥杯stem科技素养模拟练习试卷（初级第1套）（含题库教师学生账号）

小航编程题库蓝桥杯stem科技素养模拟练习试卷（初级第1套）（含题库教师学生账号）

需要在线模拟训练的题库账号请点击 小航助学编程在线模拟试卷系统&#xff08;含题库答题软件账号&#xff09;_程序猿下山的博客-CSDN博客 1. 以下选项中&#xff0c;&#xff08; &#xff09;不属于生物。 A 玫瑰花 B 河流 C 蜜蜂 D 人 2. 以下选项中&#xff0c;&…
阅读更多...
傅一平：一文讲透ERP的下一代架构！

傅一平：一文讲透ERP的下一代架构！

”5月22日&#xff0c;华为宣布仅用15小时便完成了全球88家子公司MetaERP系统的切换。这也意味着华为MetaERP系统研发取得胜利&#xff0c;成功摆脱外国供应商断供停服威胁&#xff0c;实现该系统的全栈自主可控。“ 自己最近对ERP下一代架构有了兴趣&#xff0c;原因有四个&am…
阅读更多...
docker版jxTMS使用指南：python服务之内置自动机

docker版jxTMS使用指南：python服务之内置自动机

本文讲解4.0版的jxTMS中python服务的内置自动机&#xff0c;整个系列的文章请查看&#xff1a;docker版jxTMS使用指南&#xff1a;4.0版升级内容 docker版本的使用&#xff0c;请参考&#xff1a;docker版jxTMS使用指南 4.0版jxTMS中python服务是一个采集前端数据的接口机。其…
阅读更多...
美国E8267C是德（KEYSIGHT) E8267D 20G/44G矢量信号发生器

美国E8267C是德（KEYSIGHT) E8267D 20G/44G矢量信号发生器

Agilent E8267C、Keysight E8267D、 PSG 矢量信号发生器&#xff0c;高达 44 GHz ​Keysight E8267D (Agilent) PSG 矢量信号发生器是业界首款 I/Q 调制高达 44 GHz 的集成微波矢量信号发生器。它具有先进的宽带内部基带发生器&#xff0c;能够灵活地播放任意波形或生成复杂的…
阅读更多...
33.C++函数重载

33.C++函数重载

今天进行了新的学习。 目录 1.什么是函数重载&#xff1f; 2.函数重载的规则 代码演示&#xff1a; 分析&#xff1a; 3.为什么C能进行函数重载 例如&#xff1a; 调用约定&#xff1a; 4.extern关键字 1.什么是函数重载&#xff1f; 在同一个作用域内&#xff0c…
阅读更多...
【分布族谱】卡方分布和F分布之间的关系

【分布族谱】卡方分布和F分布之间的关系

文章目录 正态分布和卡方分布F分布 正态分布和卡方分布 正态分布&#xff0c;最早由棣莫弗在二项分布的渐近公式中得到&#xff0c;而真正奠定其地位的&#xff0c;应是高斯对测量误差的研究&#xff0c;故而又称Gauss分布。。测量是人类定量认识自然界的基础&#xff0c;测量…
阅读更多...
【C++系列P1】带上这篇基础小宝典，进发C++！(持续更新ing~）

【C++系列P1】带上这篇基础小宝典，进发C++！(持续更新ing~）

​​​​​​​ 前言 大家好吖&#xff0c;欢迎来到 YY 滴 C系列 &#xff0c;热烈欢迎&#xff01;(持续更新ing~&#xff09;本章主要内容面向刚刚学完C语言&#xff0c;准备或正在接触C的老铁。而往往C奇多的小特性和知识点让铁铁们头晕晕脑涨涨&#xff0c;因而本章收纳了…
阅读更多...
最新文章

Copyright @ 2022~2023