红黑树RBTree的模拟实现
文章目录
- 前言
- 一、红黑树的概念
- 二、红黑树的性质
- 三、红黑树节点的定义
- 四、红黑树的插入Insert
- 代码实现：
- 五、红黑树的验证
- 六、红黑树与AVL树的比较
- 七、红黑树测试
- 附录：
前言
在上篇文章我们了解了第一种平衡二叉搜索树AVL树，我们知道AVL树是通过平衡因子来控制左右子树高度差，从而将二叉树变成一颗平衡二叉搜索树。但是平衡二叉搜索树因为只要不满足平衡因子的差值就需要旋转，导致旋转的次数太对了，效率可能没有那么好。本篇文章我们将要了解另外一种平衡规则控制的二叉搜索树–红黑树（RBTree）！
正文开始
一、红黑树的概念
红黑树是一种二叉搜索树，在二叉树的每个节点上增加一个存储为表示该节点的颜色。颜色可以红色（RED）或黑色（BLACK）。通过对任意一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长2倍，因而是接近平衡的。(例如：下图正是一颗红黑树)
二、红黑树的性质
根据上图示例，我们能够发现一颗红黑树具有如下几条性质：
1.每个节点不是红色就是黑色。
2.根节点是黑色的。
3.如果一个节点是红色的，那么他的左右孩子都是黑色的。
4.对于每个节点，从该节点到其所有后代的叶子结点的简单路径上，均包含相同数量的黑色节点！
5.每个叶子节点都是黑色的（此处的也是节点指的是空节点）。
满足以上红黑树的性质，就能保证该棵树是一颗平衡树吗？为什么？
我们在概念中提到，红黑树确保没有一条路径会比其他路径长2倍，因而是接近平衡的。因此问题就转变为为什么如果这颗树是一颗红黑树，就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍？
- 根据第三点，红色节点的孩子是黑色的，这点能保证没有连续的两个红色节点。
- 根据第四点，从该节点到后代的叶子路径上，包含数量相同的黑色节点，此处假如是从根节点计算，最坏情况下根节点左孩子为空，此时说明了从根节点开始一条路径上只有2个黑色节点(不包含NULL节点)，这也要求了根节点的右孩子必须且有2个黑色节点，此时根节点的右孩子可以存在一个红色节点，但是配合第三点，如果存在红色节点且红色节点的孩子一定是黑色的，此时右子树中任意一条路径的黑色节点已经达到两个，说明不能再存在黑色节点了，因此在黑色节点下最后链接一个红色节点右子树就需要停止。（如下图所示为例）
此时我们发现最短的路径长度为2（15->9）,最长的路径长度为4（15->19->17->16）【其一】，这也就验证了一颗红黑树中，其最长路径中的节点个数不会超过最短路径中的节点个数的两倍！
三、红黑树节点的定义
enum Colour
{
RED,
BLACK,
};
template<class K,class V>
struct RBTreeNode
{
RBTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED)
{}
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<K, V> _kv;
Colour _col;//节点的颜色，类型为枚举类型
};
在上述红黑树节点的定义中，新节点的_col默认给成红色是有意为之还是红黑色都可以呢？
当我们新插入一个节点之后，可能会破坏红黑树的规则，因此我们要插入一个节点要尽可能少得破坏红黑树的规则。
而插入红色节点以后，可能会破坏性质3，因为可能会导致连续的红节点；而插入黑色节点一定会破坏性质4，因为插入一个黑色节点必然会使插入节点的这一条路径黑色节点个数增加1，从而导致性质4被破坏，因此从破坏力度来说选择红色节点，插入红色节点可能破坏性质3，插入黑色节点一定破坏性质4。
从维护红黑树的角度来说，也是破坏4更难维护，因为它牵扯到每一条路径，可能会让红黑树产生翻天覆地的变化(具体详情往下看Insert)。
四、红黑树的插入Insert
红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可以分为两步：
1.按照二叉搜索树的规则插入新节点
2.检测新节点插入后，红黑树的性质是否被破坏。
bool Insert(const pair<K, V>& kv)
{
//1.搜索树的规则插入
//2.看是否违反平衡规则，如果违反就需要处理：旋转
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;//性质2：根节点为黑色
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);
cur->_col = RED;//新增节点都是红色
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//维护处理
//......
}
当走完上述代码后，我们知道此时新节点已经插入到正确的位置了，现在要做的是检查和维护这颗红黑树。
1.如果双亲节点的颜色是黑色，那说明没有违反红黑树的任何性质，则不需要调整。
2.新插入节点的双亲节点颜色红色时，此时违反性质三（不能有连续的红色节点），此时需要对红黑树进行调整。调整需分情况来讨论：（约定cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点）
情况一：cur为红，p为红，g为黑，u存在且为红
基于上述情况1进行的向上调整！
注意：此处看到的树，可能是一颗完整的树，也可能是一颗子树。
如果g是根节点，调整完成后，需要将g改为黑色
如果g是子树，g一定有双亲，且g的双亲如果是红色，需要继续向上调整
情况二：cur为红，p为红，g为黑，u不存在/u存在且为黑
说明：u的情况有两种:
- 如果u节点不存在，则cur一定时新插入的节点，因为如果cur不是新插入节点，则cur和p一定有一个节点的颜色是黑色，就不满足性质4：每条路径的黑色节点个数相同！
- 如果u节点存在，则其一定为黑色的，那么cur节点原来的颜色一定是黑色，现在看到其是红色的原因是因为cur的字数在调整过程的过程中将cur节点的颜色由黑色变成了红色！
p为g的左孩子，cur为p的左孩子，则进行右单旋；
p为g的右孩子，cur为p的右孩子，则进行左单旋；
p,g变色–p变成黑色，g变成红色。（旋转规则在AVL树种有详细讲解，大家可以去看前言链接！！！）
情况三：cur为红，p为红，g为黑，u不存在/u存在且为黑
p为g的左孩子，cur为p的右孩子，则针对p做左单旋；
p为g的右孩子，cur为p的左孩子，则针对p做右单旋；
则转换为了情况二。
代码实现：
bool Insert(const pair<K, V>& kv)
{
//1.搜索树的规则插入
//2.看是否违反平衡规则，如果违反就需要处理：旋转
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);
cur->_col = RED;//新增节点都是红色
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//存在连续的红色节点
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
assert(grandfather);
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
//情况1：
if (uncle && uncle->_col == RED)//叔叔存在且为红
{
//变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续往上调整
cur = grandfather;
parent = cur->_parent;
}
else//叔叔不存在 或者 叔叔存在且为黑
{
if (cur == parent->_left)
{
// g
// p
// c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//双旋
{
// g
// p
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else//grandfather->_right == parent
{
Node* uncle = grandfather->_left;
//情况一：
if (uncle && uncle->_col == RED)
{
//变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
// g
// p
// c
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else //双旋
{
// g
// 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;
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (parent == ppNode->_left)
{
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;
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}
五、红黑树的验证
红黑树的验证检测分为两步：
1.检测其是否满足二叉搜索树（中序遍历是否有序）
2.检测其是否满足红黑树的性质
//检测第一步：是否为二叉搜索树
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
//检测第二步：是否满足性质
bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
{
//走到null之后,判断k和black是否相等
if (nullptr == pRoot)
{
if (k != blackCount)
{
cout << "违反性质四，每条路径中黑色节点的个数必须相同" << endl;
return false;
}
return true;
}
//统计黑色节点的个数
if (BLACK == pRoot->_col)
k++;
//监测当前节点与其双亲是否都为红色
if (RED == pRoot->_col && pRoot->_parent && pRoot->_parent->_col == RED)
{
cout << "违反性质三:存在连在一起的红色节点" << endl;
return false;
}
return _IsValidRBTree(pRoot->_left, k, blackCount) &&
_IsValidRBTree(pRoot->_right, k, blackCount);
}
六、红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O（log2 N），红黑树不追求绝对平衡，其只需要保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树的实现比较简单，所以实际运用中红黑树更多。
七、红黑树测试
红黑树测试时，我们需要知道其最长路径和其最短路径。
int _maxHeight(Node* root)
{
if (root == nullptr)
return 0;
int lh = _maxHeight(root->_left);
int rh = _maxHeight(root->_right);
return lh > rh ? lh + 1 : rh + 1;
}
int _minHeight(Node* root)
{
if (root == nullptr)
return 0;
int lh = _minHeight(root->_left);
int rh = _minHeight(root->_right);
return lh < rh ? lh + 1 : rh + 1;
}
我们可以生成随机数和生成有序数来加以验证
void TestRBTree2()
{
const size_t N = 1024*1024;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; ++i)
{
//v.push_back(rand());
v.push_back(i);
}
RBTree<int, int> t;
for (auto e : v)
{
t.Insert(make_pair(e, e));
}
//t.levelOrder();
cout << endl;
cout << endl;
cout << "是否平衡?" << t.IsBalanceTree() << endl;
t.Height();
//t.InOrder();
}
首先我们使用有序数来验证，我们将使用N=1024*1024个数据进行测试
接下来我们使用随机数来验证，仍然使用N=1024*1024个数据进行测试
我们发现，我们自构的红黑树均完成了以上测试。
附录：
#pragma once
#include"AVLTree.h"
namespace zzy
{
enum Colour
{
RED,
BLACK,
};
template<class K, class V>
struct RBTreeNode
{
RBTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED)
{}
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<K, V> _kv;
Colour _col;
};
template<class K, class V>
struct RBTree
{
typedef RBTreeNode<K, V> Node;
public:
bool Insert(const pair<K, V>& kv)
{
//1.搜索树的规则插入
//2.看是否违反平衡规则，如果违反就需要处理：旋转
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);
cur->_col = RED;//新增节点都是红色
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//存在连续的红色节点
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
assert(grandfather);
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
//情况1：
if (uncle && uncle->_col == RED)//叔叔存在且为红
{
//变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续往上调整
cur = grandfather;
parent = cur->_parent;
}
else//叔叔不存在 或者 叔叔存在且为黑
{
if (cur == parent->_left)
{
// g
// p
// c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//双旋
{
// g
// p
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else//grandfather->_right == parent
{
Node* uncle = grandfather->_left;
//情况一：
if (uncle && uncle->_col == RED)
{
//变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
// g
// p
// c
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else //双旋
{
// g
// p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
//处理根 一定是黑色
_root->_col = BLACK;
return true;
}
//情况二和情况三旋转+变色以后，这颗字数不违反红黑树规则，相比插入前，黑色节点的数量是不变的，不会影响上层，处理就结束了
void Height()
{
cout << "最长路径为：" << _maxHeight(_root) << endl;
cout << "最短路径为：" << _minHeight(_root) << endl;
}
bool IsBalanceTree()
{
//检查红黑树有几条规则
Node* pRoot = _root;
//空树也是红黑树
if (nullptr == pRoot)
return true;
//检查根节点是否满足情况
if (BLACK != pRoot->_col)
{
cout << "违反红黑树性质二：根节点必须为黑色" << endl;
return false;
}
//获取任意一条路径中黑色节点的个数 --作为基准值进行比较
size_t blackCount = 0;
Node* pCur = pRoot;
while (pCur)
{
if (BLACK == pCur->_col)
blackCount++;
pCur = pCur->_left;
}
//监测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
size_t k = 0;
return _IsValidRBTree(pRoot, k, blackCount);
}
private:
//左旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (parent == ppNode->_left)
{
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;
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}
//检测第一步：是否为二叉搜索树
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
//检测第二步：是否满足性质
bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
{
//走到null之后,判断k和black是否相等
if (nullptr == pRoot)
{
if (k != blackCount)
{
cout << "违反性质四，每条路径中黑色节点的个数必须相同" << endl;
return false;
}
return true;
}
//统计黑色节点的个数
if (BLACK == pRoot->_col)
k++;
//监测当前节点与其双亲是否都为红色
if (RED == pRoot->_col && pRoot->_parent && pRoot->_parent->_col == RED)
{
cout << "违反性质三:存在连在一起的红色节点" << endl;
return false;
}
return _IsValidRBTree(pRoot->_left, k, blackCount) &&
_IsValidRBTree(pRoot->_right, k, blackCount);
}
int _maxHeight(Node* root)
{
if (root == nullptr)
return 0;
int lh = _maxHeight(root->_left);
int rh = _maxHeight(root->_right);
return lh > rh ? lh + 1 : rh + 1;
}
int _minHeight(Node* root)
{
if (root == nullptr)
return 0;
int lh = _minHeight(root->_left);
int rh = _minHeight(root->_right);
return lh < rh ? lh + 1 : rh + 1;
}
private:
Node* _root = nullptr;
};
//遇到红色节点就检查父亲，这样好实现
//root->NULL才是路径
void TestAVLTree1()
{
int a[] = { 8,7,6,5,4,3,2,1 };
AVLTree<int, int> t;
for (auto& e : a)
{
t.insert(make_pair(e, e));
}
}
void TestRBTree2()
{
const size_t N = 1024*1024;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; ++i)
{
v.push_back(rand());
//v.push_back(i);
}
RBTree<int, int> t;
for (auto e : v)
{
t.Insert(make_pair(e, e));
}
//t.levelOrder();
cout << endl;
cout << endl;
cout << "是否平衡?" << t.IsBalanceTree() << endl;
t.Height();
//t.InOrder();
}
}
(本章完！)