【C++】红黑树

本篇可以先了解二叉搜索树和AVL树

二叉搜索树、AVL树

---

1.红黑树的概念

红黑树：是一种二叉搜索树，但在每个节点上增加了一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

2.红黑树的性质

1. 每个结点不是红色就是黑色。、
2. 根结点是黑色的。
3. 如果一个结点是红色的，则它的两个孩子结点是黑色的。
4. 对于每个结点，从该结点到其所有后代结点的简单路径上，均包含相同数目的黑色结点。
5. 每个叶子结点都是黑色的（此处的叶子结点指的是空结点）。

总结一下：

a、根结点是黑色的。b、没有连续的红结点。c、每条路径都有相同数量的黑结点。

为什么满足上面的性质，红黑树就能保证：其最长路径中结点个数不会超过最短路径结点个数的两倍?

最短路径：结点全黑     最长路径：结点为一黑一红

所以，最长路径中结点个数最多是最短路径结点个数的两倍。

时间复杂度：

最短路径：log_2 N

最长路径：2 log_2 N

也就是说理论情况下，红黑树的效率比AVL树的效率略差，但是实际上，由于现在硬件的运算速度非常快，他们之间基本上已经没有差异了，因为常规数据集中log_2 N足够小，2log_2 N差异不大。

比如查找10亿个数，AVL树最多查找30次，红黑树最多查找60次。30次和60次对于现在的硬件基本是一样的。

但是插入删除同样结点，红黑树比AVL树旋转更少，因为AVL树更严格的平衡其实是通过多旋转达到的，所以实际上红黑树得到了更广泛的引用，其次红黑树实现上更容易控制。

3.红黑树节点的定义

enum Colour
{
BLACK,
RED,
};
template<class K,class V>
struct RBTreeNode
{
RBTreeNode* _left;
RBTreeNode* _right;
RBTreeNode* _parent;
pair<K, V> _kv;

Colour _col;
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_col(RED)
{}
};

插入新节点，新节点的颜色默认为红色还是黑色呢？

红色，如果为黑色，违反了规则4，如果为红色，违反了规则3。相对来说，规则4的影响较规则3的影响难处理，所以默认为红色。

4.红黑树的插入

红黑树的插入主要看叔叔

• 情况一：cur为红，p为红，u存在且为红（变色）

1. 如果g是根，把g再变黑，结束。
2. 如果g不是根，是一颗子树，再看g父亲的颜色：

• a、如果g父亲的颜色为黑，结束。
• b、如果g父亲的颜色为红，把g当作cur继续往上处理。

注意：

cur可能为新增，也可能是下面子树的祖先，原来为黑，变色处理为红色。处理是一样的。

• 情况二：cur为红，p为红，g为黑，u不存在/u存在且为黑（单旋+变色）

u不存在

如果u不存在，则cur一定为新插入的结点，因为如果cur不是新插入的结点，则cur和p一定有一个结点颜色是黑色的，就不满足性质4：每条路径黑色结点个数相同。

u存在且为黑

如果u存在且为黑，那么cur节点原来的颜色一定是黑色的，现在看到其是红色的原因是因为，cur的子树经过了变色处理，将cur调整为了红色。

注意：

p为g的左孩子，cur为p的左孩子，则进行右单旋。p为g的右孩子，cur为p的右孩子，则进行左单旋。

• 情况三：cur为红，p为红，g为黑，u不存在/存在且为黑（双旋+变色）

u不存在

u存在且为黑

注意：

p为g的左孩子，cur为p的右孩子，则先进行左旋，转换为情况二，再进行右旋。p为g的右孩子，则先进行右旋，转换为情况二，再进行左旋。

5.红黑树的验证（了解）

红黑树的验证分为两步：

1. 检测其是否为二叉搜索树（中序遍历是否有序）。
2. 检测其是否满足红黑树的性质。

6.完整代码及验证

RBTree.hpp:

#pragma once
#include<iostream>
using namespace std;

