红黑树详解&&模拟实现
一，红黑树的概念
红黑树也是一颗二叉搜索树，相比于AVL树的插入，红黑树没有那么多的旋转，对平衡的检查没有那么的严格，所以是接近平衡的。
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的
二，红黑树的特性
红黑树有下面几个特性，这些特性保证了红黑树中最长路径中得节点个数不会超过最短路径中节点个数的2倍：
- 每个结点不是红色就是黑色
- 根节点是黑色的
如果一个节点是红色的，则它的两个孩子结点是黑色的对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
其中的第3点保证了每个路径中不会出现连续的红色节点的情况，加上第4点就保证了红黑树中最长路径中的节点个数不会超过最短路径的2倍
三，红黑树的结构
和之前实现AVL树一样，我们先来写一下红黑树的基本框架
我们先用枚举来定义每个节点的颜色
//枚举来定义节点的颜色
enum Color {
RED,
BLACK
};
然后我们写出节点，每个节点包含数据和颜色和指向儿子和双亲的指针
//节点
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T _data;
Color _col;
RBTreeNode(const T &data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)//初始为红色
{}
};
这里注意：每个节点初始为红色，这也是为了在插入节点时，红色节点可以较小程度上减少对整颗树的影响
接下来是红黑树的基本框架，
template<class K,class T>//T这个模板参数来决定红黑树存储的数据类型
class RBTree {
typedef RBTreeNode<T> Node;
public:
//..
private:
Node* _root = nullptr;
};
四，红黑树的迭代器
看完了基本框架，我们现在来看一下红黑树的迭代器
迭代器部分和之前一样我们先重载operator->和operator*
template<class T>
struct _RBTreeIterator{
typedef RBTreeNode<T> Node;
typedef _RBTreeIterator<T> Self;
Node* _node;
_RBTreeIterator(Node* node)
:_node(node)
{}
T* operator->() {
return &_node->_data;
}
T& operator*() {
return _node->_data;
}
//...
}
下面我们只要来看operator++
operator++也按照是中序遍历来走的。
这里要分两种情况，右子树存在或者不存在，因为++后的下一个节点比当前节点大，
- 右子树存在时，下一个节点就是右子树中最左边的节点，
- 如果右子树不存在时，说明当前子树已经遍历结束，那么就要继续向上查找
//前置++
Self& operator++() {
if (_node->_right) {//情况1
Node* cur = _node->_right;
while (cur->_left) {
cur = cur->_left;
}
_node = cur;
}
else {//情况2
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right) {
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
注意：右子树不存在时，判断的时候也要判断parent在不在，因为cur指向的是最后一个节点时，一直向上查找到根后，防止对空指针取parent
五，模拟实现红黑树插入操作
红黑树的插入是通过调整插入后节点的颜色来保证平衡的。
如果我们插入的节点的parent的颜色为黑，则不需要调整，因为没有破坏平衡属性。
如果parent的颜色为黑，则要调整，这里为了方便我们标记了parent节点为p，cur节点为c，grandparent节点为g，parent的兄弟节点为u。
我们插入的节点为红色，所以插入后可以确定的是p为红色，g为黑色
这里插入后也要分三种情况：
- 新增节点的 u 为红色（新增节点在p的左还是右不影响）
- 新增节点在p的左孩子时，u 不存在/存在且为黑色
- 新增节点在p的右孩子时，u 不存在/存在且为黑色
下面我们来看代码实现，首先要找到插入的位置
注：这里的KeyofT是一个仿函数类型，用来获取红黑树中存储的Key值
返回值是一个pair键值对，为了支持后面map部分的operator[]，我们下一节进行讲解
pair<iterator, bool> insert(const T& data) {//传入引用减少拷贝
if (_root == nullptr) {
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root),true);
}
Node* parent = nullptr;//红黑树和AVL树都需要这种三叉的形式来辅助插入
Node* cur = _root;
KeyofT kot;
//找到插入的位置
while (cur) {
if (kot(data) > kot(cur->_data)) {
parent = cur;
cur = cur->_right;
}
else if (kot(data) < kot(cur->_data)) {
parent = cur;
cur = cur->_left;
}
else {
return false;
}
}
//将新增节点插入
}
找到位置后我们进行插入，进行调整颜色。如果是插入位置的parent是红色才进行调整，否则不进行调整。
这里的三种情况又有相反的场景，也就是p在g的右孩子时：
pair<iterator, bool> insert(const T& data) {//传入引用减少拷贝
if (_root == nullptr) {
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root),true);
}
Node* parent = nullptr;//红黑树和AVL树都需要这种三叉的形式来辅助插入
Node* cur = _root;
KeyofT kot;
//找到插入的位置
while (cur) {
if (kot(data) > kot(cur->_data)) {
parent = cur;
cur = cur->_right;
}
else if (kot(data) < kot(cur->_data)) {
parent = cur;
cur = cur->_left;
}
else {
return false;
}
}
//将新增节点插入
cur = new Node(data);
Node* newnode = cur;
cur->_col = RED;//插入的节点都设为红色，这样可以将可能少的破坏平衡
if (kot(data) > kot(parent->_data)) {
parent->_right = cur;
cur->_parent = parent;
}
else {
parent->_left = cur;
cur->_parent = parent;
}
while (parent && parent->_col == RED) {//
Node* grandparent = parent->_parent;
if (parent == grandparent->_left) {//p在g的左
Node* uncle = grandparent->_right;
if (uncle && uncle->_col == RED) {//情况1-->u为红
parent->_col = uncle->_col = BLACK;//只需要变色即可
grandparent->_col = RED;//
cur = grandparent;
parent = cur->_parent;
}
else {
if (cur == parent->_left) {//情况2
RotateR(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else {//情况3
RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;// }
}
else {//p再g的右
Node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED) {//情况1的相反场景
parent->_col = uncle->_col = BLACK;//只需要变色即可
grandparent->_col = RED;//
//往上更新
cur = grandparent;
parent = cur->_parent;
}
else {
if (cur == parent->_right) {//情况2
RotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else {
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;//
}
}
}
_root->_col = BLACK;
return make_pair(iterator(), bool);
}
注意：其中判断完情况3后如果不加break则会使打乱关系后的p,g,c,u再次进入while循环进行判断，所以要加break跳出循环
六，红黑树的检查
实现了插入后，接下来就要检查红黑树的结构是否正确。
要检查是否是红黑树，就要检查其是否符合红黑树的特性。
我们主要来检查第3和第4个特性，对于每条路径的黑色节点个数，我们可以用最左路径中黑色节点个数作为参考对对比：
bool IsBlance() {
if (_root == nullptr) {//空树也是红黑树
return true;
}
if (_root->_col == RED) {
return false;
}
int refVal = 0;//设定一个参考值来判断每条路径上的黑色节点数量是否相等
Node* cur = _root;
//这里以最左路径的黑色节点个数来做参考
while (cur) {
if (cur->_col == BLACK) {
++refVal;
}
cur = cur->_left;//如果要以最有路径做参考，则改为cur->_right
}
int blacknum = 0;//这里的blacknum是记录根节点到递归时的当前节点的黑色节点个数
return Check(_root, blacknum, refVal);//这里不传引用
}
bool Check(Node* root, int BlackNum, int REFval) {//传入blacknum是值拷贝，返回上一层的时候才可以是上一层的黑色个数，
if (root == nullptr) {//递归到叶子时的判断
if (BlackNum != REFval) {
cout << "有黑色节点不相等的路径" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED) {
cout << "有连续的红色节点" << endl;
return false;
}
if (root->_col == BLACK) {
++BlackNum;
}
//也是一种深度遍历
return Check(root->_left, BlackNum, REFval) && Check(root->_right, BlackNum, REFval);
}
如果大家想看全部的代码可以查看链接: 红黑树模拟实现
标签：黑树,Node,进阶,parent,C++,col,红黑树,节点,cur From： https://blog.csdn.net/weixin_64906519/article/details/136868232