✅<1>主页:我的代码爱吃辣
📃<2>知识讲解:数据结构——红黑树
☂️<3>开发环境:Visual Studio 2022
💬<4>前言:红黑树也是一颗二叉搜索树,其作为map,set的底层容器,具有非常好的搜索性能,仅仅通过控制颜色和位置就能达到一种,近似平衡的效果,大大减少了旋转的次数。
目录
一.红黑树的概念
二. 红黑树的性质
三.红黑树节点及其整体的定义
四.红黑树的插入操作
五.红黑树 find
六.析构函数
七.红黑树的验证
八. 红黑树与AVL树的比较
一.红黑树的概念
红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或
Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路
径会比其他路径长出俩倍,因而是接近平衡的。
二. 红黑树的性质
1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的,则它的两个孩子结点是黑色的
4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均 包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)NIL结点
思考:为什么满足上面的性质,红黑树就能保证:其最长路径中节点个数不会超过最短路径节点个数的两倍?
答案:因为性质3限制了,一条路径上,不可能出现连续的两个红色结点。又因为性质4,每条路径上黑色结点数目相同,那么最短路径就一定是全是黑色结点的路径,最长路径一定是红黑交错的路径,因为根节点一定是黑色,那么最长路径上红黑结点树一定是相等的,所以最长路径最多是最短路径的两倍。
三.红黑树节点及其整体的定义
//枚举
enum Color
{
RED,//红色
BLACK//黑色
};
template<class K,class V>
struct _RBTreeNode
{
_RBTreeNode(pair<K,V> kv)
:_kv(kv),
_col(RED),//默认红色
_left(nullptr),
_right(nullptr),
_parent(nullptr)
{
}
pair<K, V> _kv; //存储数值
Color _col; //颜色
_RBTreeNode<K, V>* _left; //左孩子
_RBTreeNode<K, V>* _right; //右孩子
_RBTreeNode<K, V>* _parent; //父亲
};
#pragma once
#include<iostream>
using namespace std;
template<class K,class V>
class RBTRee
{
typedef _RBTreeNode<K, V> Node;//结点
public:
Node* find(const K key)
{
//....
}
bool insert(pair<K, V> kv)
{
//....
}
void Inorder()
{
//...
}
~RBTRee()
{
//...
}
private:
Node* _root = nullptr;//根节点
};
思考:在节点的定义中,为什么要将节点的默认颜色给成红色的?
答案:新创建的结点,妖色要么红色,要么黑色,除了颜色区别之外,就是在插入时对整个树的影响不同,如果插入的是黑色,会影响整颗树,所有路径上的黑色结点说就会不同,必然违反性质4。如果插入的是红色结点,仅仅是局部的影响,可能会影响性质3,一定不会影响性质4。
四.红黑树的插入操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可分为两步:
1. 按照二叉搜索的树规则插入新节点。
bool insert(pair<K, V> kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kv.first < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
//找到了合适的位置
cur = new Node(kv);
if (kv.first < parent->_kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//....
}
因为性质2,所以我们每一次插入数据都想根节点变成黑色。
2.检测新节点插入后,红黑树的性质是否造到破坏,若满足直接退出,否则对红黑树进行旋转着色处理。
因为新节点的默认颜色是红色,因此:如果其双亲节点的颜色是黑色,没有违反红黑树任何
性质,则不需要调整;但当新插入节点的双亲节点颜色为红色时,就违反了性质三不能有连
在一起的红色节点,此时需要对红黑树分情况来讨论:
约定:cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点。
情况一: cur为红,p为红,g为黑,u存在且为红
解决方式:将 p , u 改为黑,g 改为红,然后把 g 当成 cur,继续向上调整。
情况二: cur为红,p为红,g为黑,u不存在/u存在且为黑
- p为g的左孩子,cur为p的左孩子,则进行右单旋转;相反,
- p、g变色--p变黑,g变红
情况三:cur为红,p为红,g为黑,u不存在/u存在且为黑
- p为g的左孩子,cur为p的右孩子,则针对p做左单旋转;
- p为g的左孩子,cur为p的左孩子,则进行右单旋转;相反,
- p、g变色--p变黑,g变红
这里的cur的也有可能是新增的结点,如果是cur本身就是新增节点那么u结点就是不存在的,否则违反规则 4,也有可能是因为cur下面的结点变黑导致 cur 变红色。
代码:
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
// g(B) g(R)
// p(R) u(R) --> p(B) u(B)
//c(R) c(R)
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上调整
cur = grandfather;
parent = cur->_parent;
}
else //u不存在/u存在且为黑,旋转+变色
{
// g(B) p(R)
// p(R) u(B) --> u(B) g(B)
//c(R) u(B)
if (cur == parent->_left)
{
//右单旋
RotateR(grandfather);
parent->_col = BLACK;
//cur->_col = RED;
grandfather->_col = RED;
}
else
{
// g(B) P(B)
// p(R) u(B) --> c(R) g(R)
// c(R) u(B)
// 左右双旋
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 = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else //u不存在/u存在且为黑,旋转+变色
{
if (cur == parent->_right)
{
//左单旋
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// 右左双旋
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
旋转:
void RotateL(Node* parent)
{
Node* curR = parent->_right;
Node* curRL = curR->_left;
//调整结点,并且修改其父亲结点指针
parent->_right = curRL;
if (curRL)//可能为空
{
curRL->_parent = parent;
}
//在修改子树根节点之前,保存子树根节点的父亲
Node* pparent = parent->_parent;
//修改子树根节点
curR->_left = parent;
parent->_parent = curR;
//子树根节点有可能是整棵树的根节点
if (pparent == nullptr)
{
_root = curR;
_root->_parent = nullptr;
}
else//子树根节点不是整棵树的根节点
{
//还要看子树是它父亲的左孩子还是右孩子
if (pparent->_left == parent)
{
pparent->_left = curR;
}
else
{
pparent->_right = curR;
}
curR->_parent = pparent;
}
}
void RotateR(Node* parent)
{
Node* curL = parent->_left;
Node* curLR = curL->_right;
parent->_left = curLR;
if (curLR)
{
curLR->_parent = parent;
}
Node* pparent = parent->_parent;
curL->_right = parent;
parent->_parent = curL;
if (parent == _root)
{
_root = curL;
_root->_parent = nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = curL;
}
else
{
pparent->_right = curL;
}
curL->_parent = pparent;
}
}
红黑树顺序插入:
红黑树随机插入:
五.红黑树 find
根据二叉搜索树特性去查找:
Node* find(const K key)
{
Node* cur = _root;
while (cur)
{
if (key < cur->_kv.first)
{
cur = cur->_left;
}
else if (key > cur->_kv.first)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
六.析构函数
后续遍历析构树:
~RBTRee()
{
_Destrory(_root);
_root = nullptr;
}
void _Destrory(Node* root)
{
if (root == nullptr)
{
return;
}
_Destrory(root->_left);
_Destrory(root->_right);
delete root;
}
七.红黑树的验证
红黑树的检测分为两步:
- 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
- 检测其是否满足红黑树的性质
其中是否满足搜索树我们只要对其中序遍历是否有序即可。
完整代码:
#pragma once
#include<iostream>
using namespace std;
enum Color
{
RED,
BLACK
};
template<class K,class V>
struct _RBTreeNode
{
_RBTreeNode(pair<K,V> kv)
:_kv(kv),
_col(RED),
_left(nullptr),
_right(nullptr),
_parent(nullptr)
{
}
pair<K, V> _kv;
Color _col;
_RBTreeNode<K, V>* _left;
_RBTreeNode<K, V>* _right;
_RBTreeNode<K, V>* _parent;
};
template<class K,class V>
class RBTRee
{
typedef _RBTreeNode<K, V> Node;
public:
Node* find(const K key)
{
Node* cur = _root;
while (cur)
{
if (key < cur->_kv.first)
{
cur = cur->_left;
}
else if (key > cur->_kv.first)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
bool insert(pair<K, V> kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kv.first < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(kv);
//找到了合适的位置
if (kv.first < parent->_kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
while ( parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
// g(B) g(R)
// p(R) u(R) --> p(B) u(B)
//c(R) c(R)
if ( grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上调整
cur = grandfather;
parent = cur->_parent;
}
else //u不存在/u存在且为黑,旋转+变色
{
// g(B) p(R)
// p(R) u(B) --> u(B) g(B)
//c(R) u(B)
if (cur == parent->_left)
{
//右单旋
RotateR(grandfather);
parent->_col = BLACK;
//cur->_col = RED;
grandfather->_col = RED;
}
else
{
// g(B) P(B)
// p(R) u(B) --> c(R) g(R)
// c(R) u(B)
// 左右双旋
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 = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else //u不存在/u存在且为黑,旋转+变色
{
if (cur == parent->_right)
{
//左单旋
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// 右左双旋
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
void Inorder(vector<K> & v)
{
_inorder(_root,v);
cout << endl;
}
~RBTRee()
{
_Destrory(_root);
_root = nullptr;
}
private:
void _Destrory(Node* root)
{
if (root == nullptr)
{
return;
}
_Destrory(root->_left);
_Destrory(root->_right);
delete root;
}
void _inorder(Node* root, vector<K>& v)
{
if (root == nullptr)
{
return;
}
_inorder(root->_left,v);
v.push_back(root->_kv.first);
_inorder(root->_right,v);
}
void RotateL(Node* parent)
{
Node* curR = parent->_right;
Node* curRL = curR->_left;
//调整结点,并且修改其父亲结点指针
parent->_right = curRL;
if (curRL)//可能为空
{
curRL->_parent = parent;
}
//在修改子树根节点之前,保存子树根节点的父亲
Node* pparent = parent->_parent;
//修改子树根节点
curR->_left = parent;
parent->_parent = curR;
//子树根节点有可能是整棵树的根节点
if (pparent == nullptr)
{
_root = curR;
_root->_parent = nullptr;
}
else//子树根节点不是整棵树的根节点
{
//还要看子树是它父亲的左孩子还是右孩子
if (pparent->_left == parent)
{
pparent->_left = curR;
}
else
{
pparent->_right = curR;
}
curR->_parent = pparent;
}
}
void RotateR(Node* parent)
{
Node* curL = parent->_left;
Node* curLR = curL->_right;
parent->_left = curLR;
if (curLR)
{
curLR->_parent = parent;
}
Node* pparent = parent->_parent;
curL->_right = parent;
parent->_parent = curL;
if (parent == _root)
{
_root = curL;
_root->_parent = nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = curL;
}
else
{
pparent->_right = curL;
}
curL->_parent = pparent;
}
}
Node* _root = nullptr;
};
//传参时benchmark是-1,代表还没有基准值,当走完第一条路径时,
//将第一条路径的黑色节点数作为基准值,后续路径走到null时,就与基准值比较。
//blacknum记录路径上的黑色节点数
bool _isRBTree(Node* root, int blacknum, int benchmark)
{
if (root == nullptr)
{
if (benchmark == -1)
{
benchmark = blacknum;
}
else
{
if (blacknum != benchmark)
{
cout << "black Node !=" << endl;
return false;
}
}
return true;
}
if (root->_col == BLACK)
{
blacknum++;
}
//判断时候出现两个连续的红色结点
if (root->_col == RED && root->_parent && root->_parent->_col == RED)
{
cout << "red connect " << endl;
return false;
}
return _isRBTree(root->_left, blacknum, benchmark) && _isRBTree(root->_right, blacknum, benchmark);
}
main.cpp
#include<vector>
#include<cassert>
#include"RB_Tree.hpp"
int main()
{
RBTRee<int, int> rb;
int i = 100000;
while(i--)
{
int num = rand() + i;
rb.insert(make_pair(num,num));
}
vector<int> v;
rb.Inorder(v);
for (int i = 0; i < v.size() - 1; i++)
{
if (v[i] > v[i + 1])
{
assert(0);
}
}
cout << rb.isRBTree() << endl;
return 0;
}
八. 红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是O(),红黑树不追
求绝对平衡,其只需保证最长路径不超过最短路径的2倍,相对而言,降低了插入和旋转的次数,
所以在经常进行增删的结构中性能比AVL树更优,而且红黑树实现比较简单,所以实际运用中红
黑树更多。