🔥🔥 欢迎来到小林的博客！！
🛰️博客主页：✈️小林爱敲代码
🛰️博客专栏：✈️数据结构与算法
🛰️欢迎关注：👍点赞🙌收藏✍️留言
今天给大家讲解红黑树，和AVL树一样，这章暂且不讲删除。后续有时间会为大家带来红黑树的删除操作。
每日一句: 生活原本沉闷，但跑起来就会有风。
目录
红黑树，是一种二叉搜索树，与AVL树不同的是，它在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。因此红黑树相比于AVL树，没有那么平衡。30层高度的AVL树换成红黑树可能会有60层，但查找30次和60次并没有什么区别。AVL树的平衡是付出了代价的，它旋转的次数更多了。而红黑树也是平衡的，它旋转的次数并没有AVL多。
红黑树必须满足以下五点性质，有一条不满足，就不是红黑树了。
1.每个节点不是红色就是黑色
2.根节点是黑色的
3.红节点的孩子必须是黑色
4.每条路径黑色节点的数量相同
5.空节点都是黑色的
满足上面性质的红黑树，它的最长路径中节点的个数不会超过最短路径的2倍
那我们先来观赏一颗红黑树
我们可以发现，
每个节点不是黑色就是红色，满足条件1
根节点 50 是黑色的，满足条件2
红色节点的孩子都是黑色，满足条件3
每条路径都有2个黑色节点，满足条件4
所有空节点的孩子都是黑色，不过是空节点，就不需要画出来了。
介绍完红黑树之后，接下来我们来实现一颗红黑树。
首先，我们依旧采用三叉链，一个指针指向左孩子，一个指向右孩子，还有一个指向自己的父亲。再用一个枚举常量col 来记录节点的颜色，kv是存储的一对值。
代码：
enum Color
{
RED,
BLACK
};
//红黑树节点
template<class K,class V>
struct RBTreeNode
{
RBTreeNode(const pair<K,V>& kv)
: _left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
,_kv(kv){}
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Color _col;
pair<K, V> _kv;
};
红黑树的定义很简单，我们存一个节点指针_root来代表整棵树的根。
//红黑树实现
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
RBTree():_root(nullptr){}
private:
Node* _root;
};
个人认为，红黑树的插入并没有AVL那么繁琐。AVL插入时需要考虑的情况太多，而红黑树并不需要考虑太多情况。
假设我们有一颗红黑树
那么接下来我们要插入一个10，那么10应该插入20的左边。那么我们让新插入的节点颜色固定为10。根节点颜色固定为黑。
那么我们发现在插入10之后，这颗红黑树是还是正常的，满足了5条性质。此时我们在插入1个25。
我们发现插入25之后，这棵树还是正常的。所以我们可以得出一个结论，如果插入节点的父亲是黑色，那么这是一颗正常的红黑树。
那么我们此时再插入一个5，它的父亲节点就是10，也就是红色。
这种情况，这颗红黑树就不满足性质3了，因为红节点的孩子必须是黑节点。那么此时我们看它的叔叔，叔叔是25。
那么此时就会出现2种情况
情况1.叔叔存在且为红色
这种情况我们只需要把父亲和叔叔变成黑色，然后把祖父变红，再把cru给祖父，循环操作直到父亲为空即可。
这种操作会把我们的根节点变成红色，所以我们在最后的时候强制把根节点变成黑色即可。
最后这颗红黑树就会变成这样
我们可以发现它依然满足上面的五个性质。
情况2.叔叔不存在或者叔叔为黑色
叔叔不存在或者叔叔为黑色的情况是一样的。
我们先来看叔叔不存在的情况。
叔叔不存在
那么这颗红黑树是这样的
这种情况我们就要发生旋转了，因为叔叔不存在，就意味着这颗红黑树已经左边一边高了。所以我们来个右单旋即可。在右边就左单旋，具体的旋转细节可以看我上篇讲解AVL树的文章。
旋转完之后是这样的
这时候我们在把 c(新增节点) 和 g(祖父节点)变成红色，再把p(父亲节点)变为黑色。这颗红黑树就调整完毕了。
叔叔为黑的情况
叔叔为黑和叔叔不存在的情况是一样的。
我们来看看叔叔为黑的情况。
这时候我们一样要发生旋转。
旋转动图：
然后我们再把c和g变为红色，p变为黑色
这样我们的红黑树就调整完毕了。这是我们的parent在左边，uncle在右边的情况。反过来的逻辑也是一样的。
插入代码：
bool insert(const pair<K,V> kv)
{
//第一次插入
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
//先查找值的位置
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
break;
}
//如果cur不为空说明有重复的值
if (cur)
return false;
//创建新节点
cur = new Node(kv);
cur->_parent = parent;
if (cur->_kv.first > parent->_kv.first)
parent->_right = cur;
else
parent->_left = cur;
cur->_col = RED;
//有连续的红节点,需要调整
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;//祖父节点
//parent是左孩子的情况
if (parent == grandparent->_left)
{
// 叔叔节点
Node* uncle = grandparent->_right;
//如果叔叔存在且为红
if (uncle && uncle->_col == RED)
{
//父亲和叔叔变黑
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
//迭代
cur = grandparent;
parent = cur->_parent;
}
else
{
//叔叔为黑或者叔叔不存在
if (cur == parent->_left)
{
//右单旋
RotateR(grandparent); //旋转祖父
parent->_col = BLACK;
grandparent->_col = cur->_col = RED;
}
else
{
//左右双旋
RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
parent->_col = grandparent->_col = RED;
}
}
}
else
{
//parent是右孩子的情况
Node* uncle = grandparent->_left;
//叔叔存在且为红
if (uncle && uncle->_col == RED)
{
uncle->_col = parent->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else
{
//叔叔不存在或为黑
if (cur = parent->_right)
{
//左单旋
RotateL(grandparent);
grandparent->_col = cur->_col = RED;
parent->_col = BLACK;
}
else
{
//右左双旋
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
parent->_col = grandparent->_col = RED;
}
}
}
}
_root->_col = BLACK; //不管如何，根节点的颜色一定为黑
return true;
}
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = parent->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* grandparent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (grandparent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parent == grandparent->_left)
grandparent->_left = subL;
else
grandparent->_right = subL;
subL->_parent = grandparent;
}
}
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* grandparent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (grandparent == nullptr)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (grandparent->_left == parent)
grandparent->_left = subR;
else
grandparent->_right = subR;
subR->_parent = grandparent;
}
}
插入都会了，查找不是轻轻松松。从根开始找，要找的值比当前节点大，就往这棵树的右边找，小就往左边找，找到了就返回。
pair<K, V>* find(const K& key)
{
if (_root == nullptr)
return nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > key)
cur = cur->_left;
else if (cur->_kv.first < key)
cur = cur->_right;
else
return &cur->_kv;
}
return nullptr;
}
当我们代码写出来了之后，还要检查这棵树是否是红黑树。我们可以先找一个基准值(任意一条路径的黑节点数量)。因为红黑树每条路径的黑节点个数是一样的。然后我们有基准值之后，在遍历的过程计算黑节点的数量。如果与基准值一样，那么这棵树所有路径黑节点的数量是相同的。
//检查红黑树是否正常
bool IsBalance()
{
if (_root->_col == RED)
{
cout << "根节点为红色" << endl;
return false;
}
//找基准值
Node* min = _root;
int banchmark = 0;
while (min)
{
if (min->_col == BLACK)
banchmark++;
min = min->_left;
}
return _IsBalance(_root,banchmark,0);
}
bool _IsBalance(Node* root,int banchmark,int BNNum)
{
if (root == nullptr)
{
if (banchmark != BNNum)
{
cout << "路径中黑节点数量不相等" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "出现连续红节点"<<endl;
return false;
}
if (root->_col == BLACK)
BNNum++;
return _IsBalance(root->_left, banchmark, BNNum) &&
_IsBalance(root->_right, banchmark, BNNum);
}
全部代码：
#include<iostream>
using namespace std;
#include<time.h>
namespace wyl
{
enum Color
{
RED,
BLACK
};
//红黑树节点
template<class K,class V>
struct RBTreeNode
{
RBTreeNode(const pair<K,V>& kv)
: _left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
,_kv(kv){}
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Color _col;
pair<K, V> _kv;
};
//红黑树实现
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
RBTree():_root(nullptr){}
bool insert(const pair<K,V> kv)
{
//第一次插入
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
//先查找值的位置
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
break;
}
//如果cur不为空说明有重复的值
if (cur)
return false;
//创建新节点
cur = new Node(kv);
cur->_parent = parent;
if (cur->_kv.first > parent->_kv.first)
parent->_right = cur;
else
parent->_left = cur;
cur->_col = RED;
//有连续的红节点,需要调整
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;//祖父节点
//parent是左孩子的情况
if (parent == grandparent->_left)
{
// 叔叔节点
Node* uncle = grandparent->_right;
//如果叔叔存在且为红
if (uncle && uncle->_col == RED)
{
//父亲和叔叔变黑
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
//迭代
cur = grandparent;
parent = cur->_parent;
}
else
{
//叔叔为黑或者叔叔不存在
if (cur == parent->_left)
{
//右单旋
RotateR(grandparent); //旋转祖父
parent->_col = BLACK;
grandparent->_col = cur->_col = RED;
}
else
{
//左右双旋
RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
parent->_col = grandparent->_col = RED;
}
}
}
else
{
//parent是右孩子的情况
Node* uncle = grandparent->_left;
//叔叔存在且为红
if (uncle && uncle->_col == RED)
{
uncle->_col = parent->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else
{
//叔叔不存在或为黑
if (cur = parent->_right)
{
//左单旋
RotateL(grandparent);
grandparent->_col = cur->_col = RED;
parent->_col = BLACK;
}
else
{
//右左双旋
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
parent->_col = grandparent->_col = RED;
}
}
}
}
_root->_col = BLACK; //不管如何，根节点的颜色一定为黑
return true;
}
pair<K, V>* find(const K& key)
{
if (_root == nullptr)
return nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > key)
cur = cur->_left;
else if (cur->_kv.first < key)
cur = cur->_right;
else
return &cur->_kv;
}
return nullptr;
}
//检查红黑树是否正常
bool IsBalance()
{
if (_root->_col == RED)
{
cout << "根节点为红色" << endl;
return false;
}
//找基准值
Node* min = _root;
int banchmark = 0;
while (min)
{
if (min->_col == BLACK)
banchmark++;
min = min->_left;
}
return _IsBalance(_root,banchmark,0);
}
private:
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = parent->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* grandparent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (grandparent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parent == grandparent->_left)
grandparent->_left = subL;
else
grandparent->_right = subL;
subL->_parent = grandparent;
}
}
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* grandparent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (grandparent == nullptr)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (grandparent->_left == parent)
grandparent->_left = subR;
else
grandparent->_right = subR;
subR->_parent = grandparent;
}
}
bool _IsBalance(Node* root,int banchmark,int BNNum)
{
if (root == nullptr)
{
if (banchmark != BNNum)
{
cout << "路径中黑节点数量不相等" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "出现连续红节点"<<endl;
return false;
}
if (root->_col == BLACK)
BNNum++;
return _IsBalance(root->_left, banchmark, BNNum) &&
_IsBalance(root->_right, banchmark, BNNum);
}
private:
Node* _root;
};
//以下是红黑树的测试代码
void RBTTest1()
{
RBTree<int, int> rb;
srand(time(0));
int N = 10000000;
size_t begin1 = clock();
for (int i = 0; i < N; i++)
{
rb.insert(make_pair(i, i));
}
size_t end1 = clock();
cout << "insert " << N << ":" << end1 - begin1 << endl;
//rb.insert(make_pair(20, 20));
//rb.insert(make_pair(10, 10));
//rb.insert(make_pair(5, 5));
//rb.insert(make_pair(3, 3));
rb.IsBalance();
}
}
💦💦如果有写的有什么不好的地方，希望大家指证出来，我会不断的改正自己的错误。💯💯如果感觉写的还可以，可以点赞三连一波哦~🍸🍸后续会持续为大家更新。
🔥🔥你们的支持是我最大的动力，希望在往后的日子里，我们大家一起进步！！！🔥🔥
HashMap中为什么引入红黑树，而不是AVL树呢1.概述开始学习这个知识点之前我们需要知道，在JDK1.8以及之前，针对HashMap有什么不同。JDK1.7的时候，HashMap的底层实现是数组+链表JDK1.8的时候，HashMap的底层实现是数组+链表+红黑树我们要思考一个问题，为什么要从链表转为红黑树呢。首先先让我们了解下链表有什么不好？？？2.链表上述的截图其实就是链表的结构，我们来看下链表的增删改查的时间复杂度增：因为链表不是线性结构，所以每次添加的时候，只需要移动一个节点，所以可以理解为复杂度是N(1)删：算法时间复杂度跟增保持一致查：既然是非线性结构，所以查询某一个节点的时候
在VMware16.2.4安装Ubuntu一、安装VMware1.打开VMwareWorkstationPro官网，点击即可进入。2.进入后向下滑动找到Workstation16ProforWindows，点击立即下载。3.下载完成，文件大小615MB，如下图：4.鼠标右击，以管理员身份运行。5.点击下一步6.勾选条款，点击下一步7.先勾选，再点击下一步8.去掉勾选，点击下一步9.点击下一步10.点击安装11.点击许可证12.在百度上搜索VM16许可证，复制填入，然后点击输入即可，亲测有效。13.点击完成14.重启系统，点击是15.双击VMwareWorkstationPro图标，进入虚拟机主
1．问题描述使用Python的turtle（海龟绘图）模块提供的函数绘制直线。2．问题分析一幅复杂的图形通常都可以由点、直线、三角形、矩形、平行四边形、圆、椭圆和圆弧等基本图形组成。其中的三角形、矩形、平行四边形又可以由直线组成，而直线又是由两个点确定的。我们使用Python的turtle模块所提供的函数来绘制直线。在使用之前我们先介绍一下turtle模块的相关知识点。turtle模块提供面向对象和面向过程两种形式的海龟绘图基本组件。面向对象的接口类如下：1）TurtleScreen类：定义图形窗口作为绘图海龟的运动场。它的构造器需要一个tkinter.Canvas或ScrolledCanva
目录H2数据库入门以及实际开发时的使用1.H2数据库的初识1.1H2数据库介绍1.2为什么要使用嵌入式数据库？1.3嵌入式数据库对比1.3.1性能对比1.4技术选型思考2.H2数据库实战2.1H2数据库下载搭建以及部署2.1.1H2数据库的下载2.1.2数据库启动2.1.2.1windows系统可以在bin目录下执行h2.bat2.1.2.2同理可以通过cmd直接使用命令进行启动：2.1.2.3启动后控制台页面：2.1.3spring整合H2数据库2.1.3.1引入依赖文件2.1.4数据库通过file模式实际保存数据的位置2.2H2数据库操作2.2.1Mysql兼容模式2.2.2Mysql模式
我为你们准备了一个简单的。我想要一个特色内容部分，其中排除了当前文章所以这可以通过delete_if使用MiddlemanBlog:但是我使用的是中间人代理，所以我无法访问current_article方法...我有一个YAML结构，其中包含以下模拟数据(以及其他数据)，文件夹设置如下:data>site>caseStudy>RANDOM-ID423536.yaml(由CMS生成)在每个yaml文件中，您会发现如下内容::id:2k1YccJrQsKE2siSO6o6ac:title:Heyplace我的config.rb看起来像这样data.site.caseStudy.eachdo
目录一、安装包链接二、安装详细步骤1.安装Wireshark和WinPcap2.安装OracleVMVirtualBox3.安装ensp三、安装后注册四、启动路由器出现40错误怎么解决一、安装包链接二、安装详细步骤链接:https://pan.baidu.com/s/1QbUUYMOMIV2oeIKHWP1SpA?pwd=xftx提取码：xftx1.安装Wireshark和WinPcap找到Wireshark安装包所在文件夹，双击它，按照以下步骤安装。2.安装OracleVMVirtualBox找到OracleVMVirtualBox安装包所在文件夹，双击它，按照以下步骤安装。注：可自定义安装
Nginx安装1.官网下载Nginx2.使用XShell和Xftp将压缩包上传到Linux虚拟机中3.解压文件nginx-1.20.2.tar.gz4.配置nginx5.启动nginx6.拓展（修改端口和常用命令）（一）修改nginx端口（二）常用命令1.官网下载Nginxhttp://nginx.org/en/download.html这里我下载的是1.20.2版本，大家按需下载对应稳定版即可2.使用XShell和Xftp将压缩包上传到Linux虚拟机中没有XShell可以参考《Linux操作系统CentOS7连接XShell》3.解压文件nginx-1.20.2.tar.gz1）检查是否存
因学习需要用到keras，通过查找较多资料最终完成Anaconda、TensorFlow和Keras的简单安装。因为网上的相关资料较多但大部分不够全面，查找起来不太方便，因此自己记录一下成功下载安装的详细过程,顺便推荐一下借鉴的写的很好的相关教程文章。keras需要在TensorFlow之上才能运行，所以要先安装TensorFlow，而TensorFlow只能在3.7以前的python版本中运行，所以需要先创建一个基于python3.6的虚拟环境，因此便需要先下载Anaconda。一、Anaconda3下载和安装Anaconda下载安装教程原文链接：https://blog.csdn.net/
我正在为我的网站使用MiddlemanBloggem，但默认情况下，博客文章似乎需要位于/source中，这在查看vim中的树时并不是特别好并尝试在其中找到其他文件之一(例如模板)。通过查看文档，我看不出是否有任何方法可以移动博客文章，以便将它们存储在其他地方，例如blog_articles文件夹或类似文件夹。这可能吗？ 最佳答案 将以下内容放入您的config.rb文件中。activate:blogdo|blog|blog.permalink=":year-:month-:day-:title.html"blog.sources=
【动态规划】一、背包问题1.背包问题总结1）动规四部曲：2）递推公式总结：3）遍历顺序总结：2.01背包1）二维dp数组代码实现2）一维dp数组代码实现3.完全背包代码实现4.多重背包代码实现一、背包问题1.背包问题总结暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！背包问题是动态规划（DynamicPlanning）里的非常重要的一部分,关于几种常见的背包，其关系如下：在解决背包问题的时候，我们通常都是按照如下五部来逐步分析，把这五部都搞透了，算是对动规来理解深入了。1）动规四部曲：（1）确定dp数组及其下标的含义（2）确定递推公式（3）dp数组的初始化（4）确定遍历顺