1.红黑树的概念
2.红黑树的性质
只要满足前四点规则，就能保证 最长路径<=最短路径*2。
由红黑树的性质可以推出：
1.最短路径全是黑色结点
2.最长路径一定是一红一黑相间的。
3.红黑树插入结点的规则
首先我们每次插入结点时都需要插入红色结点。因为插入红色结点可能会违背规则三，这时我们可以调整。但是如果插入黑色结点的话，一定会违反规则四，并且调整起来是相当有难度的！
3.1情况一
其中a,b,c,d,e代表每条路径有x个黑色结点的红黑树子树。
分析一下：
如果x=1，则a,b,c,d,e代表每条路径有1个黑色结点,那么cur一定不可能是新增结点，但是cur和p是两个连续的红节点，已经违反了规则三，所以cur原本的颜色其实是黑色，它之所以变成红色是由其子树的变化影响的。
其实是由于a下面新增了一个结点，通过调整，所以cur更换了颜色。
那么把这种情况拿出来讨论：
这是x=0的情况，想要满足红黑树的规则三和规则四，就需要将p，u变成黑色，将g变成红色。当然，cur不管接在p/u的哪个子树都是一样的。
经过这些变化后，还没有结束，因为g变成红色，如果g的父亲也是红色，还需要继续往上调整就来到了下图：
这样思路就比较清晰了。
我们还需要清楚的是：
既然cur是红色，如果p是黑色的话就不需要调整，因为没有违反红黑树的规则。所以p是红色，既然p是红色，那么g一定是黑色,否则，之前的红黑树是有问题的。所以cur,p,g的颜色是固定的。只有u存在与否和颜色是不能确定的，红黑树的结点插入情况也是根据u来分类的。
3.2情况二
如果u不存在，则：
先变颜色：p变黑，g变红。然后再右单旋，就可以满足红黑树的性质，不需要继续往上处理。
如果u存在且为黑，则：
上图是情况一和情况二合并的情况，同样的道理，也是p变黑，g变红，然后进行一次右单旋。
这种情况和上面是一样的，只不过由单旋换成双旋。先进行一次左单旋，就变成了上面的情况。然后再变色，右单旋。
4.红黑树的底层
RBTreeTest1()为测试代码
#pragma once
#include<iostream>
using namespace std;
enum Colour{
RED,
BLACK
};
template<class k, class v>
struct RBTreeNode {
RBTreeNode(const pair<k,v>& kv)
:_kv(kv)
{}
RBTreeNode<k, v>* _left = nullptr;
RBTreeNode<k, v>* _right = nullptr;
RBTreeNode<k, v>* _parent = nullptr;
pair<k, v> _kv;
Colour _col= RED;
};
template<class k,class v>
class 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->_parent = parent;//易错
if (parent->_kv.first > kv.first) parent->_left = cur;
else parent->_right = 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 = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
//叔叔不存在或叔叔存在且为黑
else {
if (cur == parent->_left) {//单旋
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else {
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else {
Node* uncle = grandfather->_left;
//叔叔存在且为红
if (uncle && uncle->_col == RED) {
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
//叔叔不存在或叔叔存在且为黑
else {
if (cur == parent->_right) {//单旋
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else {
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
_root->_col = BLACK;
}
return true;
}
void RotateR(Node* parent) {//易错，看清是左旋还是右旋
//改变树形结构
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
subL->_right = parent;
//调整父子关系
Node* ppNode = parent->_parent;
if (subLR) subLR->_parent = parent;//易错，判断是否为空指针
parent->_parent = subL;
//处理根节点
if (parent == _root) {
_root = subL;
subL->_parent = nullptr;//易错，根节点的父节点调整为0
}
else {
subL->_parent = ppNode;
if (ppNode->_left == parent) ppNode->_left = subL;
else ppNode->_right = subL;
}
}
void RotateL(Node* parent) {
//改变树形结构
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
subR->_left = parent;
//调整父子关系
Node* ppNode = parent->_parent;
if (subRL) subRL->_parent = parent;
parent->_parent = subR;
//处理根节点
if (parent == _root) {
_root = subR;
subR->_parent = nullptr;
}
else {
subR->_parent = ppNode;
if (ppNode->_left == parent) ppNode->_left = subR;
else ppNode->_right = subR;
}
}
void InOrder() {
_InOrder(_root);
}
bool IsBalance() {
if (_root->_col == RED) return false;
int refNum = 0;
Node* cur = _root;
while (cur) {
if (cur->_col == BLACK) refNum++;
cur = cur->_left;
}
return Check(_root,0,refNum);
}
private:
bool Check(Node* root,int black,const int refNum) {
if (root == nullptr) {
if (refNum != black)
cout << "存在黑色结点数量不相等的路径" << endl;
return true;
}
if (root->_col == RED && root->_parent->_col == RED) {
cout << root->_kv.first << "存在连续的红色结点" << endl;
return false;
}
if (root->_col == BLACK) black++;
return Check(root->_left,black, refNum) && Check(root->_right,black, refNum);
}
void _InOrder(Node* root) {
if (root == nullptr) return;
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
private:
Node* _root = nullptr;
size_t _size=0;
};
void RBTreeTest1() {
//int arr[] = { 8,3,1,10,6,4,7,14,13 };
int arr[] = { 2,4,6,1,3,5,15,7,16,14,8,3,1,10,6,4,7,14,13 };
RBTree<int, int> t1;
for (auto e : arr) {
t1.insert({ e,e });
}
t1.InOrder();
cout << t1.IsBalance() << endl;
}#include"RBTree.h"
int main() {
RBTreeTest1();
return 0;
}