花了几个小时看了B站大佬刘冬煜讲解红黑树源码和性质，对红黑树知识有了一个很清晰的理解。
满满的成就感，把大佬有关红黑树的资料借用了一下，做了一点简单的修改。
红黑树具有如下的性质：
1.红黑树是一颗平衡二叉搜索树，其中序遍历单调不减。
2.节点是红色或者 黑色。
3.根节点是黑色。
4.每个叶节点（也有称外部节点，目的是将红黑树变为真二叉树，也就是NULL节点，空节点）是黑色的。
5.每个红色节点的两个子节点都是黑色。（也就是说从每个叶子到根的所有路径上不能有两个连续的红色节点）
6.从根节点到每个叶子的所有路径都包含相同数目的黑色节点（这个数值叫做黑高度）。
以下就是一颗红黑树：
实际上每一颗红黑树都有等价的B-树，上图的红黑树对应的等价B-树如下：
因此红黑树本质上就是一颗B-tree。
节点
RB_Node结构体，维护信息，左右儿子，父亲，前驱后继函数，真后继函数。
迭代器
iterator结构体，各种重载
搜索
private:find(T)和public:low_bound(T)，public:upper_bound(T)，public:serach(T)的实现。
插入与双红现象
为了尽最大可能维护性质6，每一次插入，都要将节点作为红色节点插入。二叉搜索树的插入比较容易做到，但是性质5可能因此被破坏，也就是说如果被插入的节点的父亲是红色，就会出现双红现象。如上图中图中的红黑树，插入1不会引起双红现象，但是插入59或者80都会引起双红现象。
双红修正
对于双红现象，可以分为以下三种情况修正：
RR-0（没有双红现象）
如果正在修正的节点的父亲是黑色，那么修正就已经结束了。
RR-1（叔叔是黑色）（插入到等价B-树的三节点中）
如果正在修正的节点的父亲是红色（那么祖父一定是黑色的），但是叔叔是黑色，那么只需要做1或者2次旋转，再进行2次染色就可以解决。（同时也是RR-2的递归基）
如对于上面的红黑树，插入到80之后，就会触发RR-1修正，此时只需要做一次旋转，两次染色即可：（右旋祖父100，再染红100，染黑86）
同样，如果插入90之后，也会触发RR-1修正，此时只需要做两次旋转，两次染色即可：（先左旋转父亲86，再右旋100，最后染红100，染黑90）
对称的情况也可以对称处理
RR-2 （叔叔是红色）（插入到等价B-树的四节点中）
如果正在修正的节点的父亲是红色（那么祖父一定是黑色），而且叔叔也是红色，那么递归就开始 了。 如对于刚刚插入 90 的红黑树，再插入 101 之后，就会触发 RR-2 递归。不过幸运的是，这次递归深 度只有 1，因为修正之后就是 RR-0：（染黑 101 的父亲 100、叔叔 86，然后染红祖父 90）
而如果插入的是 59 而不是 101，会触发 RR-2 递归，可是深度依然为 1，因为 RR-2 修正之后就是 RR-1， 这就是说 RR-1 也是 RR-2 的递归基的原因：（RR-2 过程：染黑父亲 58、叔叔 34，然后染红祖父 49，转化 为 RR-1。RR-1 过程：左旋 25，右旋 60，然后染红 60，染黑 49。这时根节点也发生了改变，注意维护根 节点）
那如果继续插入 80 呢？这将是一个递归深度为 3 的 RR-2 修正，最终将触发 RR-2 的第三个递归基— —递归达到根节点。这时只需要染黑根节点即可，同时全树黑高度+1：（两次 RR-2 和最后一次染黑根节 点的过程，在这张图中也比较明确了，也不再赘述）
可以看出，虽然 RR-2 需要递归解决缺陷，但是递归一定可以结束，因为每次缺陷必会上升两层， 直到最终达到根节点更新全树黑高度，或者中途触发 RR-0 或 RR-1 结束。 同时，和其他平衡二叉搜索树不同，但和 B-树相同，红黑树不是向下通过枝叶生长的，而是向上通 过根生长。
其他接口
begin() （迭代器起始）
当我们封装好红黑树后，用户依然可以用 iterator 来按元素从小到大的顺序遍历整棵树。而其实迭 代器就是 begin(void)。
end() （迭代器结束、search(T)失败的返回值）
不就是 iterator(NULL)吗！
size() （包含元素数量）
我们维护着呢！
empty() （判空）
不就是!_size 吗！
clear() （移除整棵树）
后序 dfs 遍历一次就 ok 了。（其实 bfs 也是可以的，但为了好写，我选择 dfs）
删除与失黑现象
千呼万唤始出来，犹抱琵琶半遮面。事实上，删除操作才是红黑树真正的难点。
首先先介绍删除的思路：一路找到被删除节点的真后继，然后回来覆盖原节点，如此反复。如上面 我们刚刚插入过 80 的红黑树，如果我们想删除根节点 49，那我们就要进行如下过程：（找到 49 的真后 继 58，覆盖 49；然后找到 58 的真后继 59，覆盖 58；然后删除 59 即可）
这个过程，我们最后删除的是红节点，所以并没有涉及失黑修正。如果我们最后删除的是黑节点（等 价 B-树的二节点），那么麻烦就来了：性质 6 就会被破坏。
失黑修正
正如前面讲到的，失黑修正有四种情况（根据父亲和兄弟颜色划分），而且失黑节点不像双红节点 一样可以比较容易地看出，所以这时就需要我们心中有 B-树了。为了方便，我们将需要递归的放在前两 种讲解。
LB-1 （父亲为黑色，兄弟为红色）
对于上面的红黑树，如果我们删除 59（其实删除 58 效果也一样，这里为了方便直接删除最终真后 继 59），那么就会出现破坏性质 6 的缺陷：
对于 LB-1，我们不能直接解决，但是我们可以利用一次旋转，触发递归深度为 1 的递归，将它转化 为不需要递归的 LB-2R 或者 LB-3：（这里转化成了 LB-3，方法是左旋父亲 60）
和 RR-2、LB-2 不同，这里的缺陷并没有上升，但是显然我们不需要进一步递归了，因为父亲变红了， 不会触发 LB-1、LB-2B 两个需要递归的修正了。
这里我们利用 LB-3 把这棵树修正好：（右旋兄弟 86、再左旋父亲 60，然后染黑 60，这个修正在后面会讲到）
如果删除 100 呢？同样会触发 LB-1 修正，只不过递归后会触发 LB-2R，此时按照 LB-2R 进行修正： （LB-1 过程：右旋 90，染红 90，染黑 80，转化为 LB-2R。LB-2R 过程：染红 86，染黑 90）
LB-2B （没有红色侄子，且父亲为黑色，兄弟为黑色）
显而易见，这时自己、父亲、兄弟都独占二节点。这是红黑树失黑修正过程中唯一可能出现对数递归的情况。这时要染红兄弟，然后递归修正父亲。
比如，上面的红黑树（删除了 86 的节点全黑红黑树），我们想再删除 23，就会触发递归深度为 3 的修正，全树黑高度-1：（第一次 LB-2B 过程：染红 34，转化为 LB-2B。第二次 LB-2B 过程：染红 80。第 三次 LB-2B 过程：递归到根节点 58，结束修正）
等价 B-树的变化如下：
LB-3 （有红色侄子）
LB-3 的情况在前面也有提到，修正方法是 1 或 2 次旋转，然后 1 或 2 次重染色。
例如，对于上面的红黑树，我又丧心病狂地删除了 25，就会触发 LB-3 修正：（左旋 58，染黑 90， 同时要注意维护根节点）
关于 B-树的强调贯穿了整个删除的讲解，因为对于理解失黑修正，等价 B-树太重要了。
两大修正的一些总结
不管是双红修正还是失黑修正，均涉及到重染色的操作，而其中 RR-1、LB-1、LB-3 均需要旋转，注 意维护根节点。
RR-2、LB-2B 分别对应着 B-树的上溢和下溢，均需要递归。
RR-2 能递归到 RR-0、RR-1、RR-2 三种双红修正情况中的任何一种，LB-2B 同样也会递归到 LB-1、LB-2B、 LB-2R、LB-3 四种失黑修正情况中的任何一种。
而同样是递归，LB-1 只能转移到 LB-2R 和 LB-3。
等价 B-树对于我们的理解也很重要，不要忽视。
其他推论
1.按照元素单调的顺序插入到红黑树可以得到偏红黑树（所有红节点在同一 枝上）或者其它根节点左右子树域之差较大的红黑树。
比如按顺序 1~14 插入，得到如下的右偏红黑树：
2.黑高度为 h 的偏红黑树，内部节点数最多为 ，此时树高为 2h， 从根出发的最短树链长度为 h，最长树链长度为 2h，根节点的左右子树域之
差的绝对值为 ，高度之差为 h。
总的来说，红黑树稳定，应用广，重点是快！
红黑树的源码：
#include <cstdio>
using namespace std;
#define bro(x) (((x)->ftr->lc == (x)) ? ((x)->ftr->rc) : ((x)->ftr->lc))
typedef bool RB_COLOR;
#define RB_COLOR_RED true
#define RB_COLOR_BLACK false
template <typename T>
class redblacktree {
protected:
struct RB_Node;
RB_Node* _root;
RB_Node* _hot;//维护父亲节点
int _size;
void init(T);
RB_Node* zig(RB_Node*);//左旋
RB_Node* zag(RB_Node*);//右旋
void SolveDoubleRed(RB_Node*);//双红修正
void SolveLostBlack(RB_Node*);//失黑修正
RB_Node* find(T);
void removetree(RB_Node*); //dfs后序遍历，删除整棵树
public:
struct iterator;
redblacktree() : _root(NULL), _hot(NULL), _size(0) {} //构造函数
iterator insert(T); //插入，返回插入的位置
bool remove(T);
bool remove(iterator&);
iterator search(T);
iterator lower_bound(T);//下届寻找 》=
iterator upper_bound(T);//上界寻找 >
void clear(); //dfs后序遍历入口
int size();
bool empty();
iterator begin();
static iterator end();
};
template <typename T>
struct redblacktree<T>::RB_Node {
T val;
RB_COLOR RBc;
RB_Node* ftr;
RB_Node* lc;
RB_Node* rc;
RB_Node(T v = T(), RB_COLOR RB = RB_COLOR_RED, RB_Node* f = NULL, RB_Node* lchild = NULL, RB_Node* rchild = NULL) :
val(v), RBc(RB), ftr(f), lc(lchild), rc(rchild) {}
RB_Node* succ() {//找到节点的真后继
RB_Node* ptn = rc;
while(ptn->lc) {
ptn = ptn->lc;
}
return ptn;
}
RB_Node* left_node() {//前驱
RB_Node* ptn = this;
if(!lc) {
while(ptn->ftr && ptn->ftr->lc == ptn) { //存在，且父亲的左儿子是自己
ptn = ptn->ftr;
}
ptn = ptn->ftr;
} else {
ptn = ptn->lc;
while(ptn->rc) {
ptn = ptn->rc;
}
}
return ptn;
}
RB_Node* right_node() { //后继
RB_Node* ptn = this;
if(!rc) {
while(ptn->ftr && ptn->ftr->rc == ptn) {
ptn = ptn->ftr;
}
ptn = ptn->ftr;
} else {
ptn = ptn->rc;
while(ptn->lc) {
ptn = ptn->lc;
}
}
return ptn;
}
};
template <typename T>
struct redblacktree<T>::iterator {
protected:
RB_Node* _real__node;
public:
T operator*() {
return _real__node->val;
}
bool operator==(iterator const& itr) {
return _real__node == itr._real__node;
}
bool operator!=(iterator const& itr) {
return _real__node != itr._real__node;
}
bool operator!() {
return !_real__node;
}
iterator& operator=(iterator const& itr) {
_real__node = itr._real__node;
return *this;//为了链式赋值
}
iterator& operator++() {//找到后继
_real__node = _real__node->right_node();
return *this;
}
iterator& operator--() {//找到前驱
_real__node = _real__node->left_node();
return *this;
}
iterator(RB_Node* node_nn = NULL) : _real__node(node_nn) {}
iterator(T const& val_vv) : _real__node(find(val_vv)) {}
iterator(iterator const& itr) : _real__node(itr._real__node) {}
};
template <typename T>
typename
redblacktree<T>::RB_Node* redblacktree<T>::find(T v) {
RB_Node* ptn = _root;
_hot = NULL;
while(ptn && ptn->val != v) {
_hot = ptn;
if(ptn->val > v) {
ptn = ptn->lc;
} else {
ptn = ptn->rc;
}
}
return ptn;
}
template <typename T>
typename
redblacktree<T>::iterator redblacktree<T>::search(T v) {
return iterator(find(v));
}
template <typename T>
typename
redblacktree<T>::iterator redblacktree<T>::lower_bound(T v) {
RB_Node* ptn = _root;
_hot = NULL;
while(ptn) {
_hot = ptn;
if(ptn->val >= v) {
ptn = ptn->lc;
} else {
ptn = ptn->rc;
}
}
if(_hot->val >= v) {
ptn = _hot;
} else {
ptn = _hot->right_node();
}
return iterator(ptn);
}
template <typename T>
typename
redblacktree<T>::iterator redblacktree<T>::upper_bound(T v) {
RB_Node* ptn = _root;
_hot = NULL;
while(ptn) {
_hot = ptn;
if(ptn->val > v) {
ptn = ptn->lc;
} else {
ptn = ptn->rc;
}
}
if(_hot->val > v) {
ptn = _hot;
} else {
ptn = _hot->right_node();
}
return iterator(ptn);
}
template <typename T>
void redblacktree<T>::init(T v) {
_root = new RB_Node(v, RB_COLOR_BLACK, NULL, NULL, NULL);
_size = 1;
}
template <typename T>
typename
redblacktree<T>::RB_Node* redblacktree<T>::zig(RB_Node* ptn) {
ptn->lc->ftr = ptn->ftr;
if(ptn->ftr) {
if(ptn->ftr->lc == ptn) {
ptn->ftr->lc = ptn->lc;
} else {
ptn->ftr->rc = ptn->lc;
}
}
if(ptn->lc->rc) {
ptn->lc->rc->ftr = ptn;
}
ptn->ftr = ptn->lc;
ptn->lc = ptn->lc->rc;
ptn->ftr->rc = ptn;
return ptn->ftr;
}
template <typename T>
typename
redblacktree<T>::RB_Node* redblacktree<T>::zag(RB_Node* ptn) {
ptn->rc->ftr = ptn->ftr;
if(ptn->ftr) {
if(ptn->ftr->lc == ptn) {
ptn->ftr->lc = ptn->rc;
} else {
ptn->ftr->rc = ptn->rc;
}
}
if(ptn->rc->lc) {
ptn->rc->lc->ftr = ptn;
}
ptn->ftr = ptn->rc;
ptn->rc = ptn->rc->lc;
ptn->ftr->lc = ptn;
return ptn->ftr;
}
template <typename T>
typename
redblacktree<T>::iterator redblacktree<T>::insert(T v) {
RB_Node* ptn = find(v);
if(ptn) {
return iterator(ptn);
}
if(!_hot) {
//assert(_size == 0);
init(v);
return iterator(_root);
}
++_size;
ptn = new RB_Node(v, RB_COLOR_RED, _hot, NULL, NULL);
if(_hot->val < v) {
_hot->rc = ptn;
} else {
_hot->lc = ptn;
}
SolveDoubleRed(ptn);
return iterator(ptn);
}
template <typename T>
void redblacktree<T>::SolveDoubleRed(RB_Node* nn) {
while(nn->ftr && nn->ftr->RBc == RB_COLOR_RED) { //排除递归到根和RR-0的情况
RB_Node* pftr = nn->ftr;
RB_Node* uncle = bro(pftr);
RB_Node* grdftr = pftr->ftr;
if(uncle && uncle->RBc == RB_COLOR_RED) { //RR-2
grdftr->RBc = RB_COLOR_RED;
uncle->RBc = RB_COLOR_BLACK;
pftr->RBc = RB_COLOR_BLACK;
nn = grdftr;
} else { //RR-1
if(grdftr->lc == pftr) {
if(pftr->lc == nn) {
if(grdftr == _root) {
_root = pftr;
}
zig(grdftr);
pftr->RBc = RB_COLOR_BLACK;
grdftr->RBc = RB_COLOR_RED;
} else {
if(grdftr == _root) {
_root = nn;
}
zag(pftr); zig(grdftr);
nn->RBc = RB_COLOR_BLACK;
grdftr->RBc = RB_COLOR_RED;
}
} else {
if(pftr->lc == nn) {
if(grdftr == _root) {
_root = nn;
}
zig(pftr); zag(grdftr);
nn->RBc = RB_COLOR_BLACK;
grdftr->RBc = RB_COLOR_RED;
} else {
if(grdftr == _root) {
_root = pftr;
}
zag(grdftr);
pftr->RBc = RB_COLOR_BLACK;
grdftr->RBc = RB_COLOR_RED;
}
}
return;
}
}
if(nn == _root) {
nn->RBc = RB_COLOR_BLACK;
}
}
template <typename T>
typename
redblacktree<T>::iterator redblacktree<T>::begin() {
RB_Node* ptn = _root;
while(ptn->lc) {
ptn = ptn->lc;
}
return iterator(ptn);
}
template <typename T>
typename
redblacktree<T>::iterator redblacktree<T>::end() {
return iterator((RB_Node*)NULL);
}
template <typename T>
int redblacktree<T>::size() {
return _size;
}
template <typename T>
bool redblacktree<T>::empty() {
return !_size;
}
template <typename T>
void redblacktree<T>::clear() {
removetree(_root);
_size = 0;
_root = NULL;
}
template <typename T>
void redblacktree<T>::removetree(RB_Node* ptn) {
if(!ptn) {
return;
}
removetree(ptn->lc);
removetree(ptn->rc);
delete ptn;
}
template <typename T>
void redblacktree<T>::SolveLostBlack(RB_Node* nn) {
while(nn != _root) {
RB_Node* pftr = nn->ftr;
RB_Node* bthr = bro(nn);
if(bthr->RBc == RB_COLOR_RED) { //LB-1
bthr->RBc = RB_COLOR_BLACK;
pftr->RBc = RB_COLOR_RED;
if(_root == pftr) {
_root = bthr;
}
if(pftr->lc == nn) {
zag(pftr);
} else {
zig(pftr);
}
bthr = bro(nn);
pftr = nn->ftr;
}
if(bthr->lc && bthr->lc->RBc == RB_COLOR_RED) { //LB-3
RB_COLOR oldRBc = pftr->RBc;
pftr->RBc = RB_COLOR_BLACK;
if(pftr->lc == nn) {
if(_root == pftr) {
_root = bthr->lc;
}
zig(bthr); zag(pftr);
} else {
bthr->lc->RBc = RB_COLOR_BLACK;
if(_root == pftr) {
_root = bthr;
}
zig(pftr);
}
pftr->ftr->RBc = oldRBc;
return;
} else if(bthr->rc && bthr->rc->RBc == RB_COLOR_RED) { //LB-3
RB_COLOR oldRBc = pftr->RBc;
pftr->RBc = RB_COLOR_BLACK;
if(pftr->lc == nn) {
bthr->rc->RBc = RB_COLOR_BLACK;
if(_root == pftr) {
_root = bthr;
}
zag(pftr);
} else {
if(_root == pftr) {
_root = bthr->rc;
}
zag(bthr); zig(pftr);
}
pftr->ftr->RBc = oldRBc;
return;
}
if(pftr->RBc == RB_COLOR_RED) { //LB-2R
pftr->RBc = RB_COLOR_BLACK;
bthr->RBc = RB_COLOR_RED;
return;
} else { //LB-2B
bthr->RBc = RB_COLOR_RED;
nn = pftr;
}
}
}
template <typename T>
bool redblacktree<T>::remove(T v) {
RB_Node* ptn = find(v);
RB_Node* node_suc;
if(!ptn) {
return false;
}
--_size;
while(ptn->lc || ptn->rc) {
if(!(ptn->lc)) {
node_suc = ptn->rc;
} else if(!(ptn->rc)) {
node_suc = ptn->lc;
} else {
node_suc = ptn->succ();
}
ptn->val = node_suc->val;
ptn = node_suc;
}
if(ptn->RBc == RB_COLOR_BLACK) {
SolveLostBlack(ptn);
}
if(ptn->ftr) {
if(ptn->ftr->lc == ptn) {
ptn->ftr->lc = NULL;
} else {
ptn->ftr->rc = NULL;
}
}
if(_root == ptn) {
//assert(_size == 0);
_root = NULL;
}
delete ptn;
return true;
}
template <typename T>
bool redblacktree<T>::remove(iterator& itr) {
RB_Node* ptn = itr._real__node;
itr._real__node = itr._real__node->right_node();
if(!(itr._real__node)) {
itr._real__node = ptn->left_node();
}
RB_Node* node_suc;
--_size;
while(ptn->lc || ptn->rc) {
if(!(ptn->lc)) {
node_suc = ptn->rc;
} else if(!(ptn->rc)) {
node_suc = ptn->lc;
} else {
node_suc = ptn->succ();
}
ptn->val = node_suc->val;
ptn = node_suc;
}
if(ptn->RBc == RB_COLOR_BLACK) {
SolveLostBlack(ptn);
}
if(ptn->ftr) {
if(ptn->ftr->lc == ptn) {
ptn->ftr->lc = NULL;
} else {
ptn->ftr->rc = NULL;
}
}
if(_root == ptn) {
_root = NULL;
}
delete ptn;
return true;
}
redblacktree<int> s;
#include <cstdlib>
#include <ctime>
int i;
int main() {
srand(time(NULL));
for(i = 0;i < 256;++i) {
s.insert(i);
}
redblacktree<int>::iterator it;
for(i = 0;i < 256;++i) {
s.remove(i);
}
return 0;
}
标签：Node,知识点,ftr,node,lc,ptn,源码,RB,红黑树 From： https://www.cnblogs.com/huwy-123/p/17613850.html