【数据结构】平衡树之红黑树
AVL树解决了二叉搜索树退化为单支树而引发的效率问题，是一种绝对平衡的二叉搜索树，其性质（每个节点的左右子树高度差绝对值都不超过1）使其在对数据进行搜索时始终能保持高效（详见【数据结构】平衡树之AVL树）。但是，当涉及一些结构上的修改场景（例如增删），因为要频繁通过旋转来维护其绝对平衡的结构特性，代价较高，使得其在这样的场景中性能十分低下。
为了继续优化效率问题，后来又不断有大佬提出新的解决方案。1972年，Rudolf Bayer发明了最初红黑树（当时被称为平衡二叉B树）。而后在1978年， Leo J. Guibas 和 Robert Sedgewick 将其修改成了如今的红黑树。
红黑树（RBTree）是一种特殊的二叉平衡搜索树，通过一种特殊的“手法”来控制着二叉搜索树的平衡，使其效率与AVL树相当，且在应用和维护等方面整体优于AVL树。
对于平衡的控制，红黑树放弃了AVL树中调整平衡因子的方式（任一节点的左右子树高度差的绝对值不大于1），而是在树的每个节点上增加了一个用于表示节点的颜色（可以是Red或Black）的存储位，通过对任意一条从根到某个叶子节点的路径上，各个节点着色方式的限制，确保最长路径不超过最短路径的2倍，以此来使一整棵树接近平衡。
红黑树的应用十分的广泛，例如Java的集合框架 (HashMap、TreeMap、TreeSet)、C++ 的 STL（map/set、mutil_map/mutil_set）、linux内核等等，都将红黑树作为底层结构来使用过。
本篇博客将通过，对红黑树性质的梳理和主要功能的模拟实现，来帮助读者更加全面地了解红黑树。
目录
1.控制节点的红和黑，怎么就做到了“最长路径不超过最短路径的2倍”？
一、红黑树的性质
红黑树是因其维护平衡的手段而得名的，通过对树节点颜色的控制，来实现“最长路径不超过最短路径的2倍”的近似平衡。它主要具备以下性质（或者说是它的平衡规则），且这些性质与维护平衡息息相关：
- 任意一个树节点的颜色非红即黑；
- 根节点的颜色必为黑；
- 任意一个颜色为红的树节点，其孩子节点均为黑，双亲节点为黑（这意味着任意路径上没有连续的红色节点）；
- 对于任意一条从（不为空的叶节点下的）空节点通往根节点的路径，每条路径上黑色节点数量均相同；
- 每个空节点默认为黑色。
（ps：NIL节点指的是空节点 ）
二、红黑树的模拟实现
1 - 树的构建
//用枚举体来标识节点的颜色
enum Colour
{
RED, //0
BLACK, //1
};
//创建一个树节点（三叉链结构）
template<class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left; //左孩子
RBTreeNode<K, V>* _right; //右孩子
RBTreeNode<K, V>* _parent; //双亲
pair<K, V> _kv; //节点的值
Colour _col; //放弃了AVL树的平衡因子，改用颜色标识来控制平衡
//一个树节点的构造函数
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;
private:
//根节点
Node*_root = nullptr;
};
2 - 插入
红黑树可以看作是引入了颜色标识的二叉搜索树，与AVL树类似（详见【数据结构】平衡树之AVL树），它插入过程也大致分为两步：
- 按照二叉搜索树的方式插入新节点：利用插入的值创建一个新的树节点。树为空，就直接将新节点赋给根节点的指针；树不为空，就按二叉搜索树的性质查找到合适的插入位置，在合适位置插入新节点。
- 控制树的平衡：调整颜色+旋转。
bool Insert(const pair<K, V>& kv)
{
//1.按照二叉搜索树的方式插入新节点
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);
cur->_col = RED;
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//2.控制树的平衡
//...
}因为默认一个新插入的节点为红色（原因见下文“一些迷思”），所以插入后就存在两种情况：
- 新插入节点的双亲为黑色，则仍满足红黑树的平衡性质，无需控制平衡；
- 新插入节点的双亲为红色，则违背平衡性质三，需控制平衡。
而当新插入节点的双亲为红色，该如何控制平衡呢？
插入节点的双亲一定是红色的，双亲的双亲一定是黑色的，这两个节点的颜色是始终确定的。 插入的节点为红色，插入后出现了两个连续的红色节点，此时就需要调整节点的颜色。
调整颜色既是控制树平衡的手段，也是检验是否需要旋转的途径。调整颜色的对象不是新插入的节点，而是其双亲、双亲的兄弟和双亲的双亲。
详情见下图：
【Tips】新节点插入后，平衡的控制具体取决于其双亲的兄弟节点：
- 双亲的兄弟节点存在且为红色，调整颜色后，继续向上更新；
- 双亲的兄弟节点不存在，或存在且为黑色，需先旋转，然后再调整颜色。
（关于将特殊情景下的结论推广到一般性结论的说明，以及旋转分类讨论的图解，见下文“一些迷思”）
【Tips】旋转的分类讨论：
设：c为当前节点，p为其双亲节点，g为其祖父节点，u为其双亲的兄弟节点，并且cur为红色，p为红色，g为黑色，u不存在或u存在且为黑色。
1、p为g的左孩子，c为p的左孩子，则针对g做右单旋转；
2、p为g的左孩子，c为p的右孩子，则针对p做左单旋转，再针对g做右单旋转；
3、p为g的右孩子，c为p的右孩子，则针对g做左单旋转；
4、p为g的右孩子，c为p的左孩子，则针对p做右单旋转；
bool Insert(const pair<K, V>& kv)
{
//1.按照二叉搜索树的方式插入新节点
//...（见前文）
//2.控制平衡
while (parent && parent->_col == RED)//其双亲存在且双亲为红，才需要处理
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)//parent是grandfather的左孩子
{
Node* uncle = grandfather->_right;//则uncle是grandfather的右孩子
//uncle存在且为红
if (uncle && uncle->_col == RED)
{
//变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上处理
cur = grandfather;
parent = cur->_parent;
}
//uncle不存在，或存在且为黑
else
{
if (cur == parent->_left)
{
// g
// p
// c
//旋转
RotateR(grandfather);
//变色
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p
// c
//旋转
RotateL(parent);
RotateR(grandfather);
//变色
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else //parent == grandfather->_right //parent是grandfather的右孩子
{
Node* uncle = grandfather->_left;//则uncle是grandfather的左孩子
// uncle存在且为红
if (uncle && uncle->_col == RED)
{
//变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上处理
cur = grandfather;
parent = cur->_parent;
}
//uncle不存在，或存在且为黑
else
{
if (cur == parent->_right)
{
// g
// p
// c
//旋转
RotateR(grandfather);
//变色
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p
// c
//旋转
RotateL(parent);
RotateR(grandfather);
//变色
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;//无论什么情况，根始终要置为黑
return true;
}（旋转的细节详见【数据结构】平衡树之AVL树）
//左单旋
void RotateL(Node* parent)
{
Node* cur = parent->_right; //cur是parent的右孩子
Node* curleft = cur->_left; //curleft是cur的左孩子
//将parent及其左子树整体旋转下来，并将parent与cur、curleft与parent、cur与ppnode一一正确链接
parent->_right = curleft;
if (curleft)
{
curleft->_parent = parent; //curleft可能为空，若为空则无需将curleft->_parent与parent链接
}
cur->_left = parent;
//需要旋转的树，可能是一个局部的子树
//cur可能需要跟parent的双亲节点ppnode链接
Node* ppnode = parent->_parent;
parent->_parent = cur;
if (parent == _root /*ppnode==nullptr*/) //旋转点在根，cur无需跟parent的双亲节点链接
{
_root = cur;
cur->_parent = nullptr;
}
else //旋转点不在根，cur需要跟parent的双亲节点链接
{
if (ppnode->_left == parent) //parent是ppnode的左孩子，就让cur代替其成为左孩子
{
ppnode->_left = cur;
}
else //parent是ppnode的右孩子，就让cur代替其成为右孩子
{
ppnode->_right = cur;
}
cur->_parent = ppnode; //将cur的双亲节点置为ppnode
}
}
//右单旋
void RotateR(Node* parent)
{
Node* cur = parent->_left; //cur是parent的左孩子
Node* curright = cur->_right; //curright是cur的右孩子
//将parent及其右子树整体旋转下来，并将parent与cur、curleft与parent、cur与ppnode一一正确链接
//链接curright与parent
parent->_left = curright;
if (curright)
{
curright->_parent = parent;
}
//链接cur与parent、cur与parent的双亲ppnode
Node* ppnode = parent->_parent;
cur->_right = parent;
if (ppnode == nullptr)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
{
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
}
3 - 完整代码
#pragma once
#include<iostream>
using namespace std;
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 _col;
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_col(RED)
{}
};
template<class K, class V>
struct 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);
cur->_col = RED;
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//红黑树插入的关键是uncle
//1、uncle存在且为红，则变色+继续向上更新
//2、uncle不存在，或uncle存在且为黑，则旋转+变色
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;
}
//uncle不存在，或存在且为黑
else
{
if (cur == parent->_left)
{
// g
// p
// c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else // parent == grandfather->_right
{
Node* uncle = grandfather->_left;
// uncle存在且为红
if (uncle && uncle->_col == RED)
{
//变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上处理
cur = grandfather;
parent = cur->_parent;
}
//uncle不存在，或存在且为黑
else
{
if (cur == parent->_right)
{
// g
// p
// c
//旋转+变色
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p
// c
//旋转+变色
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
//左单旋
void RotateL(Node* parent)
{
++_rotateCount;
Node* cur = parent->_right;
Node* curleft = cur->_left;
parent->_right = curleft;
if (curleft)
{
curleft->_parent = parent;
}
cur->_left = parent;
Node* ppnode = parent->_parent;
parent->_parent = cur;
if (parent == _root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
{
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
}
//右单旋
void RotateR(Node* parent)
{
++_rotateCount;
Node* cur = parent->_left;
Node* curright = cur->_right;
parent->_left = curright;
if (curright)
curright->_parent = parent;
Node* ppnode = parent->_parent;
cur->_right = parent;
parent->_parent = cur;
if (ppnode == nullptr)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
{
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
}
//验树的平衡
bool CheckColourNum(Node* root, int blackNum,int benchmark)//递归查询连续的红色节点和验证黑色节点数量
{
if (root == nullptr)
{
if (blackNum != benchmark)//若某一条路径上的黑色节点数量与基准值不符，则说明树不平衡（无论基准值本身是否正确）
{
return false;
}
return true;
}
//递归记录某一条路径上的黑色节点数量
if (root->_col == BLACK)
{
++blackNum;
}
//出现两个连续的红色节点，则说明树不平衡
if (root->_col == RED && root->_parent && root->_parent->_col == RED)
{
cout << root->_kv.first << "RED show up" << endl;
return false;
}
//递归至左子树和右子树里去验证平衡
return CheckColourNum(root->_left,blackNum,benchmark)
&& CheckColourNum(root->_right, blackNum, benchmark);
}
bool IsBalance()//封装一次“bool IsBalance(Node* root)”
{
return IsBalance(_root);
}
bool IsBalance(Node* root)//验树的平衡
{
//空树是平衡的
if (root == nullptr)
return true;
//根节点不是黑色的，则说明树不平衡
if (root->_col != BLACK)
{
return false;
}
//取最左路径上的黑色节点数量作为基准值
Node* cur = _root;
int benchmark = 0;
while (cur)
{
if (cur->_col == BLACK)
{
++benchmark;
}
cur = cur->_left;
}
//查询连续的红色节点和验证黑色节点数量
return CheckColourNum(root,0,benchmark);//参数：根节点，当前路径的黑节点数量，黑节点数量的基准值
}
//求树的高度
int Height()
{
return Height(_root);
}
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;
}
private:
Node* _root = nullptr;
};补、一些迷思
1.控制节点的红和黑，怎么就做到了“最长路径不超过最短路径的2倍”？
如下图，是一棵满足“最长路径不超过最短路径的2倍”的合法红黑树，它的最长路径为4（例如13->17->25->22），最短路径为3（例如13->8->1）。
同样的，下图中是一种极端情况下的红黑树，但它仍是合法的。它的最长路径为4（例如13->17->25->22），最短路径为2（例如13->8）。
由此可见，控制节点的红和黑，保证最短路径全黑、最长路径是一黑一红相间的（或每条路径上黑色节点的总数占整棵树节点总数的1/2），就满足了“最长路径不超过最短路径的2倍”。
2.由红黑树与AVL树的性能比较，来说明为什么放弃绝对平衡
| 平衡树 | 特点 | 查找效率大致为 | 创建一棵树的数据量 | 创建后树的高度 | 所需时间约为 |
| AVL树 | 高度差的绝对值不超过1 | O(logN) | 1000个值 | 10 | 0.000001s |
| 红黑树 | 最长路径不超过最短路径的2倍 | O(2*logN) | 1000个值 | 20 | 0.000002s |
对于红黑树与AVL树，两者的性能在同一量级上，效率差距并不大，虽然在维护平衡时均需旋转，但AVL树因控制平衡更加严格，需在插入和删除时频繁通过旋转维护其结构，会付出较大的代价，故红黑树整体优于AVL树。
3.为什么新创建的节点/新插入的节点默认为红色？
当插入的节点为黑色，此时在所插入的路径上，黑色节点的数量比其他路径上多1，就违背了红黑树的性质四（对于任意一条从空节点通往根节点的路径，每条路径上黑色节点数量均相同）。
当插入的节点为红色，若此时所插入位置的双亲为红色，即出现了连续的红色节点，就违背了红黑树的性质三（任意路径上没有连续的红色节点）。
也就是说，插入的节点无论是什么颜色的，都会对红黑树的平衡有潜在的影响。
不过具体而言，若插入的节点为黑色，则是“一定会因违背性质四而破坏平衡”，此时是必须对红黑树进行调整的，且要对多条路径进行调整；而插入的节点为红色，则是“可能会因性质三而破坏平衡”，此时既可能要进行调整，也可能不进行调整，且调整时仅对一条路径进行调整。
基于这样的利弊，插入节点为红色时维护平衡的代价在理论上更小，故使插入的新节点/新创建的节点默认为红色。
4.对两种需控制平衡的情景的更多说明
设：cur为当前节点，p为其双亲节点，g为其祖父节点，u为其双亲的兄弟节点。
情景一：cur为红，p为红，g为黑，u存在且为红。cur和p均为红，违背了性质三。解决方法为，将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。
当a/b/c/d/e为空树，cur是新插入的节点，情况较为简单，上述解决方法是适用的。
而当a/b/c/d/e不为空树，cur不是新插入的节点，尽管情况较为复杂，但上述解决方法仍适用。
更复杂的情况又例如，c/d/e是每条路径都有两个黑色节点的子树...
情景二：cur为红，p为红，g为黑，u不存在/u存在且为黑。
u不存在，做旋转的处理。
u存在且为黑，做旋转和变色的处理。
【Tips】旋转的分类讨论：
1、p为g的左孩子，cur为p的左孩子，则针对g做右单旋转；
2、p为g的左孩子，cur为p的右孩子，则针对p做左单旋转，再针对g做右单旋转；
3、p为g的右孩子，cur为p的右孩子，则针对g做左单旋转；
4、p为g的右孩子，cur为p的左孩子，则针对p做右单旋转；
5.插入构建红黑树的过程图解
升序构建红黑树
降序构建红黑树
随机插入构建红黑树
