红黑树
一、红黑树
(一)红黑树的概念
红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路 径会比其他路径长出俩倍,因而是接近平衡的。
(二) 红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的,则它的两个孩子结点是黑色的
- 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均 包含相同数目的黑色结点
- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
问:为什么满足上面的性质,红黑树就能保证:其最长路径中节点个数不会超过最短路径节点 个数的两倍?
答:
最短路径:全部为黑色的
最长路径:一黑一红
所以满足最短路径恰好等于最长路径的二倍。
(三)红黑树节点的定义
首先我们定义一个枚举类型,来区分红色和黑色
enum color {
RED,
BLACK
};
思考:默认的节点定义为红色还是黑色?
答:红色,因为黑色一增加,其余所有的节点都要增加一个黑色结点,开销很大。
template<class K, class V>
struct RBTreeNode {
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<K, V> _kv;
color _col;
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_col(RED)
{}
};
二、红黑树的插入
首先找到cur该插入的位置,这里和AVL树的插入是一样的,唯一不一样的就是以前是平衡因子改变,变成了颜色改变,所以就不再介绍。代码如下:
template<class K, class V>
struct RBTree {
public:
typedef RBTreeNode<K, V> Node;
bool Insert(const 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 (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);
if (parent->_kv.first < kv.first)
parent->_right = cur;
else
parent->_left = cur;
cur->_parent = parent;
}
private:
Node* _root;
};
正式进入插入环节:
插入新节点的颜色:红色
1.插入位置父亲的颜色是黑色,不需要处理,插入结束
2.插入位置的父亲颜色是红色,出现了连续的红色节点,需要处理
这里定义爷爷(g)的另外一个结点为叔叔节点,简称uncle/u
情况一:u存在且为红
p/u变黑、g变红(如果g是root,再把g变成黑)=> c变成g,p变成c的父亲(传递上去)
注:
p/u是g的左右都不影响
cur是p的左右也不影响
由于根节点永远是黑色,所以我们在外面定义一下_root->_col = BLACK
代码如下:
while (parent && parent->_col == RED) {
Node* grandfather = parent->_parent;
if (parent == grandfather->_left) {
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED) {
// 情况一:uncle存在且为红
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else {
//情况二:u不存在或者u为黑
}
}
else {
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED) {
// 情况一:uncle存在且为红
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else {
//情况二:u不存在或者u为黑
}
}
}
_root->_col = BLACK;
情况二: uncle不存在,或者uncle为黑的情况下,需要旋转+变色(关键在于画图),旋转代码和AVL树一样不再讲解。
while (parent && parent->_col == RED) {
Node* grandfather = parent->_parent;
if (parent == grandfather->_left) {
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED) {
// 情况一:uncle存在且为红
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else {
//情况二:u不存在或者u为黑
if (parent->_left == cur) {
// g
// p u
// c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else {
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else {
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED) {
// 情况一:uncle存在且为红
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else {
//情况二:u不存在或者u为黑
if (parent->_right == cur) {
// g
// u p
// c
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;
三、红黑树的平衡验证
bool Check(Node* root, int BlackNum, int RefBlackNum) {
if (root == nullptr) {
if (BlackNum != RefBlackNum) {
cout << "黑色个数不相等" << endl;
return false;
}
return true;
}
if (root->_col == BLACK)
BlackNum++;
if (root->_col == RED && root->_parent->_col == RED) {
cout << "出现连续红色节点" << endl;
return false;
}
return Check(root->_left, BlackNum, RefBlackNum)
&& Check(root->_right, BlackNum, RefBlackNum);
}
bool IsBalance() {
if (_root && _root->_col == RED)
return false;
int RefBlackNum = 0;
Node* cur = _root;
while (cur) {
if (cur->_col == BLACK)
RefBlackNum++;
cur = cur->_left;
}
return Check(_root, 0, RefBlackNum);
}
四、代码汇总
#pragma once
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
enum color {
RED,
BLACK
};
template<class K, class V>
struct RBTreeNode {
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<K, V> _kv;
color _col;
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_col(RED)
{}
};
template<class K, class V>
struct RBTree {
public:
typedef RBTreeNode<K, V> Node;
bool Insert(const 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 (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);
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;
if (parent == grandfather->_left) {
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED) {
// 情况一:uncle存在且为红
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else {
//情况二:u不存在或者u为黑
if (parent->_left == cur) {
// g
// p u
// c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else {
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else {
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED) {
// 情况一:uncle存在且为红
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else {
//情况二:u不存在或者u为黑
if (parent->_right == cur) {
// g
// u p
// c
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;
}
}
bool Check(Node* root, int BlackNum, int RefBlackNum) {
if (root == nullptr) {
if (BlackNum != RefBlackNum) {
cout << "黑色个数不相等" << endl;
return false;
}
return true;
}
if (root->_col == BLACK)
BlackNum++;
if (root->_col == RED && root->_parent->_col == RED) {
cout << "出现连续红色节点" << endl;
return false;
}
return Check(root->_left, BlackNum, RefBlackNum)
&& Check(root->_right, BlackNum, RefBlackNum);
}
bool IsBalance() {
if (_root && _root->_col == RED)
return false;
int RefBlackNum = 0;
Node* cur = _root;
while (cur) {
if (cur->_col == BLACK)
RefBlackNum++;
cur = cur->_left;
}
return Check(_root, 0, RefBlackNum);
}
private:
Node* _root = nullptr;
};
void TestRBTree()
{
const int N = 1000000;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; i++)
{
v.push_back(rand() + i);
}
RBTree<int, int> t;
for (auto e : v)
{
t.Insert(make_pair(e, e));
}
cout << t.IsBalance() << endl;
}