今天,带来无数人的噩梦——红黑树的讲解。文中不足错漏之处望请斧正!
如果还没看过AVLTree讲解的一定要去看看,看完才能更好理解红黑树!
是什么
红黑树是自平衡的二叉搜索树。
红黑树的规则:
- 每个结点非黑即红
- 根结点为黑
- 叶子结点为黑(此处的叶子结点指空结点)
- 不能有连续的红结点,但可以有连续的黑结点
- 每条简单路径上的黑结点数量相同
满足以上规则,就能保证最长路径不超过最短路径的二倍,保持了一种相对宽松的平衡。
实现
*为了降低学习成本,部分细节先略过,等封装map和set再添上。
结构
enum Color
{
RED, BLACK
};
template<class K, class V>
struct RBTreeNode
{
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Color _clr;
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr),
_right(nullptr),
_parent(nullptr),
_kv(kv),
_clr(RED)
{}
};
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
...
private:
Node* _root = nullptr;
};
结点默认红色?往后看。
Insert
实现思路
BST插入总是找位置+插入,插入后只要保持红黑树的规则不被打破就可以。
新插入的结点设为什么颜色?
设为黑色:必然打破“黑结点数量相同”的规则。
设为红色:可能打破“不能有连续的红节点”的规则。(如果父亲是黑,就不会打破规则)
那自然设为红色。
我们要维持的规则主要就是上面两条。
注:
- 称新插入的结点为cur
- 称cur的父结点为parent
- 称parent除cur外的另一孩子为uncle
- 称parent的父结点为grandParent
插入新结点cur后:
- parent为黑:不打破规则,插入结束
-
parent为红:打破规则,调整
- uncle为红:直接着色
- uncle不存在/为黑:旋转+着色
为什么根据uncle就能判断?
若插入后需要调整:
- parent必然为红
- grandParent必然为黑(不能有连续的红结点)
既然cur、parent、grandParent都确定了,那我们只用根据u来分类即可。
- uncle为红
- uncle不存在
- uncle为黑
情况1:u为红(抽象图)
u为红,直接改色。
- cur为红,parent为红打破了“不能有连续红节点”,所以p必须变黑
- parent变黑,到parent的简单路径上都增加了一个黑节点,因为“每条简单路径上黑节点数量相同”,所以到uncle的简单路径上也需要多一个黑节点
- 我们还需要考虑g是子树还是根
- 若是子树,变红没毛病,但g变红可能向上影响(如果g的parent是红,就打破“不能有连续红结点的规则”),所以我们需要把g当做新一轮的cur继续往后看是否需要调整
- 若是根,需要重新变黑(根结点必须是黑色)
u为红直接变色:p变黑、u变黑、g变红
- 当g为根→g变黑
- 当g不为根→g作新cur往上走
- 当p为黑就停(最差走到默认为黑的根结点)
情况2:u不存在
u不存在,单旋+变色。
u不存在,则cur一定是新增。因为u不存在,就代表右边没有黑,那左边也没有黑:p为红,cur也为红,且没有其他黑,那么cur一定是新增。
- p是g的左孩子 = 左高 = 右单旋+变色(g变红,p变黑)
- p是g的右孩子 = 右高 = 左单旋+变色(g变红,p变黑)
- 旋转后不向上影响,调整结束
情况3:u为黑,整体过高
*有了AVLTree的积累,我们这就只讲一种单旋,另一种同理,反过来而已
- p是g的左孩子、cur是p的左孩子 = 整体左高 = 右单旋+变色(g变红,p变黑)
- p是g的右孩子、cur是p的右孩子 = 整体右高 = 左单旋+变色(g变红,p变黑)
- 旋转后不向上影响(不会导致和上面出现连续的红节点,被旋转的部分也没有徒增给节点),调整结束
情况4:u为黑,整体过高且局部过高
- p是g的左,cur是p的右 = 高左中右高 = 先对p左单旋,再对g右单旋,最后变色(cur变黑、g变红)
- p是g的右,cur是p的左 = 高右中左高 = 先对p右单旋,再对g左单旋,最后变色(cur变黑、g变红)
- 旋转后不向上影响,调整结束
旋转总结
到这里我们发现情况2、3、4有些相似之处,所以我们可以进一步分类:
- 种类1:
- u为红——直接变色并向上调整
- 种类2:
- u不存在/u为黑且规则高——单旋+变色解决
- u为黑且不规则高——双旋+变色解决
最后,我们要推理一个结论来圆满RBTree调平衡的合理性:种类2一定是由种类1变化而来的。
依照这个结论:种类1通过变色后向上调整,要么直接解决问题,要么演变为种类2,而种类2旋转后必然能解决问题,那么红黑树的调整我们也就必然解决干净了。
调整参考代码
while (parent && parent->_clr == RED) {
Node *grandParent = parent->_parent;
if(parent == grandParent->_left) {
Node *uncle = grandParent->_right;
//种类1: 直接变色
if (uncle && uncle->_clr == RED) {
parent->_clr = uncle->_clr = BLACK;
grandParent->_clr = RED;
cur = grandParent;
parent = cur->_parent;
} else { //种类2: 旋转+变色
if(cur == parent->_left) { //整体过高: 单旋
rotateR(grandParent);
parent->_clr = BLACK;
grandParent->_clr = RED;
} else { //整体过高+局部过高: 双旋
rotateL(parent);
rotateR(grandParent);
cur->_clr = BLACK;
grandParent->_clr = RED;
}
break; //旋转后不再向上影响,结束调整
}
} else { //相反而已
Node *uncle = grandParent->_left;
if (uncle && uncle->_clr == RED) {
parent->_clr = uncle->_clr = BLACK;
grandParent->_clr = RED;
cur = grandParent;
parent = cur->_parent;
} else {
if(cur == parent->_right) {
rotateL(grandParent);
parent->_clr = BLACK;
grandParent->_clr = RED;
} else {
rotateR(parent);
rotateL(grandParent);
cur->_clr = BLACK;
grandParent->_clr = RED;
}
break;
}
}
}
旋转参考代码
void rotateL(Node *parent) {
Node *subR = parent->_right;
Node *subRL = subR->_left;
Node *grandParent = parent->_parent;
//1. subRL变成parent的右子树
parent->_right = subRL;
if (subRL) subRL->_parent = parent;
//2. parent变成subR的左子树
subR->_left = parent;
parent->_parent = subR;
//3. subR变成局部根或整体根
if (grandParent == nullptr) { //整体根
_root = subR;
_root->_parent = nullptr;
} else { //局部根
subR->_parent = grandParent;
if (parent == grandParent->_left) grandParent->_left = subR;
if (parent == grandParent->_right) grandParent->_right = subR;
}
}
void rotateR(Node *parent) {
Node *subL = parent->_left;
Node *subLR = subL->_right;
Node *grandParent = parent->_parent;
//1. subLR变成parent的左
parent->_left = subLR;
if (subLR) subLR->_parent = parent;
//2. parent变成subL的右
subL->_right = parent;
parent->_parent = subL;
//3. subL变成局部根或整体根
if (grandParent == nullptr) { //整体根
_root = subL;
_root->_parent = nullptr;
} else { //局部根
subL->_parent = grandParent;
if (parent == grandParent->_left) grandParent->_left = subL;
if (parent == grandParent->_right) grandParent->_right = subL;
}
}
Insert参考代码
bool insert(const pair <K, V> &kv) {
if (_root == nullptr) {
_root = new Node(kv, BLACK); //根节点必须是黑的
return true;
}
//1. 找位置
Node *cur = _root;
Node *parent = nullptr;
while (cur) {
parent = cur;
if (kv.first < cur->_kv.first) {
cur = cur->_left;
} else if (kv.first > cur->_kv.first) {
cur = cur->_right;
} else if (kv.first == cur->_kv.first) {
return false;
} else { assert(false);}
}
//2. 插入
cur = new Node(kv); //默认红色
cur->_parent = parent;
if (kv.first < parent->_kv.first)
parent->_left = cur;
else
parent->_right = cur;
//3. parent的clr为红,向上影响了,需要调整
while (parent && parent->_clr == RED) {
Node *grandParent = parent->_parent;
if(parent == grandParent->_left) {
Node *uncle = grandParent->_right;
//种类1: 直接变色
if (uncle && uncle->_clr == RED) {
parent->_clr = uncle->_clr = BLACK;
grandParent->_clr = RED;
cur = grandParent;
parent = cur->_parent;
} else { //种类2: 旋转+变色
if(cur == parent->_left) { //整体过高: 单旋
rotateR(grandParent);
parent->_clr = BLACK;
grandParent->_clr = RED;
} else { //整体过高+局部过高: 双旋
rotateL(parent);
rotateR(grandParent);
cur->_clr = BLACK;
grandParent->_clr = RED;
}
break; //旋转后不再向上影响,结束调整
}
} else { //相反而已
Node *uncle = grandParent->_left;
if (uncle && uncle->_clr == RED) {
parent->_clr = uncle->_clr = BLACK;
grandParent->_clr = RED;
cur = grandParent;
parent = cur->_parent;
} else {
if(cur == parent->_right) {
rotateL(grandParent);
parent->_clr = BLACK;
grandParent->_clr = RED;
} else {
rotateR(parent);
rotateL(grandParent);
cur->_clr = BLACK;
grandParent->_clr = RED;
}
break;
}
}
}
_root->_clr = BLACK; //根节点始终为黑
return true;
}
其实红黑树还有multi版本,允许重复,有insert_unique和insert_equal,至于相同的插入在左边还是右边就无所谓了,因为高度过大后需要旋转,而不管是插入哪边旋转后的结果都一样。
测试
红黑树的测试不像以前那样打印点信息就能解决,而是要写个方法来确定我们的树100%没问题——颜色没问题、路径长度也没问题。
...
//测试
public:
//测试RBTree:
//颜色正确 == 路径长度正确
//路径长度正确 != 颜色正确
void inorder() { inorder(_root);}
bool isBlance()
{
if(_root == nullptr) return true;
if(_root->_clr == RED)
{
cout << "违反规则:根为红" << endl;
return false;
}
int refVal = 0;
Node* left = _root;
while(left)
{
if(left->_clr == BLACK) ++refVal;
left = left->_left;
}
return check(_root, 0, refVal);
}
private:
void inorder(Node* root)
{
if(root == nullptr) return;
inorder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
inorder(root->_right);
}
bool check(Node* root, int blackCnt, const int& refVal)
{
if(root == nullptr)
{
if(blackCnt != refVal)
{
cout << "违反规则:黑色结点数量不同" << endl;
return false;
}
return true;
}
if(root->_clr == RED && root->_parent->_clr == RED)
{
cout << "违反规则:出现了连续红色节点" << endl;
return false;
}
if(root->_clr == BLACK) ++blackCnt;
return check(root->_left, blackCnt, refVal)
&& check(root->_right, blackCnt, refVal);
}
};
void testRBTree()
{
// int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
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> t;
for(auto e : a) {
t.insert(make_pair(e, e));
}
t.inorder();
cout << t.isBlance() << endl;
}
#include <iostream>
using namespace std;
#include "RBTree.h"
int main() {
testRBTree();
return 0;
}
3:3
7:7
9:9
11:11
14:14
15:15
16:16
18:18
26:26
1
为什么Inorder要弄成子函数或者函数重载?
因为类外调用Inorder时得传参,_root是私有成员,想传也没办法访问到私有成员。
对比AVLTree
对平衡的要求没那么严格,插入删除的时候就会少很多旋转。虽然单次查找效率效率是2logN,但对于CPU来说logN和2logN区别很小,红黑树总体来说效率是更高的。
性能分析
红黑树是近似平衡的树,没有什么最坏情况,插入的时间复杂度为O(log(N)),查找也是。
应用场景
- C++的STL
- Java的库
- Linux内核
- 其他库
- …
今天的分享就到这里了,感谢您能看到这里。文章来源:https://www.toymoban.com/news/detail-467735.html
这里是培根的blog,期待与你共同进步!文章来源地址https://www.toymoban.com/news/detail-467735.html
到了这里,关于【C++进阶5-红黑树】噩梦般的存在?手提AVLTree暴揍红黑树!的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!