C++进阶：红黑树介绍及模拟实现
上次介绍了AVL树：C++进阶：AVL树详解及模拟实现（图示讲解旋转过程）
今天就来紧接着来红黑树啦!!!
文章目录
- 1.红黑树介绍
- 约束规则
- 2.项目文件规划
- 3.整体框架（节点和Tree）
- 4.RBL树的新节点插入
- 4.1 叔叔节点存在且为红
- 4.2 叔叔节点不存在
- 4.3叔叔节点存在而且为黑（单旋情况，左子树的左，和右子树的右）
- 4.4叔叔节点存在而且为黑（双旋情况，左子树的右，和右子树的左）
- 4.5完整版Insert（）
- 5.中序方便过会测试
- 6.编写函数看是否满足要求
- 7.测试
- 8.全部代码
- 8.1 RBTree.h
- 8.2 test.cpp
1.红黑树介绍
红黑树是一种自平衡的二叉搜索树，它在每个节点上增加了一个表示颜色的存储位，可以是红色（Red）或黑色（Black）。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的从而保证了查找、插入和删除操作的时间复杂度为 O ( l o g N ) O(logN) O(logN)
约束规则
-
每个结点是红色或者黑色
-
根节点是黑色
-
如果一个节点是红色的，则它的两个孩子结点是黑色的（不能有连续的红节点）
-
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
-
叶子节点（NIL节点）是黑色的(此处的叶子结点指的是空结点)
2.项目文件规划
头文件RBTree.h：进行模拟的编写
源文件test.cpp：进行测试，检查代码逻辑是否满足期望
3.整体框架（节点和Tree）
enum Colour//使用枚举来定义，后面模拟哈希时也会用到类似的
{
RED,
BLACK
};
template<class K,class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;//左节点
RBTreeNode<K, V>* _right;//右节点
RBTreeNode<K, V>* _parent;//父亲节点
Colour _col;//颜色，红和黑嘛
pair<K,V> _kv;//节点里存pair
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;//名字太长了，叫Node也更好理解
public:
private:
Node* _root = nullptr;//给上缺省值
};
4.RBL树的新节点插入
基本步骤：
查找插入位置： 首先，我们需要找到新节点应该插入的位置。从根节点开始，按照二叉搜索树的性质，逐级向左或向右比较键值，直到找到一个合适的位置。
插入新节点： 找到插入位置后，我们创建一个新的节点，颜色为红，并将其插入到树中。如果树为空，则新节点成为树的根节点。否则，将新节点插入到合适的位置，使得树仍然保持二叉搜索树的性质。
插入后有需要变化时情况很多，下面具体分析
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：
如果新插入节点的父亲节点是黑，那根本不会违反规则，如果要调整只有如下情况：
bool Insert(const pair<K,V> kv)
{
if (_root == nullptr)//如果为空，直接更换新节点
{
_root = new Node(kv);
_root->_col = BLACK;//注意默认是红，这里改成黑
return true;
}
Node* parent = nullptr;//存一下，新根才能链接
Node* cur = _root;
while (cur)//开始找插入位置
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;//不能有相等的
}
}
cur = new Node(kv); //这是默认红色的
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;//新节点链接成功了
while (parent != nullptr
&& parent->_col == RED)//父亲节点存在且是红进来，黑的直接满足不用调整
{
//这里进行处理
}
_root->_col = BLACK;//最后直接改根节点，不用再具体考虑
return true;
}
4.1 叔叔节点存在且为红
以下步骤来调整：
- 将父节点和叔叔节点都改为黑色。
- 将祖父节点改为红色。
- 将当前节点指向祖父节点，并将祖父节点设为当前节点的父节点(开始向上走)。
4.2 叔叔节点不存在
如果u节点不存在，则cur一定是新插入节点，因为如果cur不是新插入节点则cur和p一定有一个节点的颜色是黑色，就不满足性质4: 每条路径黑色节点个数相同。
- p为g的左孩子，cur为p的左孩子，则进行右单旋转
p为g的右孩子，cur为p的右孩子，则进行左单旋转
- p、g变色—>p变黑，g变红
void RotateL(Node* parent)//左旋
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
Node* ppnode = parent->_parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subR;
}
else
{
ppnode->_right = subR;
}
subR->_parent = ppnode;
}
}
void RotateR(Node* parent)//右旋
{
++rotateSize;
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
Node* ppnode = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subL;
}
else
{
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
}
4.3叔叔节点存在而且为黑（单旋情况，左子树的左，和右子树的右）
如果u节点存在，则其一定是黑色的，那么cur节点原来的颜色一定是黑色的现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色
4.4叔叔节点存在而且为黑（双旋情况，左子树的右，和右子树的左）
p为g的左孩子，cur为p的右孩子，左右双旋+变色
p为g的右孩子，cur为p的左孩子，右左双旋 +变色
4.5完整版Insert（）
bool Insert(const pair<K,V> kv)
{
if (_root == nullptr)//如果为空，直接更换新节点
{
_root = new Node(kv);
_root->_col = BLACK;//注意默认是红，这里改成黑
return true;
}
Node* parent = nullptr;//存一下，新根才能链接
Node* cur = _root;
while (cur)//开始找插入位置
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;//不能有相等的
}
}
cur = new Node(kv); //这是默认红色的
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;//新节点链接成功了
while (parent != nullptr
&& parent->_col == RED)//父亲节点存在且是红进来，黑的直接满足不用调整
{
Node* grandfather = parent->_parent;
//接下来分两种：parent是grandfather左或者右
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 (cur == parent->_left)//cur在parent左，单旋
{
// g
// p u
// c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//cur在parent右，双旋
{
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
}
//情况二一旦旋转完了，不用向上了
break;
}
else//parent是grandfather右
{
Node* uncle = grandfather->_left;
// 情况一：叔叔存在且为红
if (uncle && uncle->_col == RED)
{
// 变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else// 情况二：叔叔不存在或者存在且为黑
{
// 旋转+变色
// g
// u p
// c
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
}
break;
}
}
_root->_col = BLACK;//最后直接改根节点，不用再具体考虑
return true;
}
5.中序方便过会测试
void InOrder()
{
_InOrder(_root);
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first<< endl;
_InOrder(root->_right);
}
6.编写函数看是否满足要求
就从规定出发：
- 根节点不是黑的不满足
- 不是每条路径的黑色节点数量都相同
- 存在连续的红节点了
这些都是不满足要求
bool IsBalance()
{
if (_root->_col == RED)
{
return false;
}
//这里我们先算一条路径的黑色节点数量，作为参考
int ref = 0;
Node* cur = _root;
while (cur)
{
if(cur->_col==BLACK)
ref++;
cur = cur->_left;//就求最左路径
}
return Check(_root, 0, ref);
}
bool Check(Node* cur, int blackNum, int ref)
{
if (cur == nullptr)//==nullptr 说明一条路径走完了
{
if (blackNum != ref)
{
cout << "黑色节点的数量不相等" << endl;
return false;
}
return true;
}
//这里开始检查没有连续的红，就看每个cur节点和他的父亲就行
if (cur->_col == RED && cur->_parent->_col == RED)
{
cout << cur->_kv.first << "存在连续的红色节点" << endl;
return false;
}
if (cur->_col == BLACK)
{
blackNum++;
}
return Check(cur->_left, blackNum, refBlackNum)
&& Check(cur->_right, blackNum, refBlackNum);//递归进去找
}
IsBalance()函数首先检查根节点的颜色是否为红色，如果是，则不满足红黑树的性质。然后，通过调用Check()函数来递归检查每个节点，确保在每条路径上没有连续的红色节点，并统计路径上的黑色节点数量，最后与参考值进行比较。
Check()函数中，递归遍历每个节点，并检查其颜色。如果当前节点为红色，并且其父节点也为红色，则说明存在连续的红色节点，不满足红黑树的性质。如果当前节点为黑色，则增加黑色节点计数器。递归地对当前节点的左右子节点进行检查，直到遍历完整棵树的所有路径。通过这样的检查，我们可以验证红黑树是否满足性质，从而确认树的平衡性。
7.测试
void TestRBTree1()
{
int a[] = { 4, 2, 6, 1, 3, 5, 15};
RBTree<int, int> t;
for (auto e : a)
{
t.Insert(make_pair(e, e));
}
t.InOrder();
cout << t.IsBalance() << endl;
}
8.全部代码
8.1 RBTree.h
#pragma once
enum Colour//使用枚举来定义，后面模拟哈希时也会用到类似的
{
RED,
BLACK
};
template<class K,class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;//左节点
RBTreeNode<K, V>* _right;//右节点
RBTreeNode<K, V>* _parent;//父亲节点
Colour _col;//颜色，红和黑嘛
pair<K,V> _kv;//节点里存pair
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;//名字太长了，叫Node也更好理解
public:
bool Insert(const pair<K,V> kv)
{
if (_root == nullptr)//如果为空，直接更换新节点
{
_root = new Node(kv);
_root->_col = BLACK;//注意默认是红，这里改成黑
return true;
}
Node* parent = nullptr;//存一下，新根才能链接
Node* cur = _root;
while (cur)//开始找插入位置
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;//不能有相等的
}
}
cur = new Node(kv); //这是默认红色的
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;//新节点链接成功了
while (parent != nullptr
&& parent->_col == RED)//父亲节点存在且是红进来，黑的直接满足不用调整
{
Node* grandfather = parent->_parent;
//接下来分两种：parent是grandfather左或者右
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 (cur == parent->_left)//cur在parent左，单旋
{
// g
// p u
// c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//cur在parent右，双旋
{
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
}
//情况二一旦旋转完了，不用向上了
break;
}
else//parent是grandfather右
{
Node* uncle = grandfather->_left;
// 情况一：叔叔存在且为红
if (uncle && uncle->_col == RED)
{
// 变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else// 情况二：叔叔不存在或者存在且为黑
{
// 旋转+变色
// g
// u p
// c
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
}
break;
}
}
_root->_col = BLACK;//最后直接改根节点，不用再具体考虑
return true;
}
void RotateL(Node* parent)//左旋
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
Node* ppnode = parent->_parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subR;
}
else
{
ppnode->_right = subR;
}
subR->_parent = ppnode;
}
}
void RotateR(Node* parent)//右旋
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
Node* ppnode = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subL;
}
else
{
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
}
void InOrder()
{
_InOrder(_root);
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first<< endl;
_InOrder(root->_right);
}
bool IsBalance()
{
if (_root->_col == RED)
{
return false;
}
//这里我们先算一条路径的黑色节点数量，作为参考
int ref = 0;
Node* cur = _root;
while (cur)
{
if(cur->_col==BLACK)
ref++;
cur = cur->_left;//就求最左路径
}
return Check(_root, 0, ref);
}
bool Check(Node* cur, int blackNum, int ref)
{
if (cur == nullptr)//==nullptr 说明一条路径走完了
{
if (blackNum != ref)
{
cout << "黑色节点的数量不相等" << endl;
return false;
}
return true;
}
//这里开始检查没有连续的红，就看每个cur节点和他的父亲就行
if (cur->_col == RED && cur->_parent->_col == RED)
{
cout << cur->_kv.first << "存在连续的红色节点" << endl;
return false;
}
if (cur->_col == BLACK)
{
blackNum++;
}
return Check(cur->_left, blackNum, ref)
&& Check(cur->_right, blackNum, ref);//递归进去找
}
private:
Node* _root = nullptr;//给上缺省值
};
void TestRBTree1()
{
int a[] = { 4, 2, 6, 1, 3, 5, 15};
RBTree<int, int> t;
for (auto e : a)
{
t.Insert(make_pair(e, e));
}
t.InOrder();
cout << t.IsBalance() << endl;
}
8.2 test.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include"RBTree.h"
int main()
{
TestRBTree1();
return 0;
}
今天就到这里啦！！
