前言
在传统二叉搜索树的基础上，我们学习了AVL树，它通过独特的平衡机制，确保了稳定高效的插入、查找和删除操作。然而，由于其频繁的平衡调整，可能使性能收到一定影响。因此，另一种自平衡二叉搜索树——红黑树应运而生。本篇文章，我们将深入探讨红黑树的实现原理，带你解开其简洁而深邃的设计之美。
与AVL树相同，之后的红黑树实现当中，我们会将键值对(pair)作为节点数据域。
注：若无特殊说明，本文所提到的所有“路径”都指根节点到NULL的路径。
一、红黑树介绍
红黑树（Red-Black-Tree）是一种自平衡二叉搜索树，但它并非像AVL树那样“严格平衡”，而是允许一定的不平衡存在，在保证增删查改效率没有太大影响的情况下，显著减少了平衡调整的次数，提升总体效率。
AVL树一般通过节点的“平衡因子”来维持平衡，而红黑树通过给节点“着色”，确保其高效性。
在非空情况下，红黑树的性质（约束条件）如下：
1. 它是一棵二叉搜索树
2. 每一个节点都会被着色，不是黑色就是红色
3. 根节点必须为黑色
4. 对于一个红色节点，它的孩子或为空，或是黑色。也就是说路径上不能有连续红色节点
5. 从根节点到NULL节点的所有路径上，黑色节点的数量都相同
有了以上约束条件，就可确保其没有一条路径长度能够超出其他路径的2倍，从而保证高效操作。
如上图，每一条路径上都有相同数量的黑色节点。
二、红黑树原理详解
那么，红黑树为什么能够控制路径长度呢？
来看一个极端情况：
假设一棵红黑树的一条路径上有n个黑色节点，那么由于其所有路径上的黑色节点数量是相同的，所以其所有路径上都一定有n个黑色节点。对于这棵树，最长的可能路径上的节点就是一黑一红一黑一红（要确保无连续红色节点）......一共有2n个节点；最短的可能路径上的节点是全黑的，一共有n个节点。那么其他可能的路径长度都在n~2n之间。所以说没有一条路径长度能够超出其他路径长度的两倍，也就确保了根节点左右子树的高度比一定在1~2之间。
接下来，我们分析一下红黑树的效率。
设一棵红黑树一共有N个节点，它的最短可能路径的长度为h，由于可能的路径长度都在h~2h之间，那么节点数N就满足 2^{h}-1\leq N\leq 2^{2h}-1 。由此可知，在路径最短情况下，其进行增删查改的时间消耗为O(logN)；路径最长情况下，进行查找的时间消耗为O(2logN)。因此红黑树增删查改的时间复杂度为O(logN)。
红黑树的平衡控制相对AVL树较为抽象，但由于那几点约束条件，控制了最长路径和最短路径之比，间接地使红黑树达到了“近似平衡”，增删查改地时间消耗不会过大，并且相比AVL树，旋转调整次数会更少。
三、红黑树的实现
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)
{
}
};
与AVL树相同，红黑树也采用三叉链表结构，更有利于节点之间的控制访问。
在节点构造当中，我们并没有设置节点的初始颜色，之后在实现节点插入的实现当中，我们会重点讨论初始颜色的问题。
2. 红黑树类型定义及接口声明
我们需要实现的接口如下：
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
RBTree() = default;
RBTree(const RBTree<K, V>& t);
~RBTree();
bool Insert(const pair<K, V>& kv);
Node* Find(const K& key);
void Inorder();
bool IsValidRBTree();
private:
Node* _root = nullptr;
};
3. 红黑树的插入
为了保持红黑树增删查改的高效性，插入操作要保证满足红黑树的性质。
红黑树的插入过程大致如下：
1. 首先按照二叉搜索树的插入规则确定插入节点的位置。
2. 插入新节点，并确定新节点的颜色。
3. 为保持红黑树的性质，需要对原有树结构进行平衡调整。
颜色设置
我们首先来探讨新节点的颜色设置问题。
如果新插入的节点是根节点（树为空），毋庸置疑，为黑色。并且此时整个结构已经满足红黑树性质，插入完成。
如果新插入的节点不是根节点，那么能否设置初始颜色为黑色呢？我们假设新插入的节点为黑色：
不难发现，插入节点4之后，已经不满足红黑树性质：5->2->4->NULL这条路径上有3个黑色节点，而5->7->6->NULL这条路径上有2个黑色节点。实际上，如果插入黑色节点，不管插入到什么位置，该条路径上的黑色节点数都会增加，而其他路径上的黑色节点数不变，此时一定会违反红黑树的约束条件。
那么，我们插入一个红色节点：
此时可以看到，插入之后，整个结构依然满足红黑树的性质。当然，这是因为节点2是黑色节点，此时插入结束。若一个红色节点插入在红色节点的下方，出现连续红色节点，那么也会违反约束条件。
总之，若插入黑色节点，一定违反红黑树规则，而插入红色节点，可能违反红黑树规则。所以我们退而求其次，将新节点（除根节点外）设置为红色。
平衡调整
确定了新节点颜色之后，我们探讨平衡调整的问题。
之前已经提到，我们如果将新节点插入在红色节点的下方，就需要进行平衡调整。有两种场景需要分别讨论。
场景1：仅变色
如上图所示， parent和uncle都是红色，grandfather为黑色，此时插入新节点cur，出现连续红色节点。这种情况下，将parent和uncle变黑，grandfather变红，整个结构就满足了红黑树的性质。
但上图是一种具体情况，如果整棵树是另一棵树的子树，且节点4是红色的，那么变色之后就会再次**出现连续的红色节点（节点2和节点4），此时就需要继续向上调整：将grandfather作为新的cur，然后找到新的parent和uncle，进行变色或做其他调整（之后会讲解），然后再向上检查，直到遇到根节点或者无连续红色节点为止。**
通过观察上图，不难发现：针对需要进行平衡调整的情况，新节点插入之后，parent一定为红，否则无需调整；grandfather一定为黑，否则未插入节点时就已经出现连续红色节点，红黑树原本就有问题。 那么，重要变量就是uncle节点。
总结：当uncle为红时，仅需变色：将parent和uncle变黑，grandfather变红。然后将grandfather作为新的cur，找到新的parent和uncle，继续判断、调整，直到遇到根节点或无连续红色节点。
场景2：旋转+变色
刚才提到uncle是重要变量，那么我们就给出uncle的其他可能情况（不存在或为黑），进而分析各种调整场景。
分类讨论之前，我们首先需要明确需要进行平衡调整的情况下，uncle和cur的关系。
一个节点被标记为cur（确定插入位置之后），仅有两种情况：
1. 它是新增节点；2. 它是场景1向上调整时标记的节点。
当uncle不存在时，cur一定是新增节点。原因：若cur不是新增节点，则其必然是向上调整时标记的节点，那么一定发生了变色，也就是说cur所在的某条路径A上至少有两个黑色节点（包括一个根节点）。而uncle不存在，则从根节点到uncle（NULL）位置的路径上的黑色节点数一定少于路径A，两条路径黑色节点数量不一致，不满足红黑树性质。
当uncle为黑时，cur一定时向上调整时标记的节点。原因：uncle为黑，则从根节点到uncle的路径B上至少有两个黑色节点。如果cur是新增节点，那么从根节点到cur的路径上的黑色节点数一定少于路径B，两条路径黑色节点数量不一致，不满足红黑树性质。
uncle不存在：
这种情况下，如果只是改变parent和grandfather的颜色，并不能解决问题：变色之后路径4->2->1->NULL上有1个黑色节点，而路径4->NULL上没有黑色节点，不满足红黑树性质。
此时就要配合旋转操作来解决问题。根据三个节点的相对位置，需要我们分情况进行单旋或双旋，从而调整树的结构：
单旋+变色：
可以看到，我们以grandfather为旋转点，进行右/左单旋，然后将parent变黑，grandfather变红，整个结构满足红黑树性质，并且该部分的根已经变成黑色，无需继续向上调整，插入结束。
双旋+变色：
双旋完成后，将cur变黑，grandfather变红，整个结构满足红黑树，并且该部分的根已经变成黑色，无需继续向上调整，插入结束。
总结：当uncle不存在时，需要根据实际情况进行旋转+变色。单旋完成后要将parent变黑，grandfather变红；双旋完成后要将cur变黑，grandfather变红。操作结束后，该部分的根成为黑色，不会出现连续红色节点，无需再向上调整。
uncle为黑：
刚才已经提到，uncle为黑时，cur一定是向上调整时标记的节点。所以我们使用抽象图来表示插入状况：
如图所示， a、b、c、d、e分别表示相应黑色节点数量的子树，当a、b的黑色节点数由n-1变为n时，说明发生了变色，使得cur变为红色。此时由于uncle是黑色，如果直接将parent变黑，grandfather变红，那么根节点到a、b、c路径上的黑色节点数与到d、e的路径不相等，不满足红黑树的性质。所以要以grandfather为旋转点，分情况进行旋转再变色。
不难发现，uncle为黑时的旋转、变色逻辑与uncle不存在时完全相同，这里博主就不再一一列举各种旋转情况。总结：当uncle为黑时，需要根据实际情况进行旋转+变色。单旋完成后要将parent变黑，grandfather变红；双旋完成后要将cur变黑，grandfather变红。操作结束后，该部分的根成为黑色，不会出现连续红色节点，无需再向上调整。
注意：平衡调整完成之后，整棵树的根节点可能变为红色。所以平衡调整结束后，一定要将根节点设置为黑色。
红黑树插入的总体过程：
总代码
红黑树插入代码实现：
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->_left;
}
else if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(kv);
cur->_col = RED;
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;
if (parent == grandfather->_left)
{
Node* 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
{
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->_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 RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR) subLR->_parent = parent;
Node* ppNode = parent->_parent;
subL->_right = 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;
}
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL) subRL->_parent = parent;
Node* ppNode = parent->_parent;
subR->_left = 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;
}
}
4. 红黑树的查找
红黑树的查找逻辑与传统二叉搜索树相同，注意按照键查找。
代码如下：
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;
}
5. 中序遍历、拷贝构造和析构
三个函数的实现逻辑与AVL树完全相同。注意拷贝时不要忘记parent指针。
代码如下：
void Inorder()
{
_Inorder(_root);
}
void _Inorder(Node* root)
{
if (root == nullptr) return;
_Inorder(root->_left);
cout << root->_kv.first << ' ' << root->_kv.second << endl;
_Inorder(root->_right);
}
RBTree(const RBTree<K, V>& t)
{
_root = _Copy(t._root);
}
Node* _Copy(Node* root, Node* parent = nullptr)
{
if (root == nullptr) return nullptr;
Node* NewRoot = new Node(root->_kv);
NewRoot->_col = root->_col;
NewRoot->_parent = parent;
NewRoot->_left = _Copy(root->_left, NewRoot);
NewRoot->_right = _Copy(root->_right, NewRoot);
return NewRoot;
}
~RBTree()
{
_Destroy(_root);
}
void _Destroy(Node* root)
{
if (root == nullptr) return;
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
6. 检查红黑树是否合法
判断一棵红黑树是否合法，就要判断它是否满足红黑树的性质。可以从以下几点入手：
1. 检查根节点是否为黑色。
2. 当一个节点为红色时，判断其父亲是否是黑色。
3. 检查各个路径上的黑色节点数是否相等。
对于第三点，可以先遍历一条路径（可以选择走最左路径，避免递归），记录路径上的黑色节点个数，然后再判断其他所有路径上的黑色节点个数是否与之一致。
代码实现：
bool IsValidRBTree()
{
if (_root == nullptr) return true;
if (_root->_col == RED)
{
cout << "根节点为红" << endl;
return false;
}
int refNum = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK) refNum++;
cur = cur->_left;
}
return _Check(_root, 0, refNum);
}
bool _Check(Node* root, int num, const int refNum)
{
if (root == nullptr)
{
if (num != refNum)
{
cout << "黑色节点数量不相等" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "有连续红色节点" << endl;
return false;
}
if (root->_col == BLACK) num++;
return _Check(root->_left, num, refNum) && _Check(root->_right, num, refNum);
}
接下来我们写一段代码，插入一组数据，验证红黑树的合法性：
int main()
{
RBTree<int, int> t;
int a[] = {
4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto& e : a)
{
t.Insert({
e,e });
}
t.Inorder();
cout << t.IsValidRBTree() << endl;
return 0;
}
运行结果：
7. 程序全部代码
红黑树实现全部代码如下：
#include <iostream>
#include <utility>
using namespace std;
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:
RBTree() = default;
RBTree(const RBTree<K, V>& t)
{
_root = _Copy(t._root);
}
~RBTree()
{
_Destroy(_root);
}
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->_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;
if (parent == grandfather->_left)
{
Node* 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
{
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->_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;
}
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;
}
void Inorder()
{
_Inorder(_root);
}
bool IsValidRBTree()
{
if (_root == nullptr) return true;
if (_root->_col == RED)
{
cout << "根节点为红" << endl;
return false;
}
int refNum = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK) refNum++;
cur = cur->_left;
}
return _Check(_root, 0, refNum);
}
private:
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR) subLR->_parent = parent;
Node* ppNode = parent->_parent;
subL->_right = 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;
}
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL) subRL->_parent = parent;
Node* ppNode = parent->_parent;
subR->_left = 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 _Inorder(Node* root)
{
if (root == nullptr) return;
_Inorder(root->_left);
cout << root->_kv.first << ' ' << root->_kv.second << endl;
_Inorder(root->_right);
}
Node* _Copy(Node* root, Node* parent = nullptr)
{
if (root == nullptr) return nullptr;
Node* NewRoot = new Node(root->_kv);
NewRoot->_col = root->_col;
NewRoot->_parent = parent;
NewRoot->_left = _Copy(root->_left, NewRoot);
NewRoot->_right = _Copy(root->_right, NewRoot);
return NewRoot;
}
void _Destroy(Node* root)
{
if (root == nullptr) return;
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
bool _Check(Node* root, int num, const int refNum)
{
if (root == nullptr)
{
if (num != refNum)
{
cout << "黑色节点数量不相等" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "有连续红色节点" << endl;
return false;
}
if (root->_col == BLACK) num++;
return _Check(root->_left, num, refNum) && _Check(root->_right, num, refNum);
}
Node* _root = nullptr;
};
int main()
{
RBTree<int, int> t;
int a[] = {
4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto& e : a)
{
t.Insert({
e,e });
}
t.Inorder();
cout << t.IsValidRBTree() << endl;
return 0;
}
总结
红黑树通过引入节点颜色和一系列平衡规则，在保持高效查询性能的同时，优化了插入和删除操作的复杂度。与AVL树相比，红黑树对平衡的要求较为宽松，避免了频繁的旋转调整，从而提升了动态操作的效率。尽管红黑树的结构较为复杂，但它通过颜色标记、旋转操作以及路径黑色节点数量的控制，成功实现了查找、插入和删除操作的平衡。在实际应用中，红黑树被广泛用于操作系统、数据库等领域，发挥着其重要的作用。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤
