一、红黑树的概念
在 AVL 树中删除一个结点，旋转可能要持续到根结点，此时效率较低
红黑树也是一种二叉搜索树，通过在每个结点中增加一个位置来存储红色或黑色，并对结点的着色进行限制，使得该二叉搜索树的最长路径不超过最短路径的两倍，即红黑树是一颗近似平衡的二叉搜索树，他不像 AVL 树的平衡那么严格，所以红黑树在插入和删除时，也不需要大量的旋转，并且搜索效率差不了 AVL 多少
红黑树是一颗二叉搜索树并且满足如下规则：
- 每个节点不是红色就是黑色
- 根结点是黑色的
- 每个红结点的左右孩子一定是黑色
- 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点
- 叶结点都是黑色的(这里的叶结点指的是空节点)
根据上述规则可以得到：最短路径：全黑结点的路径，最长路径：一黑一红的路径，所以红黑树可以保证最长路径不超过最短路径的一半
二、红黑树的实现
1. 红黑树的存储结构
// 结点的颜色
enum Color { RED, BLACK };
// 红黑树的结点
template<class K, class V>
struct RBTreeNode
{
std::pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Color _color; // 结点的颜色
RBTreeNode<K, V>(const std::pair<K, V>& kv = std::pair<K, V>(K(), V()))
: _kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _color(RED) // 为了方便树的结构调整，新结点默认为红色
{}
};
// 红黑树
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
RBTree<K, V>()
: _root(nullptr)
{}
private:
Node* _root;
};
2. 红黑树的插入
首先按照二叉搜索树的方式插入结点，保证插入结点之后还是二叉搜索树，为了方便树的结构调整，插入结点默认为为红色，当插入结点完成之后，可能会违反红黑树的性质，此时有三种情况
-
插入结点的父节点是黑色：没有违反红黑树的性质
-
插入结点的父节点是红色，叔节点存在且为红：违反了红黑树的性质，此时需要对父节点和爷爷结点进行变色
由于父节点是红色的，所以爷爷结点一定存在且为黑，变色完之后，如果 g 结点是根结点，则将 g 结点变为黑色，否则将 g 结点所在的子树当做新插入的结点，继续向上调整
- 插入结点的父节点是红色，叔节点不存在或存在且为黑：违反了红黑树的性质，此时需要对爷爷结点所在的子树进行旋转然后再对结点进行变色
由于父节点是红色的，所以爷爷结点一定存在且为黑，变色完之后，子树的根结点是黑色的，不用继续向上调整
u 存在且为黑的情况，一定是由 u 存在且为红的情况继续向上调整而来的
// 右旋
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;
if (pparent == nullptr) _root = subL;
else
{
if (pparent->_left == parent) pparent->_left = subL;
else pparent->_right = subL;
}
subL->_parent = pparent;
}
// 左旋
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;
if (pparent == nullptr) _root = subR;
else
{
if (pparent->_left == parent) pparent->_left = subR;
else pparent->_right = subR;
}
subR->_parent = pparent;
}
// 插入
bool Insert(const std::pair<K, V>& kv)
{
// 按照二叉搜索树的方式插入结点，保证该树插入结点之后还是二叉搜索树
if (_root == nullptr)
{
_root = new Node(kv);
_root->_color = BLACK;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else return false;
}
cur = new Node(kv);
if (parent->_kv.first > kv.first) parent->_left = cur;
else parent->_right = cur;
cur->_parent = parent;
// 更新颜色
while (parent && parent->_color == RED)
{
Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
// u 存在且为红
// u 不存在或存在且为黑
// p 为 g 的左，cur 为 p 的左 右单旋
// p 为 g 的左，cur 为 p 的右 先左旋再右旋
if (uncle && uncle->_color == RED)
{
grandfather->_color = RED;
parent->_color = BLACK;
uncle->_color = BLACK;
// 继续判断是否违反了红黑树的性质
cur = grandfather;
parent = grandfather->_parent;
}
else
{
if (parent->_left == cur)
{
RotateR(grandfather);
grandfather->_color = RED;
parent->_color = BLACK;
}
else
{
RotateL(parent);
RotateR(grandfather);
grandfather->_color = RED;
cur->_color = BLACK;
}
}
}
else
{
Node* uncle = grandfather->_left;
// u 存在且为红
// u 不存在或存在且为黑
// p 为 g 的右，cur 为 p 的右 左单旋
// p 为 g 的右，cur 为 p 的左 先右旋再左旋
if (uncle && uncle->_color == RED)
{
grandfather->_color = RED;
parent->_color = BLACK;
uncle->_color = BLACK;
// 继续判断是否违反了红黑树的性质
cur = grandfather;
parent = grandfather->_parent;
}
else
{
if (parent->_right == cur)
{
RotateL(grandfather);
grandfather->_color = RED;
parent->_color = BLACK;
}
else
{
RotateR(parent);
RotateL(grandfather);
grandfather->_color = RED;
cur->_color = BLACK;
}
}
}
}
_root->_color = BLACK;
return true;
}