enum Colour
{
BLACK,
RED,
};
template<class K,class V>
struct RBTreeNode
{
RBTreeNode* _left;
RBTreeNode* _right;
RBTreeNode* _parent;
pair<K, V> _kv;

Colour _col;
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;
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->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
//新增节点为红色
cur->_col = RED;

while (parent && parent->_col == RED)
{
//红黑树的调节关键看叔叔
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//情况一：uncle存在且为红
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else
{
//情况三：单旋变为情况二
if (cur == parent->_right)
{
RotateL(parent);
swap(parent, cur);
}
//情况二：有可能为情况三变化而来
RotateR(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
break;
}
}
else
{
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->_left)
{
RotateR(parent);
swap(parent, cur);
}
RotateL(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
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* pparent = parent->_parent;
parent->_parent = subR;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
{
pparent->_right = subR;
}
subR->_parent = pparent;
}
}
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
subL->_right = parent;
Node* pparent = parent->_parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
subL->_parent = pparent;
}
}
//验证是否满足二叉搜索树
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << " " << root->_kv.second;
cout << endl;
_InOrder(root->_right);
}
void InOrder()
{
_InOrder(_root);
}
//验证是否满足红黑树
bool _IsValidRBTree(Node* root, size_t k, const size_t blackCount)
{
//走到null之后，判断k和black是否相等
if (nullptr == root)
{
if (k != blackCount)
{
cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
return false;
}
return true;
}
// 统计黑色节点的个数
if (BLACK == root->_col)
k++;
// 检测当前节点与其双亲是否都为红色
Node* parent = root->_parent;
if (parent && RED == parent->_col && RED == root->_col)
{
cout << "违反性质三：没有连在一起的红色节点" << endl;
return false;
}
return _IsValidRBTree(root->_left, k, blackCount) &&
_IsValidRBTree(root->_right, k, blackCount);
}
bool IsValidRBTree()
{
Node* root = _root;
// 空树也是红黑树
if (nullptr == root)
return true;
// 检测根节点是否满足情况
if (BLACK != root->_col)
{
cout << "违反红黑树性质二：根节点必须为黑色" << endl;
return false;
}
// 获取任意一条路径中黑色节点的个数
size_t blackCount = 0;
Node* cur = root;
while (cur)
{
if (BLACK == cur->_col)
blackCount++;
cur = cur->_left;
}
// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
size_t k = 0;
return _IsValidRBTree(root, k, blackCount);
}

private:
Node* _root = nullptr;
};
void TestRBTree()
{
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.IsValidRBTree() << endl;
cout << endl;

int b[] = { 16,3,7,11,9,26,18,14,15 };
RBTree<int, int> t2;
for (auto e : b)
{
t2.Insert(make_pair(e, e));
}
t2.InOrder();
cout << t2.IsValidRBTree() << endl;
}

RBTest.cpp:

#define _CRT_SECURE_NO_WARNINGS 
#include"RBTree.hpp"

int main()
{
TestRBTree();
return 0;
}

运行结果：

7.红黑树与AVL树的比较

性能测试：

void TestRB_AVLTree()
{
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());
}
RBTree<int, int> rbtree;
size_t begin1 = clock();
for (auto e : v)
{
rbtree.Insert(make_pair(e, e));
}
size_t end1 = clock();
AVLTree<int, int> avltree;
size_t begin2 = clock();
for (auto e : v)
{
avltree.Insert(make_pair(e, e));
}
size_t end2 = clock();
cout << "RBTree" << end1 - begin1 << endl;
cout << "AVLTree" << end2 - begin2 << endl;
}

运行结果：

红黑树和 AVL 树都是高效的平衡二叉树，增删改查的时间复杂度都是 O($log_2 N$) ，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2 倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL 树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

8.红黑树的应用

1. C++STL库-map/multimap set/multiset
2. java库
3. linux内核
4. 其他一些库

关于红黑树的查找操作和二叉搜索树的查找相同，红黑树的删除操作不这里不做解释。

原文地址：https://blog.csdn.net/2202_75924820/article/details/142960329

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！