红黑树详解
概述
二叉树是常见且广泛使用的一种树，面临其可能退化成链表的潜藏缺点，在使用上难免让人担心其效率。为了让降低这种不平衡的可能性，具有自动平衡左右数量分布效果的自平衡二叉搜索树(AVL 树)被发明了出来。
为了能让二叉树获得更高的查找效率、更方便的到达目的地，在 AVL 树基础上，红黑树被发明了出来。
红黑比平衡性的要求比 AVL 树还要宽松。红黑树是利用节点颜色来检查二叉树每条路径的高度是否差不多，因为发明者定下了以下规则：
-
树上的每个结点(node) 只能是 红色 或 黑色。
-
根节点(root) 一定是黑色。
-
叶子节点(leaf) 一定是 黑色 的 空值节点 (NULL)。
-
任一路径上不能有两个连续的红色。注意：黑色节点的子节点颜色没有限制。
红黑树的算法时间复杂度为 O(logn)，因为红黑树保证最长路径不会超过最短路径的两倍（由规则 4 和规则 5）。原因是：当某条路径最短时，这条路径必然都是由黑色节点构成。当某条路径长度最长时，这条路径必然是由红色和黑色节点相间构成（规则4限定了不能出现两个连续的红色节点）。而规则5又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点。此时，在路径最长的情况下，路径上红色节点数量 = 黑色节点数量。该路径长度为两倍黑色节点数量，也就是最短路径长度的 2 倍。
注意：null 节点是指每个叶节点都有两个空的并且颜色为黑的 NULL 节点，一般在示例图中需要它的时候就可以把它看成两个黑色的节点，不需要的时候可以忽视它。
红黑树与AVL的比较：
红黑树和 AVL 树的算法时间复杂度相同，但红黑树不追求完全平衡，换来的是增删节点时转转次数的降低，任何不平衡都会在三次旋转之内解决，但AVL是严格平衡树，旋转次数比红黑树多。插入节点失衡时，AVL 和 RBTree 都是最多两次旋转实现复衡 (O(1))，但删除节点失衡时，AVL 需要维护从被删除节点到根节点路径上所有节点的平衡 (O(logN))，而红黑树最多只需要 3 次 (O(1))，所以 RBTree 在内容极多时优于 AVL，RBTree 的功能、性能、空间开销综合更好。红黑树有着良好的稳定性和完整的功能，性能表现也很不错，综合实力强，在 STL 的 set 和 map 等容器中被优先使用。
因为红黑树也是一种二叉树，所以例如：插入结点、删除结点、查询结点等针对红黑树的操作与二叉树的操作前段演算法相同，只是在每次操作完后可能会让树的结构改变而可能无法满足红黑树的规则，进而可能不具有平衡的性质。为了在操作后仍是一颗红黑树，需要通过变色和旋转调整来满足红黑树的规则。
template<typename T>
class RBNode {
public:
RBNode* left_;
RBNode* right_;
RBNode* parent_;
bool is_black_;
T val_;
public:
RBNode(int value):
val_(value),
left_(nullptr),
right_(nullptr),
is_black_(true) {};
RBNode(int value, bool is_black):
val_(value),
left_(nullptr),
right_(nullptr),
is_black_(is_black) {};
~RBNode() {};
};
template<typename T>
class RBTree {
public:
RBNode<T>* root_;
public:
RBTree(): root_(nullptr) {};
~RBTree() {};
RBNode<T>* InsertNode(int value);
RBNode<T>* UpdateNode(int value);
void DeleteNode(int value);
RBNode<T>* FindValue(int value);
};
说明：由于在红黑树中，增加节点是会涉及到相邻节点的颜色转换为了更加方便的访问父节点，在红黑树中需要记录父节点的位置。
红黑树的插入操作
根据父节点的状态，我们分成三种情况讨论节点插入：
- 父节点不存在
- 父节点存在，且父节点为黑色。
- 父节点存在，且父节点为红色。
1. 父节点不存在
此时插入节点就是根节点，根据红黑树特性(2)直接插入黑节点
2. 父节点存在，且父节点为黑色
假如插入节点必须是黑色，则需要对整个红黑树进行调色，才能使得红黑树保证红黑树满足特性(5)，而假如插入节点是红色节点，那么只需要对有限个节点进行变色+旋转就可以把树重新调整为红黑树。因此这里我们假定插入节点是红色节点。
在此基础上，我们再把插入分为三种情况讨论：
基础定义：当前节点，父节点（当前节点的父亲），舅节点（父节点的兄弟节点），祖父节点（父节点的父节点）
-
插入节点的父节点是黑节点：此时没有违反红黑树的任何一条性质，直接按照AVL树的插入性质进行插入就可以。
-
插入节点的父节点是红节点，舅节点不存在或存在但为黑节点：此时违反了红黑树的性质2
当父节点在祖父节点左侧时，假如插入节点在祖父节点的左侧，对祖父节点进行右单旋，对父节点和祖父节点进行变色处理。当插入节点在祖父节点的右侧，对父节点进行左单旋，对祖父节点进行右单旋，再对当前节点和祖父节点进行变色处理，此时就完成了红黑树的插入。 当父节点在祖父节点右侧时，假如插入节点在祖父节点的右侧，对祖父节点进行左单旋，对父节点和祖父节点进行变色处理。当插入节点在祖父节点的左侧，对父节点进行右单旋，对祖父节点进行左单旋，再对当前节点和祖父节点进行变色处理，此时就完成了红黑树的插入。
- 插入节点的父节点是红色，舅节点是红节点：此时违反了红黑树的性质2
此时只需要对父节点和舅节点和祖父节点进行变色处理，此时不知道祖父节点是不是根节点，因此要继续向上处理！ 4.
最后！记得把根节点设置为黑节点，防止循环向上变色时把根节点处理为红色。 代码如下。
const RBNode<T>&& InsertNode(int value) {
if (!root_) {
RBNode b_node(value);
root_ = &b_node;
return std::move(b_node);
}
auto & parent = FindParent(value);
if (parent->is_black_) {
RBNode r_node(value, false);
parent->left = r_node;
return parent;
}
else {
}
}
验证红黑树是否平衡函数
对红黑树是否平衡的检查主要检查的是性质2和性质3，通过验证是否有两个连续的红节点可以验证性质2，通过递归获取每条路径的黑节点个数和提前计算好的基准值进行对比就可以验证性质3
3.红黑树的迭代器 红黑树的迭代器设计中有困难主要是++和–操作符的重载，我们知道红黑树按照中序遍历得到的数据是有序的，我们要模拟中序遍历这个过程实现++和–-
begin()函数返回红黑树中序遍历的第一个节点构建的迭代器，也就是红黑树的最左节点，利用循环可以找到
end()函数红黑树中序遍历的最后一个节点构建的迭代器，也就是空节点nullptr
1.前置++操作符的重载：
如果右子树存在，找到右子树的最左节点，它就是下一个节点 如果右子树不存在，向上循环找到第一个子节点不是父节点右节点的节点，它就是下一个节点
Self& operator++()
{
if (_node->_right)
{
Node* left = _node->_right;
while (left->_left)
{
left = left->_left;
}
_node = left;
}
else
{
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_right)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--()
{
if (_node->_right)
{
Node* left = _node->_right;
while (left->_left)
{
left = left->_left;
}
_node = left;
}
else
{
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_right)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}