[C++]——红黑树（附源码）
目录
一、前言
在上一篇博客中，为小伙伴们进行了AVL树的讲解，但是由于在实际场景中大部分插入的数据都是无序的，所以红黑树的应用相较于AVL树会更会广泛，插入相同的数据，红黑树的旋转次数会比AVL树少很多，且其层数也不会像二叉搜索树那样高。因此在本篇博客中为大家带来红黑树的讲解，如有不足之处，欢迎各位大佬们给予指正！
二、正文
2.1 红黑树的概念
红黑树，是一棵二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
以下图为例我们发现最短的路径上有三个节点，最长的路径有4个节点，并没有超出最短路径的两倍。
2.2 红黑树的性质
在上面中我们了解到一颗红黑树中，最长路径的节点不超过最短路径的两倍，那么我们到底该如何让一颗二叉搜索树变成这样的一颗红黑树呢？这就需要满足红黑树的以下几个性质：
1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
2.3红黑树节点的定义
那么在了解完红黑树的概念及其性质后，接下来我们就来讲讲该如何实现这样的一颗红黑树。
首先我们要明确的是红黑树的底层结构其实是与AVL树是一样的，都是一颗搜索二叉树，且为了使他们的结构都能达到各自的平衡，因此都需要采取三叉链的结构，即树节点内必须包含父亲，左孩子和右孩子三个节点指针，以方便树的旋转平衡。除此之外，既然是红黑树，其节点就是有“颜色”的，那么理所应当的，我们在每个节点内还需要定义一个颜色，我们可以通过枚举的方式来实现，这也是其与AVL树不同的地方所在。
当然这里还有一个额外需要注意的地方，就是对于一个节点的初始化，其三叉链的节点指针好说，定义为空指针即可，但是颜色我们该定义为黑色还是红色呢？在这里我们采取的是红色，这里其实是考虑在尽量影响较少红黑树的结构下我们选择的，因为如果当我们将新插入节点的颜色定义为黑色时，那么该节点所处路径下的黑色节点数就都会加一，就会与其他路径的黑色节点数不同，在调整次数为各个路径黑色节点数相同就会比较麻烦；反之若是插入新节点的颜色为红色，那么就不会影响该路径的黑色节点数，倘若插入处的父亲节点为黑色，那么插入后仍为一颗红黑树。如果父亲节点为红色，虽然违背了红黑树“红色节点的左右孩子节点都是黑色”这一点，但是通过变色或者旋转的方式我们还是能够比较轻松将其重新变成一颗红黑树相较于去调整其他路径的黑色节点数来说，因此我们在创建一个新节点的时候，会将其颜色初始化为红色。
具体代码如下：
//枚举：红色和黑色
enum Color
{
RED,
BLACK
};
//红黑树节点的定义
template <class K,class V>
struct RBTreeNode
{
//采取三叉链的方式方便树的旋转平衡
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
//颜色
Color _col;
pair<K, V> _kv;
RBTreeNode(const pair<K ,V> kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED) //默认初始化为红色
, _kv(kv)
{}
};2.4 红黑树的插入
在成功创建完一个红色的新节点后，接下来的操作就是将这个新节点插入树中。
首先，第一步就是找到其应所处的位置。由于红黑树的底层结构是一颗二叉搜索树，因此我们只需要从根节点开始不断进行数值的比较，若是比插入节点的数值大就来到左子树；比插入的节点数据小，就来到右子树，直至找到空指针为止，那么该处就是新节点所应该插入的位置。要注意的是如果遇到插入的数据在比较时遇到相同时就应该退出来，无需插入。（无重复数据的红黑树）
第二步就是进行新节点与父亲节点的链接，若是父亲节点的数据大于新节点，就链接到其左子树，小于新节点，则链接到右子树。
第三步就是进行红黑树规则的判断，判断在插入该节点后是否仍满足一颗红黑树，若是不满足则需要进行相对应的调整，使其重新变为一颗红黑树，这也是其在插入过程中最为重要的一步。那么我们该如何判断在插入新节点后，此树是否仍为一颗红黑树呢，其实在上面新节点的颜色选择上已经点出了，由于我们插入新节点的颜色是红色，那么其违反的规则只有一条，就是“红色节点的左右子树必须都为黑色节点”，因此只要新节点的父亲节点为红色，就说明我们插入新节点后，此树就不再是一颗红黑树，需要我们对此树进行一个调整使其重新变成一颗红黑树。
代码框架如下：
bool Insert(const pair<K, V>& kv)
{
//空树
if (_root == nullptr)
{
_root = new Node(kv);
}
//树不为空
else
{
//寻找父亲结点
Node* parent = nullptr;
Node* cur = _root;
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 return false;
}
//插入新节点
cur = new Node(kv);
if (cur->_kv.first > parent->_kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
//检测插入新节点后，红黑树的性质是否发生变化
while (parent && parent->_col == RED)
{
……
}
}
//无论进行怎样的处理 根结点都为黑
_root->_col = BLACK;
return true;
}当我们找好位置插入新节点后，若是父亲节点的颜色为黑色，自然满足红黑树的性质，不需要再继续调整；但是如果父亲节点的颜色为红色，那么就不满足红黑树的性质，我们就需要根据不同的情况进行调整，下面我们就对这几种情况进行逐一的讲解。
注：cur为当前节点，p为父亲节点，g为祖父节点，u为叔叔节点
2.4.1 情况一
cur为红，p为红，g为黑，u存在且为红
面对这种情况，我们只需要将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。在向上调调整的过程中我们可能会遇到这两种情况：
1.cur为红色，p为黑色——满足红黑树的性质，调整完毕
2.一直调整至根节点，即g为nullptr——无需继续向上调整，将根节点，即p节点调整为黑色，调整完毕
示意图及代码如下：
//情况一：uncle存在且为红->变色
//父亲是祖父的左节点
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//变色后继续向上传递
cur = grandfather;
parent = cur->_parent;
}
}
//父亲是祖父的右节点
else if (parent == grandfather->_right)
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//变色后继续向上传递
cur = grandfather;
parent = cur->_parent;
}
} 2.4.2 情况二
cur为红，p为红，g为黑，u不存在
面对这种情况情况，操作起来就不像情况一那么简单，情况一无需考虑cur，p，g三节点之间的相对位置，而情况二则需要根据三者之间的相对位置来进行不同的旋转，大致有四种旋转情况：左单旋，右单旋，左右双旋和右左双旋
具体旋转和变色如下：
2.4.3 情况三
cur为红，p为红，g为黑，u存在且为黑
面对这种情况，与情况二的操作类似，都是旋转加变色
具体旋转和变色见下：
虽然情况二和情况三中一种是存在u节点且为黑，一种不存在u节点，但我们发现在旋转和变色的过程u节点几乎没有参与其中，因此我们在实现的时候其实可以将这两种情况归为一种。
具体代码如下：
//旋转加变色
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
//父亲是祖父的左节点
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//情况二\三:uncle不存在或者uncle存在但颜色为黑->旋转加变色
else if (uncle == nullptr || uncle->_col == BLACK)
{
//孩子在父亲的左边->右单旋加变色
// g
// p
//c
if (cur == parent->_left)
{
RotateR(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
break;
}
//孩子在父亲的右边->左右单旋加变色
// g
// p
// c
else if (cur == parent->_right)
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
break;
}
}
}
//父亲是祖父的右节点
else if (parent == grandfather->_right)
{
Node* uncle = grandfather->_left;
//情况二\三:uncle不存在或者uncle存在但颜色为黑->旋转加变色
else if (uncle == nullptr || uncle->_col == BLACK)
{
//孩子在父亲的右边->左单旋加变色
// g
// p
// c
if (cur == parent->_right)
{
RotateL(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
break;
}
//孩子在父亲的左边->右左单旋加变色
// g
// p
// c
else if (cur == parent->_left)
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
break;
}
}
}
}在红黑树的节点插入之后，为了方便建立起对插入过程的直观理解，下面为大家呈现两种节点插入方式所带来的效果。
方式一：升序（降序插入） 插入构建红黑树
方式二：随机插入构建红黑树
2.5 红黑树的验证
当我们按照代码所写构建完一颗红黑树之后，下一步就是对我们所搭建的红黑树进行验证才能保证我们的代码无误。对于红黑树来说验证主要分为两步：
1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)，对于这一步来说与前面AVL的验证是相同的，笔者就不在这里做过多赘述，有需求的小伙伴可以移步到博主的上一篇文章【C++】——AVL树-CSDN博客
2. 检测其是否满足红黑树的性质：
①根节点是否为黑色
②红色节点的左右子树是否都为黑色节点
③每条路径的黑色节点数相同
具体代码如下：
// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
bool IsValidRBTRee()
{
//空树
if (_root == nullptr) return true;
//根结点为黑色
if (_root->_col == RED) return false;
//每条路径的黑色结点数相同
int benmarch = 0;
Node* root = _root;//基准值
while (root)
{
if (root->_col == BLACK) ++benmarch;
root = root->_left;
}
_IsValidRBTRee(_root, 0, benmarch);
}
bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack)
{
if (pRoot == nullptr && blackCount != pathBlack)
{
return false;
}
else if (pRoot == nullptr && blackCount == pathBlack)
{
return true;
}
if(pRoot->_col==BLACK)
{
blackCount++;
}
if (pRoot->_col == RED && pRoot->_parent && pRoot->_parent->_col == RED)
{
cout << pRoot->_kv.first << "出现连续的红节点" << endl;
return false;
}
return _IsValidRBTRee(pRoot->_left,blackCount,pathBlack) &&
_IsValidRBTRee(pRoot->_right,blackCount,pathBlack);
}三、全部代码
#pragma once
//枚举：红色和黑色
enum Color
{
RED,
BLACK
};
//红黑树节点的定义
template <class K,class V>
struct RBTreeNode
{
//采取三叉链的方式方便树的旋转平衡
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Color _col;
pair<K, V> _kv;
RBTreeNode(const pair<K ,V> kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED)
, _kv(kv)
{}
};
template<class K,class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
RBTree() {}
bool Insert(const pair<K, V>& kv)
{
//空树
if (_root == nullptr)
{
_root = new Node(kv);
}
//树不为空
else
{
//寻找父亲结点
Node* parent = nullptr;
Node* cur = _root;
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 return false;
}
//插入新节点
cur = new Node(kv);
if (cur->_kv.first > parent->_kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
//旋转
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
//父亲是祖父的左节点
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//情况一：uncle存在且为红->变色
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//变色后继续向上传递
cur = grandfather;
parent = cur->_parent;
}
//情况二:uncle不存在或者uncle存在但颜色为黑->旋转加变色
else if (uncle == nullptr || uncle->_col == BLACK)
{
//孩子在父亲的左边->右单旋加变色
// g
// p
//c
if (cur == parent->_left)
{
RotateR(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
break;
}
//孩子在父亲的右边->左右单旋加变色
// g
// p
// c
else if (cur == parent->_right)
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
break;
}
}
}
//父亲是祖父的右节点
else if (parent == grandfather->_right)
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//变色后继续向上传递
cur = grandfather;
parent = cur->_parent;
}
//情况二\三:uncle不存在或者uncle存在但颜色为黑->旋转加变色
else if (uncle == nullptr || uncle->_col == BLACK)
{
//孩子在父亲的右边->左单旋加变色
// g
// p
// c
if (cur == parent->_right)
{
RotateL(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
break;
}
//孩子在父亲的左边->右左单旋加变色
// g
// p
// c
else if (cur == parent->_left)
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
break;
}
}
}
}
}
//无论进行怎样的处理 根结点都为黑
_root->_col = BLACK;
return true;
}
// 检测红黑树中是否存在值为k的节点，存在返回该节点的地址，否则返回nullptr
Node* Find(const K& k)
{
_Find(_root);
}
// 获取红黑树最左侧节点
Node* LeftMost()
{
_LeftMost(_root);
}
// 获取红黑树最右侧节点
Node* RightMost()
{
_RightMost(_root);
}
// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
bool IsValidRBTRee()
{
//空树
if (_root == nullptr) return true;
//根结点为黑色
if (_root->_col == RED) return false;
//每条路径的黑色结点数相同
int benmarch = 0;
Node* root = _root;//基准值
while (root)
{
if (root->_col == BLACK) ++benmarch;
root = root->_left;
}
_IsValidRBTRee(_root, 0, benmarch);
}
private:
bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack)
{
if (pRoot == nullptr && blackCount != pathBlack)
{
return false;
}
else if (pRoot == nullptr && blackCount == pathBlack)
{
return true;
}
if(pRoot->_col==BLACK)
{
blackCount++;
}
if (pRoot->_col == RED && pRoot->_parent && pRoot->_parent->_col == RED)
{
cout << pRoot->_kv.first << "出现连续的红节点" << endl;
return false;
}
return _IsValidRBTRee(pRoot->_left,blackCount,pathBlack) && _IsValidRBTRee(pRoot->_right,blackCount,pathBlack);
}
// 左单旋
void RotateL(Node * pParent)
{
Node* grandparent = pParent->_parent;
Node* cur = pParent->_right;
Node* cur_left = cur->_left;
//旋转相关结点
if (cur_left) cur_left->_parent = pParent;//不为空
pParent->_right = cur_left;
cur->_left = pParent;
pParent->_parent = cur;
if (this->_root == pParent)
{
this->_root = cur;
cur->_parent = nullptr;
}
else if (grandparent->_left == pParent)
{
grandparent->_left = cur;
cur->_parent = grandparent;
}
else if (grandparent->_right == pParent)
{
grandparent->_right = cur;
cur->_parent = grandparent;
}
}
// 右单旋
void RotateR(Node * pParent)
{
Node* grandparent = pParent->_parent;
Node* cur = pParent->_left;
Node* cur_right = cur->_right;
//旋转相关节点
pParent->_left = cur_right;
if (cur_right) cur_right->_parent = pParent; //不为空
cur->_right = pParent;
pParent->_parent = cur;
if (grandparent == nullptr)
{
this->_root = cur;
cur->_parent = nullptr;
}
else if (grandparent->_left == pParent)
{
grandparent->_left = cur;
cur->_parent = grandparent;
}
else if (grandparent->_right == pParent)
{
grandparent->_right = cur;
cur->_parent = grandparent;
}
}
Node* _Find(Node* root,const K& k)
{
if (root == nullptr) return nullptr;
if (root->_kv.first > k) _Find(root->_left, k);
else if (root->_kv.first < k) _Find(root->_right, k);
else return root;
}
Node* _LeftMost(Node* root)
{
if (root == _root) return root;
else if (root->_left == nullptr) return root;
else return _LeftMost(root->_left);
}
Node* _RightMost(Node* root)
{
if (root == _root) return root;
else if (root->_right == nullptr) return root;
else return _RightMost(root->_right);
}
Node* _root=nullptr;
};
void text()
{
const int N = 10000;
vector<pair<int,int>> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; ++i)
{
v.push_back(pair<int,int>(i,i));
}
RBTree<int, int> RBTree;
for (const auto& e : v)
{
RBTree.Insert(e);
cout << e.first << ":" << RBTree.IsValidRBTRee()<<endl;
}
}四、结语
到此为止，关于红黑树树的讲解就告一段落了，至于其他的内容，小伙伴们敬请期待呀！
关注我 _麦麦_分享更多干货：_麦麦_-CSDN博客
大家的「关注❤️ + 点赞👍 + 收藏⭐」就是我创作的最大动力！谢谢大家的支持，我们下期见！
原文地址：https://blog.csdn.net/m0_73953114/article/details/143300535
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！