红黑树详解
什么是红黑树？
红黑树，是一种二叉搜索树的特化，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(logN)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的，如果一个节点是红色的则它的两个孩子结点是黑色的
- 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
- 每个叶子结点都是黑色的**(此处的叶子结点指的是空结点)**
为什么满足以上性质的二叉树就可以满足最短路径长度小于等于最长路径长度的两倍呢？
在极端情况下，根据性质2和3，假设一条路径全为黑色节点，另一条路径黑红节点交错，此时是满足最短路径长度小于等于最长路径长度的两倍的，其他非极端条件下也同样满足。
红黑树的实现
0.红黑树的节点
由左右父三个节点的指针、保存的数据val、节点的颜色组成
class RBTNode
{
public:
RBTNode<T>* _left;
RBTNode<T>* _right;
RBTNode<T>* _parent;
T val;
color _col;
RBTNode(const T& v)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,val(v)
{}
};
1.红黑树的插入操作
我们假设原红黑树是正确的，假设插入节点是黑色节点，它会破坏性质3，这种破坏想要重新调整为红黑树是十分困难的，原因是它要控制每条路径黑节点的数量，因此对每条路径都要调整，而假如插入节点是红色节点，那么只需要对有限个节点进行变色+旋转就可以把树重新调整为红黑树。
因此这里我们假定插入节点是红色节点。
这里把红黑树的插入分为三种情况：
定义：当前节点，父节点（当前节点的父亲），舅节点（父节点的兄弟节点），祖父节点（父节点的父节点）
1.插入节点的父节点是黑节点：此时没有违反红黑树的任何一条性质，直接按照AVL树的插入性质进行插入就可以。
2.插入节点的父节点是红节点，舅节点不存在或存在但为黑节点：此时违反了红黑树的性质2
- 当父节点在祖父节点左侧时，假如插入节点在祖父节点的左侧，对祖父节点进行右单旋，对父节点和祖父节点进行变色处理。当插入节点在祖父节点的右侧，对父节点进行左单旋，对祖父节点进行右单旋，再对当前节点和祖父节点进行变色处理，此时就完成了红黑树的插入。
- 当父节点在祖父节点右侧时，假如插入节点在祖父节点的右侧，对祖父节点进行左单旋，对父节点和祖父节点进行变色处理。当插入节点在祖父节点的左侧，对父节点进行右单旋，对祖父节点进行左单旋，再对当前节点和祖父节点进行变色处理，此时就完成了红黑树的插入。
3.插入节点的父节点是红色，舅节点是红节点：此时违反了红黑树的性质2
- 此时只需要对父节点和舅节点和祖父节点进行变色处理，此时不知道祖父节点是不是根节点，因此要继续向上处理！
4.插入节点就是根节点：直接插入黑节点
最后！记得把根节点设置为黑节点，防止循环向上变色时把根节点处理为红色
代码实现：
pair<iterator, bool> insert(const T x)
{
KeyOfT kot;
if (_root == nullptr)
{
_root = new Node(x);
_root->_col = BLACK;
return make_pair(iterator(_root), true);
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kot(x)>kot(cur->val))
{
parent = cur;
cur = cur->_right;
}
else if (kot(x) < kot(cur->val))
{
parent = cur;
cur = cur->_left;
}
else
{
return make_pair(iterator(cur), false);
}
}
cur = new Node(x);
cur->_col = RED;
cur->_parent = parent;
Node* newnode = cur;
if (kot(x)>kot(parent->val))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle&& uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
RotateR(parent);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col=BLACK;
grandfather->_col = RED;
}
break;
}
}
if (parent == grandfather->_right)
{
Node* uncle = grandfather->_left;
if (uncle&& uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return make_pair(iterator(newnode), true);
}
左旋代码：
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 (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
}
右旋代码：
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 (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}
2.验证红黑树是否平衡函数
对红黑树是否平衡的检查主要检查的是性质2和性质3，通过验证是否有两个连续的红节点可以验证性质2，通过递归获取每条路径的黑节点个数和提前计算好的基准值进行对比就可以验证性质3
代码实现：
bool isbalance()
{
if (_root == nullptr)
{
return true;
}
if (_root->_col != BLACK)
{
return false;
}
Node* cur = _root;
int count = 0;
while (cur)
{
if (cur->_col == BLACK)
{
count++;
}
cur = cur->_left;
}
int num = 0;
return _isbalance(_root, count, num);
}
bool _isbalance(Node* _root,int count,int num)
{
if (_root == nullptr)
{
if (num == count)
{
return true;
}
return false;
}
if (_root->_col == BLACK)
{
num++;
}
if (_root->_col == RED && _root->_parent->_col == RED)
{
return false;
}
return _isbalance(_root->_left, count, num) && _isbalance(_root->_right, count, num);
}
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;
}
2.前置–操作符的重载：
如果左子树存在，找到左子树的最右节点，它就是下一个节点
如果左子树不存在，向上循环找到第一个子节点不是父节点左节点的节点，它就是下一个节点
Self& operator--() { if (_node->_left) { Node* right = _node->_left; while (right->_right) { right = right->_right; } _node = right; } else { Node* parent = _node->_parent; Node* cur = _node; while (parent && cur == parent->_left) { cur = cur->_parent; parent = parent->_parent; } _node = parent; } return *this; }