目录
1、红黑树的概念
1.1 红黑树的定义
红黑树是一种自平衡的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是红色或黑色。通过对从根节点到叶子节点的路径上的节点颜色进行约束，红黑树确保没有一条路径会比其他路径长出两倍，因此它是近似平衡的。
1.2 红黑树的规则
1. 每个节点不是红色就是黑色。
2. 根节点是黑色的。
3. 红色节点的子节点必须是黑色的，即任意一条路径不能有连续的红色结点。
4. 对于任意一个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点。
从根节点开始，有9条路径。
补充说明：在《算法导论》等书籍中，通常会补充一条规则，即每个叶子节点（NIL节点）都是黑色的。这里的叶子节点并不是传统意义上的叶子节点，而是指空节点（NIL节点），有时也称为外部节点。NIL节点的引入是为了方便准确地标识出所有路径。
1.3 为什么没有一条路径会比其他路径长出两倍
根据规则4，从根节点到任意NIL节点的路径上的黑色节点数量是相同的。假设最短路径上的黑色节点数量为bh（black height），那么最短路径的长度就是bh（即全黑的路径）。
根据规则2和规则3，根节点是黑色节点，路径中不能有连续的红色节点。因此，最长路径的节点颜色分布只能是“黑-红-黑-红...”交替出现。假设最短路径的长度为bh，那么最长路径的长度最多为2*bh（即一黑一红交替的路径）。
最短路径和最长路径是极端情况，可能一棵树中都没有。假设任意一条从根到NULL结点路径的长度为x，那么bh<=x<=2*bh。
1.4 红黑树的性能
1. 红黑树的高度近似为 logN。
2. 红黑树的查找、插入、删除等操作的时间复杂度均为 O(logN)。
3. 虽然它的平衡性不如AVL树严格，但在实际应用中，红黑树的旋转次数较少，性能表现良好。红黑树和AVL树的时间复杂度都是 O(logN)，适用于需要高效查找、插入、删除操作的场景。
2、红黑树的实现
2.1 红黑树的结构
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 _col;
RBTreeNode(const pair<K,V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
{ }
};
template<class K,class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
//...
private:
Node* _root = nullptr;
};2.2 红黑树的插入
2.2.1 红黑树插入一个值的大概过程
1. 按二叉搜索树的规则插入一个值。
2. 如果是向空树中插入，新节点应为黑色节点(即根节点，规则2，根节点是黑色的)。
如果是向非空树中插入，新节点必须是红色节点，因为插入黑色新节点会破坏规则4，而规则4较难维护。
3. 在非空树中插入后，新节点必须是红色节点。如果其父节点是黑色的，则未违反任何规则，插入操作结束。
4. 在非空树中插入后，新节点必须是红色节点。如果其父节点是红色的，则违反了规则3。
若新节点cur为红色，其父节点parent也为红色，则祖父节点grandfather必为黑色，因为插入就是红黑树，不会出现连续的红节点。这三个节点的颜色已确定，关键在于考察叔叔节点uncle的情况。
说明：下图中假设我们把新增结点标识为c(cur)，c的父亲标识为p(parent)，p的父亲标识为 g(grandfather)，p的兄弟标识为u(uncle)。
2.2.2 情况1：变色
叔叔存在且为红。
p和u变黑，g变红，
再c = g，c如果是根，c变黑，操作结束，如果是局部子树的根，继续向上判断。
如果p是g的右，操作相同。
注意：无所谓c是p的左或右，因为是c的p,g,u变色。
2.2.3 情况2：单旋+变色
叔叔存在且为黑，或叔叔不存在。bh(black height)为路径上黑色节点的数量。
对g进行右旋，将p(根)变黑，g变红。 对g进行左旋，其他操作相同。
旋转后，子树根节点是黑色，且满足规则3，4，操作结束。
2.2.4 情况3：双旋+变色
叔叔存在且为黑，或叔叔不存在。bh(black height)为路径上黑色节点的数量。
先对p进行左旋，再对g进行右旋，将c(根)变黑，g变红。 先对p进行右旋，再对g进行左旋，相同操作相同。
旋转后，子树根节点是黑色，且满足规则3，4，操作结束。
2.2.5 红黑树插入的代码实现
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 (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (kv.first < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
if (kv.first > parent->_kv.first)
parent->_right = cur;
else
parent->_left = cur;
cur->_parent = parent;
while (parent&&parent->_col == RED)
{
Node* grandfather = parent->_parent;
Node* uncle;
if (parent == grandfather->_left)
{
// g
// p u
uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
// g
// u p
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)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
if (parent == nullptr)
_root->_col = BLACK;
return true;
}2.3 红黑树的查找
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key > cur->_kv.first)
cur = cur->_right;
else if (key < cur->_kv.first)
cur = cur->_left;
else
return cur;
}
return nullptr;
}2.4 红黑树的验证
1. 规则1通过枚举颜色类型来天然保证颜色要么是黑色要么是红色。
2. 规则2只需直接检查根节点即可满足条件。
3. 规则3采用前序遍历进行检查，当遇到红色节点时，检查其孩子节点不太方便，因为孩子节点有两个且不一定都存在。相反，遇到红色节点，检查父节点的颜色更方便。
4. 规则4使用前序遍历，在遍历过程中通过形参记录从根节点到当前节点的黑色节点数量（blackNum）。每遇到黑色节点，++blackNum。当遍历到空节点时，就计算出了一条路径上的黑色节点数量。然后，可以将任意一条路径的黑色节点数量作为参考值，依次进行比较即可。
bool IsBalance()
{
if (_root->_col != BLACK)
return false;
Node* cur = _root;
int refNum = 0;
while (cur)
{
if (cur->_col == BLACK)
++refNum;
cur = cur->_left;
}
return _IsBalance(_root, 0, refNum);
}
bool _IsBalance(Node* root, int blackNum, const int refNum)
{
if (root == nullptr)
{
if (blackNum != refNum)
return false;
else
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
return false;
if (root->_col == BLACK)
++blackNum;
return _IsBalance(root->_left, blackNum, refNum) &&
_IsBalance(root->_right, blackNum, refNum);
}2.5 红黑树的删除
红黑树的删除本章节不做讲解，有兴趣的同学可参考：《算法导论》或者《STL源码剖析》中讲解。
2.6 红黑树的代码实现
2.6.1 RBTree
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
namespace Lzc
{
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 _col;
RBTreeNode(const pair<K,V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_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 (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (kv.first < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
if (kv.first > parent->_kv.first)
parent->_right = cur;
else
parent->_left = cur;
cur->_parent = parent;
while (parent&&parent->_col == RED)
{
Node* grandfather = parent->_parent;
Node* uncle;
if (parent == grandfather->_left)
{
// g
// p u
uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
// g
// u p
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)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
if (parent == nullptr)
_root->_col = BLACK;
return true;
}
void RotateR(Node* parent)
{
Node* pParent = parent->_parent;
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
parent->_parent = subL;
subL->_parent = pParent;
if (pParent == nullptr) // 当pParent == nullptr时,_root == parent
{
_root = subL;
}
else
{
if (pParent->_left == parent)
pParent->_left = subL;
else
pParent->_right = subL;
}
}
void RotateL(Node* parent)
{
Node* pParent = parent->_parent;
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
parent->_parent = subR;
subR->_parent = pParent;
if (pParent == nullptr)
_root = subR;
else
{
if (pParent->_left == parent)
pParent->_left = subR;
else
pParent->_right = subR;
}
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key > cur->_kv.first)
cur = cur->_right;
else if (key < cur->_kv.first)
cur = cur->_left;
else
return cur;
}
return nullptr;
}
void InOrder()
{
_InOrder(_root);
}
int Height()
{
return _Height(_root);
}
int Size()
{
return _Size(_root);
}
bool IsBalance()
{
if (_root->_col != BLACK)
return false;
Node* cur = _root;
int refNum = 0;
while (cur)
{
if (cur->_col == BLACK)
++refNum;
cur = cur->_left;
}
return _IsBalance(_root, 0, refNum);
}
~RBTree()
{
Destroy(_root);
_root = nullptr;
}
void Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int LeftHeight = _Height(root->_left);
int RightHeight = _Height(root->_right);
return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;
}
int _Size(Node* root)
{
if (root == nullptr)
return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}
bool _IsBalance(Node* root, int blackNum, const int refNum)
{
if (root == nullptr)
{
if (blackNum != refNum)
return false;
else
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
return false;
if (root->_col == BLACK)
++blackNum;
return _IsBalance(root->_left, blackNum, refNum) && _IsBalance(root->_right, blackNum, refNum);
}
Node* _root = nullptr;
};
}2.6.2 Test.cpp
#include"RBTree.h"
#include<vector>
#include<time.h>
namespace Lzc
{
void TestRBTree1() {
RBTree<int, int> rbt;
// 常规的测试用例
int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
// 特殊的带有双旋场景的测试用例
// int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a) {
rbt.Insert({ e, e });
}
rbt.InOrder();
cout << rbt.IsBalance() << endl;
}
// 插入一堆随机值，测试平衡，顺便测试一下高度和性能等
void TestRBTree2() {
const int N = 100000;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; i++) {
v.push_back(rand() + i);
}
// 测试插入性能
size_t begin2 = clock();
RBTree<int, int> rbt;
for (auto e : v) {
rbt.Insert(make_pair(e, e));
}
size_t end2 = clock();
cout << "Insert:" << end2 - begin2 << endl;
// 测试平衡性、高度和大小
cout << "IsBalance:" << rbt.IsBalance() << endl;
cout << "Height:" << rbt.Height() << endl;
cout << "Size:" << rbt.Size() << endl;
// 测试查找性能
size_t begin1 = clock();
// 查找已存在的值
/*for (auto e : v) {
rbt.Find(e);
}*/
// 查找随机值
for (size_t i = 0; i < N; i++) {
rbt.Find((rand() + i));
}
size_t end1 = clock();
cout << "Find:" << end1 - begin1 << endl;
}
}
int main()
{
Lzc::TestRBTree1();
//Lzc::TestRBTree2();
return 0;
}