1.红黑树的概念
红黑树首先是一棵二叉搜索树，但在每个结点包含一个颜色信息（Red or Black）。通过对任何一条根到叶子的路径上各个结点着色的限制，红黑树可以确保根到各个叶子结点的最长路径最多是最短路径的两倍——近似平衡。相较于AVL树虽然达不到完全平衡，如搜索10亿个数据，AVL数需搜索30次（2^30），而红黑树可能最多需要搜索60次（这对于CPU而言没有区别），但是红黑树却可以省去大量的旋转操作的代价。
为什么红黑树可以保证最长路径不超过最短路径的两倍基于红黑树的性质：
1. 每个结点非黑即红
2. 根节点为黑色
3. 如果一个结点的是红色的，那么他的左右孩子结点是黑色的。
4. 对于每个结点，从该结点到其所有后代叶子结点的简单路径上，均包含相同数目的黑色结点。
5. 所有的叶子结点都是黑色（此处叶子节点指的是NIL）
🚩总结上述的性质：
1. 路径中没有连续的红色结点
2. 最短路径：全部由黑色结点构成。最长路径：黑红间隔，黑红结点数量相等。
3. 叶子结点是黑色的NIL（空）结点
假设每条路径黑色结点数为N，那么最长路径为2*N，最短路径则是N，显然最长路径不会超过最短路径的两倍，而且一棵全黑的红黑树是满二叉树。
2.红黑树结点定义
结点定义为三叉链，一个结点可以指向左右子树以及父结点，存储的数据类型为pair存放键值对，结点还需带有颜色信息：
enum Colour
{
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;
Colour _colour;
RBTreeNode(const pair<K,V>& kv):
_left(nullptr),
_right(nullptr),
_parent(nullptr),
_kv(kv),
_colour(RED)
{}
};
3.红黑树结构
里面只包含一个根节点的成员变量:
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
private:
Node* _root = nullptr;
};
4.红黑树的插入操作
在插入结点时与二叉搜索树的规则一致（比当前结点小往左，比前结点大往右，或者相反，这取决于你想要的中序遍历是升序还是降序），后面再进行调整。
?新插入结点的颜色应该是什么？
- 如果每次新插入的结点颜色为黑色，则会破坏上述红黑树规则4（每条路径黑色结点的数量保持一致），如果再去调整每条路径的黑色结点数量，无疑将是个巨大的工程。
- 如果每次新插入的结点是红色，首先路径上黑色结点数量保持不变，如果父结点是黑色便插入成功，但是如果父结点也为红色则破坏规则3（不能出现连续红结点），于是只需往上调整该路径的红黑结点的颜色即可，工程量也并不大。
所以，插入新结点的颜色选择 <font color="#dd0000">红 </font>色。
?调整规则
如果插入结点的父结点是黑色的那么插入成功，如果父结点是红色的则需要调整。
标记：cur——新插入结点，p——父结点，g——祖父节点，u——叔叔结点
🚩注意：由于插入新结点前原本是一棵红黑树，此时父结点为红色（固定），那么祖父结点一定存在且为黑色（固定）（规定根节点是黑的）。这里谈论父结点是祖父结点的左孩子情形，右孩子情形可自己推演。
所以变数在叔叔结点。
情形和规则如下：
叔叔结点 u 存在且为红
为避免连续红色，将父结点p改为黑色，为了保证祖父这条路径的黑色结点数不变，所以祖父节点g改为红色，同时叔叔结点u改为黑色
现在可以保证新增结点后路径的黑色结点的数量保持不变，但还没有结束，此时需要围绕祖父结点情况展开讨论：
- 祖父结点g为根结点，那么将祖父改为黑色即可，此时相当于每条路径的黑色结点都增加了1个，插入操作完成。
- 祖父结点g不是根结点，那么此时我们要将祖父结点当成新增的红色结点cur，如果他的父结点为黑色，插入完成。如果父结点仍然为红色，那么又需要根据它的叔叔结点的情况进行不同的向上调整操作。
因此总结抽象图如下：
- 🚩注意：cur是parent的左孩子还是右孩子情况是一样的，因为只做变色处理，不用旋转。
叔叔结点 u 存在且为黑
?注意：这种情况的cur一定为调整上来的结点，而不是新增结点。如果是新增结点，那么g的左右子树的黑色结点数目不等，与红黑树原则相悖。
- 当cur为parent的左孩子（直线）——右单旋,p变黑色，g变红色
- 当cur为parent的右孩子（折线）——左右双旋，cur变黑色，g变红色
可以先进行左单旋，然后交换cur和p，把折线变为直线，最后都执行直线的情况。
- 🚩注意：假设a的黑色结点为
x，b、c的黑色结点为x，d、e的黑色节点为x-1。 调整后子树根结点下所有路径的黑色结点数量都为x，符合红黑树规则。此时由于子树根结点为黑色，不用再往上更新。发现整个旋转过程与u无关。
叔叔结点 u 不存在
?注意：这种情况的cur一定是新增结点，而不可能是下面的子树更新上来的变红结点。因为g的右侧没有黑结点，所以cur的下面不可能再有黑结点了。
- 当cur为parent的左孩子（直线）——右单旋,p变黑色，g变红色
- 当cur为parent的右孩子（折线）——左右双旋，cur变黑色，g变红色
当然左单旋后先交换cur和p，把折线变为直线，最后可都执行直线的情况。
上述即为p是g左孩子的变色及旋转规则，如果p为g的右孩子时做镜像处理。
代码如下：
- 旋转代码
private:
void RotateL(Node* parent)
{
Node* Pparent = parent->_parent;
Node* subR = parent->_right;
Node* subRL = subR->_left;
subR->_left = parent;
parent->_parent = subR;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_parent = Pparent;
if (Pparent)
{
if (Pparent->_right == parent)
{
Pparent->_right = subR;
}
else
{
Pparent->_left = subR;
}
}
else
{
_root = subR;
}
}
void RotateR( Node* parent)
{
Node* Pparent = parent->_parent;
Node* subL = parent->_left;
Node* subLR = subL->_right;
// parent 与 subL的关系建立
subL->_right = parent;
parent->_parent = subL;
// parent 与 subLR 的关系建立
if (subLR != nullptr)
{
subLR->_parent = parent;
}
parent->_left = subLR;
// Pparent 与 subL的关系建立
if (Pparent != nullptr)
{
subL->_parent = Pparent;
if (Pparent->_left == parent)
{
Pparent->_left = subL;
}
else
{
Pparent->_right = subL;
}
}
else
{
_root = subL;
subL->_parent = nullptr;
}
}
- 插入结点代码
public:
pair<Node*, bool> Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_colour = BLACK;
return make_pair(_root, true);
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
if (cur->_kv.first > kv.first)
{
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
cur = cur->_right;
}
else
{
return make_pair(cur, false);
}
}
Node* newnode = new Node(kv);
newnode->_parent = parent;
if (parent->_kv.first > kv.first)
{
parent->_left = newnode;
}
else
{
parent->_right = newnode;
}
cur = newnode;
//开始调整
while (parent && parent->_colour == RED)//最差情况，处理到根节点为止
{
Node* grandfather = parent->_parent;
Node* uncle = nullptr;
if (grandfather->_right == parent) //parent为grandfather右树
{
uncle = grandfather->_left;
if (uncle && uncle->_colour == RED)//情况1，仅需变色，且考虑往上追溯
{
parent->_colour = BLACK;
uncle->_colour = BLACK;
grandfather->_colour = RED;
//继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else //情况2+3 uncle为黑或者不存在，需要旋转+变色
{
//这里不会对uncle进行旋转或是变色处理，我们只关心是折线还是直线情况。
if (cur == parent->_left)//折线情况
{
//对parent做右单旋
RotateR(parent);
swap(cur, parent);
}
//统一处理为直线情况
RotateL(grandfather);
parent->_colour = BLACK;//parent（当前子树的根节点）变为黑色
grandfather->_colour = RED;//grandfather变为红色，以保证路径的黑色结点数量不变
//无需再往上调整了，下次的while会因为parent为黑直接结束循环，不用在此break
}
}
else //parent为grandfather左树
{
uncle = grandfather->_right;
if(uncle && uncle->_colour==RED)//情况1，仅需变色，且考虑往上追溯
{
parent->_colour = BLACK;
uncle->_colour = BLACK;
grandfather->_colour = RED;
//继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else //情况2+3 uncle为黑或者不存在，需要旋转+变色
{
//这里不会对uncle进行旋转或是变色处理，我们只关心是折线还是直线情况。
if (cur == parent->_right)
{
//对parent做左单旋
RotateL(parent);
swap(cur, parent);
}
//统一处理为直线情况
RotateR(grandfather);
parent->_colour = BLACK;
grandfather->_colour = RED;
//无需再往上调整了，下次的while会因为parent为黑直接结束循环，不用在此break
}
}
}//while
_root->_colour = BLACK;//如果grandfather为根节点，那么让其变黑色
return make_pair(newnode, true);
}
5.红黑树的验证
遍历
首先检查我们自己写的红黑树满足基本二叉搜索树的性质（中序遍历为升序）
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
public:
void InOrder()
{
_InOrder(_root);
}
平衡性
检查根节点为黑，每条路径的黑色结点数量是一致的，且不能存在连续的红色结点：
public:
//平衡性
bool isBalance()
{
if (_root == nullptr)
{
return true;
}
if (_root->_colour == RED)
{
return false;
}
//计算一条路径的黑节点数量，并以此为基准
int blacknums = 0;
Node* cur = _root;
while (cur)
{
if(cur->_colour==BLACK)
blacknums++;
cur = cur->_left;
}
int count = 0;
return _isBalance(_root, blacknums, count);
}
private:
bool _isBalance(Node* const& root, int blacknums, int count)
{
if (root == nullptr)
{
if (count != blacknums)
{
cout << "黑节点数量不一致" << endl;
return false;
}
return true;
}
//检查是否存在连续的红节点
if (root->_colour == RED && root->_parent->_colour == RED)
{
cout << "存在连续红结点" << endl;
return false;
}
if (root->_colour == BLACK)
{
count++;
}
return _isBalance(root->_left, blacknums, count) && _isBalance(root->_right, blacknums, count);
}
这里我们试一下代码是否正确：
#include "RBTree.h"
void testRBTree()
{
RBTree< int, int > t;
int n = 10000;
srand(time(nullptr));
for (int i=0;i<n;++i)
{
int e = rand();//随机插入10000个值
t.Insert(make_pair(e, e));
}
//t.InOrder();
cout << "是否为红黑树：" << t.isBalance() << endl;
}
int main()
{
testRBTree();
return 0;
}
6.红黑树的删除
红黑树的删除方法可观看视频红黑树删除，下面我对思路做出整理，并写出代码。
基于二叉搜索树的删除，我们知道删除一个结点分三种情况
- 当删除结点的左右子树都为空，可直接删除；
- 当删除结点的左右子树有一者为空，那么需要将删除结点的子树连接到删除结点的父结点
- 如果删除结点的左右子树都不为空，那么要找到替换删除结点。
所以最终待删除结点只可能是度<=1的结点
为了在删除结点后，仍能保持红黑树的性质，我们还需要考虑调整的情况：
我们将待删除结点标记为 N
情形1： N 为红色结点
N 为红色结点必为叶子节点，不存在其他情况。
解释：红黑树中的红结点的度为只能为0或者2（如果度为1，因为红结点不能连续，那么该红节点以下的路径的黑结点数量必不相等）。
操作：删除红色叶子结点不会影响该条路径的黑色结点数量，直接删除即可，无需往上调整，删除结束。
情形2：N是度为1的黑色结点
N的一侧为空，另一侧孩子M必为红色叶子结点。
解释：如果M为黑色，则N下两条路径的黑色结点数量将不同。
操作：将N删掉，M顶替到N的位置，并将M变为黑色，不会违反红黑树性质，删除结束。
情形3：N是度为0的黑色结点
这种情形是最复杂的，因为随着N的删除，导致其上祖先的下属路径的黑色结点数量发生变化，需要按情况向上做平衡处理（修复），修复完成后再删除，这里的修复情况又将分为4种。
我们将N的父结点记为P，N的兄弟结点记为B
🚩注意：我们只讨论N结点P的左孩子的情况（右孩子则是镜像处理）
4种情况如下：
情况3.a 黑兄弟，远红侄
（N为P左孩子，那么远红侄是B的右孩子。如果N为P的右孩子，那远红侄是B的左孩子，这里注意区分，下面还有近红侄就是离N更近的侄子结点，不再赘述。）
这种情况优先级最高：只要远侄子是红色即可，近侄子为红或者不存在都无需在意，都一律按照这种情况进行处理。
操作：左旋父，祖染父色，父叔黑
见图（P的颜色为白表明其可黑可红，不去在意）
祖结点的颜色没变过，不会出现连续红的情况，同时祖结点左右的黑色结点数量也保持不变，红黑树性质没有破坏，修复完成！
情况3.b 黑兄弟 近红侄
当远侄子不存在，且近侄子存在的时候（注意近红侄此时不可能为黑，也不会出现远值黑近值红情况，否则B左右的黑结点数量不一致），按照这种情况处理。
🚩该情况不能直接修复，而是通过处理转换为情况3.a
操作：右旋兄（注意旋后身份转换），兄弟染黑，远侄子染红，回到情况3.a
情况3.c 黑兄弟 双黑侄
两个侄子为黑结点或者NIL。
操作：兄弟染红，同时考察父结点P：
- 1）
P为根结点或红结点，P染黑后修复结束（P树的黑色结点高度没改变） - 1）
P为黑色结点且P为非根结点，那么根据这个父结点的兄弟重新判断是属于哪一种情况，直到修复结束。（P树的黑色结点高度-1，需要假定P为删除结点，从P的视角向上调整）
情况3.d 红兄弟
该情况也是无法自己修复，需要转换成其他的形态。
操作：左旋父，父染红、祖染黑，变成前三种情况
🚩注意：旋转后，N会有一个新的兄弟，且必为黑色结点，那么就会回到上面的三种修复情况。父祖换色保证祖父下的黑结点高度不变。
完整删除代码如下：
public:
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
//实际待删除结点
Node* delPos = nullptr;
Node* delParentPos = nullptr;
//寻找待删除结点
while (cur)
{
if (cur->_kv.first > key)//往左找
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < key)//往右找
{
parent = cur;
cur = cur->_right;
}
else//找到删除结点
{
if (cur->_left == nullptr)//左为空，右未必为空
{
if (cur == _root)
{
_root = _root->_right;
if (_root)
{
_root->_parent = nullptr;
_root->_colour = BLACK;//根节点注意时刻保持黑色
}
delete cur;
return true;
}
else
{
delPos = cur;
delParentPos = parent;
}
}
else if (cur->_right == nullptr)//左必定不为空
{
if (cur == _root)
{
_root = _root->_left;
_root->_parent = nullptr;
_root->_colour = BLACK;
delete cur;
return true;
}
else
{
delParentPos = parent;
delPos = cur;
}
}
else //cur左右均不为空 需找替换结点
{
Node* minR = cur->_right;
Node* minRParent = cur;
while (minR->_left)
{
minRParent = minR;
minR = minR->_left;
}
//替换
cur->_kv = minR->_kv;
delPos = minR;
delParentPos = minRParent;
}
break;//进行红黑树调整和实际删除
}
}
if (delPos == nullptr)//没有找到删除结点
{
return false;
}
//由于红黑树会向上调整，所以需要备份实际删除的结点
cur = delPos;
parent = delParentPos;
//红黑树调整
//当cur为红结点直接删即可，这里只需考虑cur为黑的情况
if(cur->_colour==BLACK)
{
//cur的度为1 孩子结点必为红色
if (cur->_left)
{
cur->_left->_colour = BLACK;
}
else if (cur->_right)
{
cur->_right->_colour = BLACK;
}
else//cur为叶子结点
{
while (cur != _root)
{
if (cur == parent->_left)//待删除结点是父结点的左孩子
{
Node* brother = parent->_right;
//情况3.a 黑兄弟远红侄
if (brother->_colour == BLACK && brother ->_right && brother->_right->_colour == RED)
{
RotateL(parent);//左旋父
brother->_colour = parent->_colour;//祖染父色
parent->_colour = BLACK;//父叔黑
brother->_right->_colour = BLACK;
//此情况完毕后，结束修复
break;
}
//情况3.b 黑兄弟近红侄
else if (brother->_colour == BLACK &&brother ->_left &&brother->_left->_colour == RED)
{
brother->_colour = RED;//兄弟和侄子的颜色交换
brother->_left->_colour = BLACK;
RotateR(brother);//右旋兄
}
//情况3.c 黑兄弟双黑侄
else if (brother->_colour == BLACK
&&( brother->_left == nullptr || brother->_left->_colour==BLACK)
&&( brother->_right == nullptr|| brother->_right->_colour==BLACK))
{
brother->_colour = RED;
if (parent == _root || parent->_colour == RED)
{
parent->_colour = BLACK;
break;
}
//向上调整
cur=parent;
parent = cur->_parent;
}
//红兄弟
else if (brother->_colour == RED)
{
parent->_colour = RED;
brother->_colour = BLACK;
RotateL(parent);//左旋父
}
}
else //待删除结点是父结点的右孩子
{
Node* brother = parent->_left;
//情况3.a 黑兄弟远红侄
if (brother->_colour == BLACK && brother->_left && brother->_left->_colour == RED)
{
RotateR(parent);//右旋父
brother->_colour = parent->_colour;//祖染父色
parent->_colour = BLACK;//父叔黑
brother->_left->_colour = BLACK;
//此情况完毕后，结束修复
break;
}
//情况3.b 黑兄弟近红侄
else if (brother->_colour == BLACK && brother->_right && brother->_right->_colour == RED)
{
brother->_colour = RED;//兄弟和侄子的颜色交换
brother->_right->_colour = BLACK;
RotateL(brother);//左旋兄
}
//情况3.c 黑兄弟双黑侄
else if (brother->_colour == BLACK
&& (brother->_left == nullptr || brother->_left->_colour == BLACK)
&& (brother->_right == nullptr || brother->_right->_colour == BLACK))
{
brother->_colour = RED;
if (parent == _root || parent->_colour == RED)
{
parent->_colour = BLACK;
break;
}
//向上调整
cur = parent;
parent = cur->_parent;
}
//红兄弟
else if (brother->_colour == RED)
{
parent->_colour = RED;
brother->_colour = BLACK;
RotateR(parent);//右旋父
}
}
}
}
}
//实际删除
if (delPos->_left == nullptr)//左为空和全空的情况
{
if (delPos == delParentPos->_left)
{
delParentPos->_left = delPos->_right;
if (delPos->_right)
{
delPos->_right->_parent = delParentPos;
}
}
else
{
delParentPos->_right = delPos->_right;
if (delPos->_right)
{
delPos->_right->_parent = delParentPos;
}
}
}
else//左不为空右为空
{
if (delPos == delParentPos->_left)
{
delParentPos->_left = delPos->_left;
if (delPos->_left)
{
delPos->_left->_parent = delParentPos;
}
}
else
{
delParentPos->_right = delPos->_left;
if (delPos->_left)
{
delPos->_left->_parent = delParentPos;
}
}
}
delete delPos;
return true;
}
- 验证
主函数如下：每删除一个结点考察是否仍保持红黑树
void testRBTree()
{
RBTree< int, int > t;
int arr[] = { 21,18,32,4,26,9,17,12,30,29 };
cout << "-------------插入结点------------" << endl;
for (int i=0;i<10;++i)
{
int e = arr[i];
t.Insert(make_pair(e, e*100));
}
t.InOrder();
cout << "是否为红黑树：" << t.isBalance() << endl;
cout << "-------------删除结点------------" << endl;
for (auto e : arr)
{
t.Erase(e);
cout << "是否为红黑树：" << t.isBalance() << endl;
}
}
int main()
{
testRBTree();
return 0;
}
7.红黑树与AVL树
AVL树是高度平衡的二叉搜索树，搜索时间复杂度为O(log2N),红黑树为近似平衡二叉搜索树，由于最长路径是最短路径的2倍（为常数项倍数），所以时间复杂度也为O(log2N)。
红黑树允许存在更大的“参差”，故也减少了插入结点时的旋转操作的次数，在STL的 map和set 中充当了底层数据结构。
我会以此博客中的红黑树代码为基础，实现一个简单的map（set）类，希望了解红黑树应用的朋友可以移步查看。
— end —
青山不改 绿水长流
