概述
概念
红黑树也是是一种自平衡的二叉搜索树，与AVL树不同的是它在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black；
通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍（最长路径也不会超出最短路径的两倍，因此红黑树的平衡性要求相对宽松，没有AVL树那样严格），从而使搜索树达到一种相对平衡的状态；
性质
-
每个结点不是黑色就是红色；
-
根结点必须是黑色的；
-
红色结点的两个子结点必须都是黑色的，这保证了没有两个连续的红色节点相连；
-
每个叶子结点都是黑色的(此处的叶子结点指的是空结点，也被称为NIL节点)；
-
任意结点到其每个叶子结点的简单路径上，黑色节点的数量相同：确保了树的黑平衡性，即红黑树中每条路径上黑色结点的数量一致；
分析
-
红黑树中的性质确保了任意路径上的黑色节点数量相等，这是红黑树能够保持平衡的关键；根据这个性质，我们可以证明红黑树的最长路径中的节点个数不会超过最短路径的节点个数的两倍。
-
假设红黑树的最短路径上的黑色节点数量为k；由于任意路径上的黑色节点数量相等，所以最长路径上的黑色节点数量不能少于k个；
-
现在来看最长路径上的节点个数；由于红色节点的两个子节点都是黑色的，因此最长路径上不能有连续的红色节点；而对于红黑树而言，最长路径上的红色节点数量最多为k，因为最长路径上的黑色节点数量不能少于k个；所以最长路径上的节点个数最多为2k，其中k个是黑色节点，k个是红色节点；
-
综上所述，红黑树的最长路径中的节点个数不会超过最短路径的节点个数的两倍，即最长路径上的节点个数最多为2k，其中k为最短路径上的黑色节点数量；
这个性质保证了红黑树的高度始终保持在较小的范围内，从而保持了树的平衡性。因为红黑树的高度与最长路径上的节点个数成正比，所以最长路径的节点个数的上限为最短路径的节点个数的两倍，确保了红黑树的平衡性和高效性；
这里分析一种极端的情况：如果一棵红黑树有红有黑，它里面如果有一条全黑的路径，那这条全黑的路径一定就是最短路径；如果有一条是一黑一红，一黑一红…，这样黑红相间的，那就是最长的路径；然后它们里面的黑色结点个数又是相同的的，所以最长路径最多是最短路径的两倍，不可能超过最短路径两倍；所以这样红黑树的高度就能够保持在一个相对平衡的范围内，当然就没有AVL树那么严格，比如：
每个叶子结点都是黑色的(此处的叶子结点指的是空结点，也被称为NIL节点)，有什么用？
对于最上面的红黑树样例图片，如果不带空的话，可能会认为有5条路径，但是这里计算路径其实应该走到空（NIL），所以正确的应该是有11条路径；可以认为这条规则就是为了更好的帮我们区分不同路径的；
对比AVL树
对于一棵红黑树来说，如果它里面全部的黑色结点一共有N个的话，那它的最短路径长度就差不多是logN；然后整棵树的节点数量就是在 (N，2N) 之间；所以最长路径长度就可以认为差不多是2logN；所以红黑树的查找最少是logN次，最多是2logN次，所以红黑树查找的时间复杂度是O(logN)。而AVL树也是O(logN），但AVL树是比较严格的O(logN），而红黑树是省略了常数项。 所以严格来说，红黑树的查找效率是比不上AVL树的（但对于计算机来说是没什么差别的），但是它们是同一个数量级的，都是O(logN）;
由于AVL树要求更加严格的平衡，所以在进行插入和删除操作时，可能需要更频繁地进行旋转操作来调整树的结构，以保持平衡；相比之下，红黑树的插入和删除操作需要旋转的次数相对较少，因此在插入和删除操作频繁的情况下，红黑树可能更加高效；
所以综合而言，红黑树其实更胜一筹，红黑树在实际应用中更为常用，STL中的map和set底层就是用的红黑树；
插入
对于红黑树来说，插入新结点之后，我们要检查红黑树的性质是否遭到破坏，如果遭到破坏的话，就需要进行相应的调整；
因为新节点的默认颜色是红色，因此：
-
如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；
-
但当新插入节点的双亲节点颜色为红色时，就违反了性质不能有连续红色结点出现，此时需要对红黑树分情况来讨论；
约定：
-
当我们在红黑树中插入一个新结点的时候，cur为当前新插入结点，p（parent）为父结点，g（grandfather）为祖父结点，u（uncle）为叔叔节点，比如：
第一次插入
作为根结点，直接将它染成黑色就完了；
父亲是黑色的
由于新插入的结点默认是红色的，这种也不需要调整，插入完直接结束；
cur为红，p为红，g为黑，u存在且为红（无需旋转，变色即可）
现在们插入一个红色结点，那这里就出现了连续红色结点的情况，这是不行的。 那可以直接把p改成黑色吗？不可以，直接把p改成黑色的话，这条路径就增加了一个黑色结点，但是其它路径数量不变，那就不满足所有路径黑色结点数量相同的性质了；
-
将p、u改为黑，g改为红；
-
如果g是根节点，调整完成后，需要将g改为黑色；
-
如果g是一棵子树，将p,u改为黑，g改为红；如果g的父亲是黑色，就可以结束了，但现在g的父亲也是红色，所以继续向上调整，把g当成cur，重新确定p、u、g，进行同样的操作，一直往上走，直至某一次调整完遇到g的父亲为黑或者走到根停止；
cur为红，p为红，g为黑，u不存在/u存在且为黑（单旋+变色）
如果出现u存在且为黑的情况一定是由上面的情况调整得到的。因为如果插入的时候就是这种情况：
是不可能出现的，因为这样的话插入之前红黑树中不同路径的黑色结点数量就不相等了，就不符合是一颗红黑树了；所以出现这种情况一定是上面的情况转变得来的：
那对于这种情况要进行旋转+变色（对于上面u不存在也是一样）；为什么要旋转？因为这种情况的话最长路径有可能已经超过最短路径的两倍了，比如上面这个图如果如果d/e是空的话就已经超过了；所以要先旋转降高度，再去调整颜色使它符合红黑树；进行什么旋转呢？ 那就要看具体情况了，其实还是AVL树的四种情况。当前是在较高左子树的左侧插入，所以要进行的旋转是右单旋；
先旋转（对g这棵树）的目的就是让它变平衡；然后变色怎么变呢？ 变色的话不论那种旋转是统一的：p、g变色——p变黑，g变红；
这样就重新符合红黑树了；
cur为红，p为红，g为黑，u不存在/u存在且为黑（双旋+变色）
上面分析的是需要进行单旋然后变色的情况，那当然就有需要进行双旋调整高度，然后再变色的情况。当然本质是因为插入的情况不同，所以需要不同的旋转来降高度；
首先前提条件跟上面一样，还是cur为红，p为红，g为黑，u不存在/u存在且为黑；
如果u不存在，就是这样：
先进行一个左右双旋；
然后cur变黑，g变红（不论哪种双旋，变色是一样的）；
这样就重新调整为红黑树了；
同样的，如果这里出现u存在且为黑的情况，也一定是情况3调整更新得到的，比如这样：
那然后其实和u为空一样，先进行一个左右双旋（因为这里画的还是较高左子树右侧插入的情况）；
然后变色，还是跟上面一样，cur变黑，g变红；
代码
#pragma once
enum Colour
{
RED,
BLACK,
};
template struct RBTreeNode
{
RBTreeNode *_parent;
RBTreeNode *_left;
RBTreeNode *_right;
T _data;
Colour _col;
RBTreeNode(const T &data) : _parent(nullptr), _left(nullptr), _right(nullptr), _data(data), _col(RED) {}
};
template class RBTree
{
typedef RBTreeNode Node;
public:
bool Insert(const T &data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return true;
}
Node *parent = nullptr;
Node *cur = _root;
while (cur)
{
if (data < cur->_data)
{
parent = cur;
cur = cur->_left;
}
else if (data > cur->_data)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
} // 走到这里cur为空，就是key应该插入的位置
cur = new Node(data); // 链接
if (data < parent->_data)
parent->_left = cur;
if (data > parent->_data)
parent->_right = cur; // 链接父亲指针
cur->_parent = parent; // 如果插入之后它的parent是红的，就需要进行调整
while (parent && parent->_col == RED)
{
Node *grandfather = parent->_parent; // 如果父亲是祖父的左孩子，那右孩子就是叔叔
if (parent == grandfather->_left)
{
Node *uncle = grandfather->_right; // 这里处理的情况是叔叔存在且为红，变色+向上继续处理
if (uncle && uncle->_col == RED)
{ // 将p,u改为黑，g改为红
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED; // 更新cur为grandfather，判断它的父亲是什么情况：
// 1.如果不存在或者为黑，就需要继续处理了，也不会进行循环了
// 2.如果它的父亲存在且为红，重新循环进行调整
cur = grandfather;
parent = cur->_parent;
}
else // 叔叔不存在/叔叔存在且为黑的情况
{ // g
// p u
// c
if (cur == parent->_left) // 左左——右单旋+变色
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else // 左右——左右双旋+变色
{ // g
// p u
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
} // 这里调整完就可以break了，因为颜色都变的合适了，而相关的链接关系旋转会帮我们处理
break;
}
} // 如果父亲是祖父的右孩子，那左孩子就是叔叔
else // parent = grandfather->_right
{
Node *uncle = grandfather->_left; // 这里处理的情况是叔叔存在且为红
if (uncle && uncle->_col == RED)
{ // 将p,u改为黑，g改为红
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED; // 更新cur为grandfather，判断它的父亲是什么情况：
// 1.如果不存在或者为黑，就需要继续处理了，也不会进行循环了
// 2.如果它的父亲存在且为红，重新循环进行调整
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right) // 右右——左单旋+变色
{ // g
// u p
// c
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else // 右左——右左双旋+变色
{ // g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
} // 上面处理过程中有可能会把根变成红色，这里统一处理一下，把根置成黑
_root->_col = BLACK;
return true;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool IsBlance()
{
if (_root && _root->_col == RED)
{
cout << "根结点是红色" << endl;
return false;
} // 先求出一条路径黑色结点数量
int mark = 0;
Node *cur = _root;
while (cur)
{
if (cur->_col == BLACK)
++mark;
cur = cur->_left;
} // 检查是否出现连续红色结点及所有路径黑色结点数量是否相等
return _Check(_root, 0, mark);
}
int TreeHeight() { return _TreeHeight(_root); }
private:
int _TreeHeight(Node *root)
{
if (root == nullptr)
return 0;
int RightH = _TreeHeight(root->_left);
int leftH = _TreeHeight(root->_right);
return RightH > leftH ? RightH + 1 : leftH + 1;
}
bool _Check(Node *root, int blackNum, int mark)
{
if (root == nullptr)
{ // 走到空就是一条路径走完了，比较一下是否相等
if (blackNum != mark)
{
cout << "存在黑色结点数量不相等" << endl;
return false;
}
return true;
}
if (root->_col == BLACK)
++blackNum;
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "出现连续红色结点" << endl;
return false;
}
return _Check(root->_left, blackNum, mark) && _Check(root->_left, blackNum, mark);
}
void _InOrder(Node *root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
} // 左单旋
void RotateL(Node *parent)
{
Node *subR = parent->_right;
Node *subRL = subR->_left; // 旋转并更新_parent指针
parent->_right = subRL;
if (subRL)
subRL->_parent = parent; // 先保存一下parent->_parent，因为下面会改它
Node *pparent = parent->_parent; // 旋转并更新_parent指针
subR->_left = parent;
parent->_parent = subR; // 若pparent为空则证明旋转的是一整棵树，因为根结点的_parent为空
if (pparent == nullptr)
{ // subR是新的根
_root = subR;
_root->_parent = nullptr;
} // 若pparent不为空，则证明旋转的是子树，parent上面还有结点
else
{ // 让pparent指向子树旋转之后新的根
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
{
pparent->_right = subR;
} // 同时也让新的根指向pparent
subR->_parent = pparent;
}
} // 右单旋
void RotateR(Node *parent)
{
Node *subL = parent->_left;
Node *subLR = subL->_right; // 旋转并更新_parent指针
parent->_left = subLR;
if (subLR)
subLR->_parent = parent; // 先保存一下parent->_parent，因为下面会改它
Node *pparent = parent->_parent; // 旋转并更新_parent指针
subL->_right = parent;
parent->_parent = subL; // 若parent等于_root则证明旋转的是一整棵树（这也是一种判断方法）
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{ // 让pparent指向子树旋转之后新的根
if (parent == pparent->_left)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
} // 同时也让新的根指向pparent
subL->_parent = pparent;
}
}
private:
Node *_root = nullptr;
};
参考
https://zhuanlan.zhihu.com/p/659174741