您现在的位置是：首页 >学无止境 >【C++】红黑树的插入分析及验证网站首页学无止境
【C++】红黑树的插入分析及验证
1. 红黑树概念
红黑树 是一种二叉搜索树，但在每个节点上增加一个存储位表示节点的颜色，可以是red或black，
通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其他路径长处两倍，所以是接近平衡的
2. 红黑树性质
1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
(不能出现连续的红色节点)
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
(每条路径上都有相同数量的黑色节点)
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
(走到NULL才算一条路径)
3. 结构定义
使用枚举来记录红色与黑色，用_col表示当前节点颜色
但是在构造函数中为什么默认是红色呢？为什么不能是黑色呢？
关于默认节点为红/黑色的讨论
若在红框中插入黑色节点则违反规则4 即每条路径上都有相同数量的黑色节点，还需要再次将不同路径上都添加黑色节点，影响太大
若在红框中插入红色节点，则有可能违反规则3(存在两个连续的红色节点)
当前情况违反规则3
若插入红色节点后，父节点为黑色，则不违反规则3
所以默认节点为红色更利于去解决问题
4. insert
grandfather节点省略为g ，uncle节点省略为u ，parent节点省略为p，cur节点省略为c
情况1—— uncle节点存在且为红色(g p c左斜形成一条直线)
当插入红色节点后，与父节点形成连续的红色节点
把parent节点变成黑色，uncle节点置为黑色，并将grandfather节点置为红色
若grandfather节点的父节点为黑色，则不需要继续处理
若grandfather节点的父节点为红色，把当前的grandfather节点作为新增节点cur，继续向上调整
情况2——uncle节点不存在/存在且为黑色(g p c 左斜形成直线 右单旋)
uncle节点不存在
当uncle节点不存在时，则cur作为新增节点，
因为红黑树也是一种二叉搜索树，因为左边高，所以进行右单旋
uncle节点存在并且为黑色
首先进行变色，将新增节点的上面两个节点置为黑色，再将cur节点置为红色
同时需要进行右旋转
将c作为g的左子树，将g作为p的右子树
将g置为红色
将p置为黑色
RotateR/RotateL的实现，与AVL树的类似，只需把原来的代码的平衡因子去掉即可
不懂查看：AVL树的实现
情况3——uncle节点不存在/存在且为黑色(g p c 形成左折线 双旋)
因为 grandfather(g) parent( p) cur( c) 节点为一条折线，所以为双旋
uncle节点不存在
作为这样的折线存在，所以要进行双旋，先对p进行右单旋，在对旋转后的根进行左单旋
uncle节点存在并且为黑色
首先进行变色，将新增节点上面的两个节点由红色置为黑色
再将cur节点由黑色置为红色
在进行左单旋，将cur的左子树节点 作为p的右子树，将p作为cur的左子树
进行右单旋，将cur的右子树节点作为g的左子树，将g作为cur的右子树
最终cur变为黑色，g变为红色
情况1—— uncle节点存在且为红色(g p c右斜形成一条直线)
当插入红色节点后，与父节点形成连续的红色节点
把parent节点变成黑色，uncle节点置为黑色，并将grandfather节点置为红色
若grandfather节点的父节点为红色，把当前的grandfather节点作为新增节点cur，继续处理
与上述左斜形成直线的写法相同
情况2——uncle节点不存在/存在且为黑色(g p c 右斜形成直线 左单旋)
这里以节点不存在举例
此时的uncle节点处于NULL
将parent节点置为黑色，将grandfather节点置为红色
并进行旋转，将1作为6的左子树，将6作为8的左子树
相当于进行左单旋
情况3——uncle节点不存在/存在且为黑色(g p c 形成右折线 双旋)
首先进行变色，将新增节点上面的两个节点由红色置为黑色
再将cur节点由黑色置为红色
在进行右单旋，将cur的右子树节点 作为p的左子树，将p作为cur的右子树
进行左单旋，将cur的左子树节点作为g的右子树，将g作为cur的左子树
最终cur变为黑色，g变为红色
5.判断是否为红黑树
规则中要求根节点为黑色，所以当根为红色时就返回false
连续的红色节点
若当前节点为红时，检查儿子是否为红，但是儿子节点有可能为空
所以采用当前节点为红时，若父节点也为红，则返回false
使用blacknum用于记录每条路径的黑色节点个数
blacknum作为一个形参传值调用，下一层的++不会影响上一层
如果当前节点的颜色为黑色，则blacknum++
6. 整体代码
#pragma once
#include<iostream>
#include<cassert>
using namespace std;
enum colour
{
RED,//红色 默认为0
BLACK,//黑色 默认为1
};
template<class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<K, V> _kv;//当前节点值
colour _col;//表示颜色
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr),
_right(nullptr),
_parent(nullptr),
_kv(kv),
_col(RED)
{
}
};
template<class K,class V>
class RBTree
{
typedef RBTreeNode<K,V> Node;
public:
bool insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;//若刚插入一个节点，则该节点颜色是黑色
return true;
}
Node* parent = nullptr;//用于记录cur的前一个节点
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);
//再次判断parent当前节点值与插入值大小
if (parent->_kv.first > kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
//cur的上一个节点即为 刚才的记录cur前一个节点的parent
cur->_parent = parent;
//当父节点不为NULL并且父节点为红色
while (parent != nullptr && parent->_col == RED)
{
Node* grandfather = parent->_parent;//爷爷节点
//若父节点为爷爷节点的左子树，则unlce为爷爷节点的右子树
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
// g
// p u
// c
//情况1:u存在并且为红，直接变色即可，并继续往上处理
if (uncle && uncle->_col == RED)
//若uncle节点为红色，将parent与uncle都置为黑色，爷爷节点置为红色
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//继续往上调整
cur=grandfather;
parent = cur->_parent;
}
//情况2+3:u不存在或者u存在且为黑，旋转+变色
else
{
//情况2
//g p c 作为一条直线 所以为单旋
// g
// p u
//c
if (cur == parent->_left)
{
//右旋转
RotateR(grandfather);
//最终p作为最终的根 为黑 g为红
parent->_col = BLACK;
grandfather->_col = RED;
}
//情况3
//g p c 作为一条折线 所以为双旋
// g
// p u
// c
else
{
//左单旋
RotateL(parent);
//右单旋
RotateR(grandfather);
//最终cur作为最终的根 为黑 g为红
cur->_col = BLACK;
grandfather->_col = RED;
//父节点继续保持红色
parent->_col = RED;
}
break;
}
}
else//grandfather->_right == parent
若父节点为爷爷节点的右子树，则unlce为爷爷节点的左子树
{
// g
// u p
// c
Node* uncle = grandfather->_left;
//情况1:u存在并且为红，直接变色即可，并继续往上处理
if (uncle && uncle->_col == RED)
//若uncle节点为红色，将parent与uncle都置为黑色，爷爷节点置为红色
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//继续往上调整
cur = grandfather;
parent = cur->_parent;
}
//情况2+3:u不存在或者u存在且为黑，旋转+变色
else
{
//情况2
//g p c 作为一条直线 所以为单旋
// g
// u p
// c
if (cur == parent->_right)
{
//左旋转
RotateL(grandfather);
//最终p作为最终的根 为黑 g为红
parent->_col = BLACK;
grandfather->_col = RED;
}
//情况3
//g p c 作为一条折线 所以为双旋
// g
// u p
// c
else
{
//右单旋
RotateR(parent);
//左单旋
RotateL(grandfather);
//最终cur作为最终的根 为黑 g为红
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
//为了避免grandfather节点正好为根时，会被更新成红色的情况
_root->_col = BLACK;
return true;
}
void inorder()//中序遍历
{
_inorder(_root);
cout << endl;
}
//判断一颗二叉树是否为红黑树
bool isbalance()
{
//检查根是否为黑
if (_root && _root->_col == RED)
{
cout << "根节点颜色是红色" << endl;
return false;
}
//连续的红色节点
return _check(_root,0);
}
private:
bool _check(Node* root,int blacknum)
{
if (root == nullptr)
{
//为空时，blacknum代表一条路径的黑色节点个数
cout << blacknum << " ";
return true;
}
//blacknum代表黑色节点的个数
if (root->_col == BLACK)
{
blacknum++;
}
//若当前节点为红 父节点也为红
if (root->_col == RED
&&root->_parent
&&root->_parent->_col==RED)
{
cout << "存在连续的红色节点" << endl;
return false;
}
//遍历整棵树
return _check(root->_left,blacknum) && _check(root->_right,blacknum);
}
void _inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_inorder(root->_left);
cout << root->_kv.first << " ";
_inorder(root->_right);
}
void RotateL(Node* parent)//左单旋
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL != nullptr)
{
subRL->_parent = parent;
}
Node* ppnode = parent->_parent;//记录parent的前一个节点
subR->_left = parent;
parent->_parent = subR;
if (ppnode == nullptr)//说明parent是根即代表整棵树
{
_root = subR;//subR作为新的根
_root->_parent = nullptr;//subR的父节点指向原来的parent,所以要置nullptr
}
else//说明旋转的是一部分，所以要跟ppnode相连接
{
if (ppnode->_left == parent)//若连接在左子树上
{
ppnode->_left = subR;
}
else//若连接在右子树上
{
ppnode->_right = subR;
}
subR->_parent = ppnode;//将subR父节点置为ppnode
}
}
void RotateR(Node* parent)//右单旋
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR != nullptr)
{
subLR->_parent = parent;
}
Node* ppnode = parent->_parent;//记录parent的父节点
subL->_right = parent;
parent->_parent = subL;
if (ppnode == nullptr)//若旋转整棵树
{
_root = subL;
_root->_parent = nullptr;
}
else//若旋转整棵树的部分子树
{
if (ppnode->_left == parent)
{
ppnode->_left = subL;
}
else
{
ppnode->_right = subL;
}
subL->_parent = ppnode;//使subL的父节点为ppnode
}
}
private:
Node* _root = nullptr;
};
void test_RBTree1()
{
int a[]={16, 3, 7, 11, 9, 26, 18, 14, 15};
//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16,14 };
RBTree<int, int>v1;
for (auto e : a)
{
v1.insert(make_pair(e, e));
}
v1.inorder();
cout << v1.isbalance() << endl;
}
站长推荐
- SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权 - stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - 【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》 - 【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述
【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述