花了两天时间把红黑树总结了一下，可能还有错误，欢迎指正。后面附了C++实现代码。
目录
本文参考了以下博客：
https://www.cnblogs.com/skywang12345/p/3245399.html
https://www.cnblogs.com/skywang12345/p/3624291.html#a2
https://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html
https://www.cnblogs.com/qingergege/p/7351659.html
1. 介绍
R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。红黑树是一种弱平衡二叉查找树，平衡性不如AVL树严格，但其效率却更高，因为AVL树追求高度平衡性，插入删除操作时将进行大量的旋转调整操作，降低了效率。
红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。（不能有两个连续的红色节点）
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
注意：
特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接*衡的二叉树。
红黑树示意图如下：
红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。
2. 左旋及右旋
红黑树最基本的基本操作是添加、删除。在对红黑树进行添加或删除之后，红黑树就发生了变化，可能不再满足红黑树的5条性质，也就不再是一颗红黑树了，而是一颗普通的树，所以往往需要通过重新着色以及旋转等操作，使这颗树重新成为红黑树。
旋转包括两种：左旋 和 右旋。下面分别对它们进行介绍。
左旋：
对某个结点x做左旋操作时，假设其右孩子为y：以x到y的链为“支轴”进行。使y成为该子树新的根结点，x成为y的左孩子，y的左孩子成为x的右孩子
可以理解为，对节点X左旋，意味着将X变成一个左节点，其右节点Y变成其新的父节点
左旋伪代码：
y = x.right; //假设x的右儿子为y
x.right = y.left; //将 y的左儿子设为 x的右儿子
y.left.parent = x ; //y的左儿子的父节点 x
y.parent = x.parent; //原来x的父节点变成 y的父节点
if(x.parent == null) then tree_root = y; //此时x的父节点为空，y变成了根节点
else if(x == x.parent.left) then x.parent.left = y ; //更新父节点的指向
else x.parent.right = y ;
y.left = x ; //x变成y的左儿子
x.parent = y ; //y变成了x的父节点
c++ 实现：
template<class T, class K>
void MyRBTree<T, K>::leftRotate(RBTNode<T, K>* node)
{
RBTNode<T, K>* y = node->right;
node->right = y->left;
if(node->right)node->right->parent = node;
y->parent = node->parent;
if (y->parent == NULL) this->rootNode = y;
else if (y->parent->left == node) node->parent->left = y;
else node->parent->right = y;
y->left = node;
node->parent = y;
return;
}
右旋：
对某个结点x做右旋操作时，假设其左孩子为y，以x到y的链为“支轴”进行。使y成为该子树新的根结点，x成为y的右孩子，y的右孩子成为x的左孩子。
可以理解为：对节点X右旋，意味着将X变成一个右节点，其左节点Y变成其新的父节点
右旋伪代码：
y = x.left ; //假设x的左儿子为y
x.left = y.right ; //y的右儿子变成x的左儿子
x.left.parent = x ; //y的右儿子的父节点变成是x
y.parent = x.parent ; //x的父节点变成y的父节点
if(y.parent == null) then tree_root = y ; //如果x的父节点为空，现在y变成根节点
else if(y.parent.left == x) y.parent.left = y ; //更新父节点的指向
else y.parent.right = y ;
x.parent = y ; //y变成x的父节点
y.right = x ; //x变成y的右儿子
c++ 实现：
template<class T, class K>
void MyRBTree<T, K>::rightRotate(RBTNode<T, K>* node)
{
RBTNode<T, K>* y = node->left;
node->left = y->right;
if (node->left) node->left->parent = node;
y->parent = node->parent;
if (y->parent == NULL) this->rootNode = y;
else if (y->parent->left == node) y->parent->left = y;
else y->parent->right = y;
node->parent = y;
y->right = node;
return;
}
3. 插入
插入过程首先将红黑树当作一颗二叉查找树，将节点插入；然后，将节点着色为红色；最后，通过旋转和重新着色等方法来修正该树，使之重新成为一颗红黑树。
第一步: 将红黑树当作一颗二叉查找树，将节点插入。
红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，旋转之后它一定还是二叉查找树。这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一颗二叉查找树的事实。
第二步：将插入的节点着色为"红色"
回顾一下红黑树的五大特性：
(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
将插入的节点着色为红色，显然不会违反特性1、3、5，当插入的节点是红黑树的第一个节点时，这个节点成为根节点，直接置黑即可。所以插入新节点的过程往往最容易违反的是特性4（插入节点的父节点刚好也是红节点）。
插入节点伪代码insert(z)：
x = tree_root ; //从根节点开始找
y = new node ;
while(x) //找到新节点z应该插入的位置
{
y = x ;
if(z.key > x.key) x = x.right ;
else x = x.left ;
} //z将被插入到y的下方
z.parent = y ; //插入z
if(y == null) tree_root = z ;
else if(y.key > z.key) y.left = z ;
else y.right = z ;
z.color = red ; //新节点着色为红色
then insertFixUp(z); //调整使满足红黑树
C++实现：
template<class T, class K>
bool MyRBTree<T, K>::insertNode(RBTNode<T, K>* node)
{
if (node == NULL) return false;
RBTNode<T, K>* root = this->rootNode;
RBTNode<T, K>* parentNode = NULL; //待插入位置
while (root)
{
parentNode = root;
if (node->key > root->key) root = root->right;
else root = root->left;
}
node->parent = parentNode; //插入节点
if (parentNode == NULL)
{
this->rootNode = node; //父节点为空，当前节点为根节点
this->rootNode->color = BLACK;
}
else
{
if (parentNode->key > node->key) parentNode->left = node;
else parentNode->right = node;
}
insertNodeFixUp(node); //调整红黑树
return true;
}
第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。
第二步插入的操作显然不会违背前面三条特性，但可能违背第四条特性：插入的节点被着色为红色，如果这个节点的父节点也为红色，这个时候就需要对红黑树进行调整，使之重新成为红黑树。
根据被插入节点的父节点，可分为以下三种情况：
1. 被插入的节点是根节点（父节点为null）。
处理方法：直接把此节点涂为黑色。
2. 被插入的节点的父节点是黑色。
处理方法：什么也不需要做。节点被插入后，仍然是红黑树。
3. 被插入的节点的父节点是红色。
需要对红黑树进行调整。
此时违反了特性4。这种情况下，被插入节点是一定存在非空祖父节点的（父节点为红节点，必不是根节点）；进一步的讲，被插入节点也一定存在叔叔节点(即使叔叔节点为空，我们也视之为存在，空节点本身就是黑色节点)。理解这点之后，我们依据"叔叔节点的情况"，将这种情况进一步划分为3种Case。
图中都用N表示插入节点，P表示parent父节点，U表示uncle叔叔节点，G表示grandparent祖父节点。因为下面的不同CASE根据叔叔节点U进行分类，所以P和U谁是G的左儿子右儿子很重要，下面的图都以 P是G的左儿子为例，当P是G的右儿子时，情况类似。
CASE1：叔叔节点为红色
如上图，父节点和叔叔节点为红色，则祖父节点必为黑色，调整策略如下：
- 将父节点和叔叔节点置黑，祖父节点置红
- 将祖父节点作为入口节点，继续向上调整。（未结束）
当前节点”和“父节点”都是红色，违背“特性(4)” ==》将“父节点”设置“黑色” ==》 违背特性(5)，包含父节点P的分支多了一个黑节点 ==》将祖父节点置为红 ==》 叔叔节点为红色，违背特性(4) ==》再将叔叔节点置为黑色。此时，祖父节点以下的所有节点，都满足了红黑树特性，但是祖父节点自己却不一定满足，所以，将祖父节点作为入口节点，继续向上调整。
若此时，祖父节点是根节点，直接将祖父节点设为“黑色”，那就完全解决这个问题了；若祖父节点不是根节点，那我们需要将“祖父节点”设为“新的入口节点”，继续向上调整。
上图中P是G的左儿子，当P是右儿子，U是左儿子时，是一样的情况。
CASE2：叔叔节点为黑色，当前节点为叔叔节点的远侄子节点
如上图，P和N都为红节点，祖父节点G为黑节点，调整策略如下：
- 交换父节点，祖父节点颜色
- 以祖父节点为支点执行右旋（结束）
如上图，远侄子节点表示N位于离G较远的那一侧。
交换父节点P和祖父节点G颜色，解决了PN违反特性4的问题，同时未改变PN黑节点数量，但是导致了U分支黑节点减少一个（特性5），解决方法是，以G为支点右旋，将P旋转到当前子树的根节点位置，让P的黑色被左右子树共享。
上图中P是G左儿子，当P是右儿子，U是左儿子时，情况类似，将以祖父节点为支点右旋改为左旋即可。
CASE3：叔叔节点为黑色，当前节点为叔叔节点的近侄子节点
如上图，父节点为红色节点，则祖父节点必为黑色节点，策略如下：
- 以父节点为支点执行左旋
- 将P更新为新的入口节点，回到了CASE2(未结束)
如上图，以父节点为支点左旋之后，未改变黑节点数量。此时将父节点P视为新的入口节点，则回到了CASE2的情况，所以在执行一次CASE2即可。
当P是右儿子，U是左儿子，则对父节点P左旋改右旋即可。
|
|
特征 |
策略 |
后续 |
| CASE1 |
叔叔节点为红 |
父、叔节点与祖父节点交换颜色， 祖父节点作为新的入口节点 |
未结束 |
| CASE2 |
叔叔节点为黑，当前节点为远侄子 |
父节点、祖父节点交换颜色， 祖父节点右旋（左旋） |
结束 |
| CASE3 |
叔叔节点为黑，当前节点为近侄子 |
父节点左旋（右旋） 父节点作为新的入口节点 |
回到 CASE2 |
总结：三种情况下的核心思想都是先将红色节点上移，直到满足红黑树特性，或者将红色节点移到根节点，然后置黑。
当插入一个新的节点，首先将该节点置为红色节点，主要有以下三种情况：
- 当前节点的父节点为空，插入的新节点即为根节点，则直接将该节点置黑。
- 当前节点的父节点为黑，此时什么都不用做。
- 当前节点的父节点为红，此时违背了特性(4)，需要对该树进行调整，可继续分为三种情况：
1. 叔叔节点也为红。
此时祖父节点必为黑节点，所以先将父节点和叔叔节点置为黑，祖父节点置为红（红节点上移），此时局部以满足红黑树特性，但祖父节点却不一定满足，所以需要继续将祖父节点作为当前节点，继续向上调整。
2. 叔叔节点为黑，当前节点为叔叔节点的远侄子节点
当前节点和父节点都为红，违背了特性(4)，所以将父节点置黑，祖父节点置红（红节点上移），此时包含叔叔节点的分支黑节点数减少，违背了特性(5)，所以以祖父节点为支点执行右旋，让黑色的父节点成为当前子树新的根节点，黑色被左右子树共享。
3. 叔叔节点为黑，当前节点为叔叔节点的近侄子节点
当前节点和父节点都为红，违背了特性(4)，以父节点为支点执行左旋，相当于将当前节点进行了上移（红节点上移），然后将原父节点P视为当前节点，就回到了上面b的情况，继续执行b即可。
重新着色及旋转操作伪代码（insertFixUp(node)）：
While(node.parent != null && node.parent.color = red) //如果父节点存在且为红色
{
P = node.parent ; //父节点
if(P == P.parent.left)
{
U = Pt.right ; //叔叔节点
If(U.color == red) //CASE1
{
P.color = black ; //改变颜色
U.color = black ;
P.parent.color = red ;
node = P.parent ; //祖父节点作为新的入口节点
}
else if( node = P.left) //CASE2
{
P.color = black ; //调整颜色
P.parent.color = red ;
rightRotate(P.parent) ; //祖父节点支点右旋
return ;
}
else if( node = P.right) //CASE3
{
leftRotate(P) ;
node = P ;
}
else //error happened ?
}
else //P是其父节点的右儿子，与上面情况类似的
{ same as then clause with "right" and "left" exchanged }
}
tree_root.color = black; //1、2的情况，父节点为空，或者父节点为黑
c++ 实现：
template<class T, class K>
void MyRBTree<T, K>::insertNodeFixUp(RBTNode<T, K>* node)
{
RBTNode<T, K>* parentNode ;
while ((parentNode = node->parent) && parentNode->color == RED) //如果父节点存在且为红色
{
RBTNode<T, K>* gparent = parentNode->parent; //如果父节点存在且为红色，说明父节点不是root，所以必存在gparent
//如果父节点是左孩子
if (gparent->left == parentNode)
{
RBTNode<T, K>* uncle = gparent->right;
if (uncle && uncle->color == RED) //CASE1 叔叔节点为红
{
parentNode->color = BLACK;
gparent->color = RED;
uncle->color = BLACK;
node = gparent;
}
else if (node == parentNode->left) //CASE2 远侄子节点
{
parentNode->color = BLACK;
gparent->color = RED;
rightRotate(gparent);
return;
}
else if (node == parentNode->right) //CASE3 近侄子节点
{
leftRotate(parentNode);
node = parentNode;
}
else cout << " some thing error happend when INSERT !!!" << endl;
}
else //父节点是右孩子
{
RBTNode<T, K>* uncle = gparent->left;
if (uncle && uncle->color == RED) //CASE1
{
parentNode->color = BLACK;
gparent->color = RED;
uncle->color = BLACK;
node = gparent;
}
else if (node == parentNode->right) //CASE2 当前节点是远侄子
{
parentNode->color = BLACK;
gparent->color = RED;
leftRotate(gparent);
return;
}
else if (node == parentNode->left) //CASE3
{
rightRotate(parentNode);
node = parentNode;
}
else cout << " some thing error happend when INSERT !!!" << endl;
}
}
this->rootNode->color = BLACK; //当前调整节点为根节点，直接置黑即可
//当前节点父节点为黑，无需再调整
}
4. 删除
首先，将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除；然后，通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树
第一步：将红黑树当作一颗二叉查找树，将节点删除
这和"删除常规二叉查找树中删除节点的方法是一样的"。分3种情况：
① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。
② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。
③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。
在这里，后继节点相当于替身，在将后继节点的内容复制给"被删除节点"之后，再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了，下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然"后继节点"不可能双子都非空，就意味着"该后继节点"要么没有儿子，要么只有一个儿子。若没有儿子，则按"情况① "进行处理；若只有一个儿子，则按"情况② "进行处理。
总结起来就是，如果删除节点z存在空子节点，则y=z，y被删除，然后y的子节点x替换到y的位置。如果删除节点z双子非空，则将后继点y的值覆盖z，然后删除后继点y
删除元素伪代码delete(z)：
y = z ; //y是将被真正删除的节点
if(z.left && z.right) //z左右子节点都不为空
then y = nextNode(zs) //y为x的后继节点
if(y.left) x = y.left ; //此时的y必存在null子节点
else x = y.right ; //x是y节点的儿子节点
if(y != z) //说明y不是z本身，而是一个后继节点
then { copy y's satellite data into z } //将y的相关信息覆盖到z，不包括红黑颜色
//后面需要做的就是将y节点删除
x.parent = y.parent ;
if(y.parent == null) then tree_root = x ; //删除的y是根节点
else if(y.parent.left = y) y.parent.left = x ; //将x向前移动，将y从树上摘下
else y.parent.right = x ;
if(y.color == black) deleteFixUp(x) ; //如果删除的节点y是红节点，未改变红黑树特性
//如果删除的节点y是黑节点，则需要重新调整
C++ 实现：
template<class T, class K>
bool MyRBTree<T, K>::removeNode(RBTNode<T, K>* node)
{
if (node == NULL) return false;
RBTNode<T, K>* child, *parentNode;
RBTNode<T, K>* deleteNode = node;
if (node->left && node->right) //左右子节点都不为null
{
//寻找后继节点, 即大于node的最小值
deleteNode = node->right;
while (deleteNode->left) deleteNode = deleteNode->left;
}
if (deleteNode != node) //需要删除的是后继节点
{
node->key = deleteNode->key;
node->value = deleteNode->value;
}
//接下来就是删除掉deleteNode
parentNode = deleteNode->parent;
//deleteNode 不可能左右节点都不为null
if (deleteNode->left) child = deleteNode->left;
else child = deleteNode->right;
if (child) child->parent = parentNode;
if (parentNode == NULL) rootNode = child;
else
{
if (deleteNode == parentNode->left) parentNode->left = child;
else parentNode->right = child;
}
//被删除的是黑节点，则需要调整红黑树
if (deleteNode->color == BLACK) removeFixUp(child, parentNode); //传两个参数主要是因为child可能为null（被删除节点没有子节点）
//parentNode 可能为空（被删除节点为根节点）
delete deleteNode;
return true;
}
第二步：通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。
因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树，使之重新成为一棵红黑树。
是否需要调整红黑树由真正删除的节点y及y的子节点x决定：
如果y是红节点，删除后红黑树性质未发生改变，所以不需要调整
当y是黑节点，根据x的情况决定如何调整：（y被删除，x替换他的位置，导致包含x的分支少了一个黑节点，失去平衡）
- x 是根节点，直接置黑即可
- x 是红节点，直接将x置黑即可
- x是黑节点，分为以下四种情况讨论：（x和y都是黑节点s）
（x对应下图中的N代表第一步中被删掉的节点y的子节点，包含N分支都少了一个黑节点）不同的CASE按照兄弟节点S分类，所以N和谁是P的左右节点是不同的情况，但类似。对以下五种CASE分类的规律在于，兄弟节点的颜色，再看侄子节点的颜色（侄子节点先看远侄子再看近侄子），最后看父亲节点的颜色
CASE 1： N兄弟节点是红色 （红）
此时，N的父节点P和N的兄弟节点S的子节点（侄子节点）都是黑节点
N是一个黑节点，且N的支路还少一个黑节点，所以兄弟节点S必不可能为null。
调整策略：
- 父节点和兄弟节点（P、S）颜色互换
- 以父节点P为支点左旋（未结束）
操作完成之后，所有分支的黑节点数都没有发生改变，只是N的兄弟节点变成了黑色，变成后面要讨论的情况。进入下一次调整，入口节点仍为N，包含N的分支仍少一个黑节点。
当N为P的右儿子，S为左儿子，左旋改右旋即可。
CASE2：N的兄弟节点为黑色，远侄子节点为红色
没有上色的节点表示黑色红色均可 。
调整策略：
- P和S 颜色对调，
- 以P为支点左旋
- 将SR置黑（结束）
包含N的分支少了一个黑节点，注意到S的子节点有红节点，核心思想是将这个红色的节点移到Ns的上方，并置为黑节点，即满足了要求。（所以P的颜色无关，因为旋转前后P的位置上的节点颜色不变）。
相当于是P的位置上颜色一直没有改变，将P的右子节点（黑）移到了左子节点，N的上方，此时N的分支多了一个黑节点，满足了要求，而P的右子节点分支少了一个黑节点，所以又将SR置黑。
当N为P右儿子，S为左儿子，不仅要将左旋改右旋，还要注意，此时的远侄子不再是SR，而时SL，所以，第三步置黑的是SL 。
CASE3: 兄弟节点S为黑色，远侄子节点为黑色，近侄子节点为红色
调整策略：
- 将S和近侄子SL颜色互换
- 以S为支点右旋（未结束）
这个过程相当于将近侄子的颜色移到了远侄子的位置，因为是红色，所以对黑节点数量没有影响，最终变成了CASE2，继续调整。
上图虽未画出N和P，但仍表示N为P左儿子，S为右儿子（因为近侄子是SL，所以N在左）。
当N在右，S在左时，要特别注意，近侄子就变成了SR，右旋也要改左旋。
调整策略：
- 将S和近侄子SL颜色互换
- 以S为支点左旋（未结束）
CASE4：兄弟节点和两个侄子节点都为黑色的情况，父亲节点P为红色。
调整策略：
- 将P置黑
- 将S置红（结束）
这是最简单的一种情况，N的支路少了一个黑节点，因此将P置黑，这又导致了S支路多了一个黑节点，因此再将S置红。
CASE5: 兄弟节点和两个侄子节点都为黑色的情况，父亲节点P 也为黑色
调整策略：
- 将S 置为红节点
2 将P作为新的起始节点，重新调整（未结束）
N的支路上少了一个黑节点，因此将S置为红色，此时P的左右支路都少了一个黑节点，也就是需要在P的支路上再添加一个黑节点，所以将P作为新的起始点，重新进入调整。
总结一下，一共五种情况：
|
|
特征 |
操作 |
后续 |
| CASE1 |
S红 |
P、S颜色互换，P左旋（右旋） |
未结束 |
| CASE2 |
S黑，远侄子红 |
P、S颜色互换，P左旋（右旋），远侄子置黑 |
结束 |
| CASE3 |
S黑，远侄子黑，近侄子红 |
S、近侄子颜色互换，S右旋（左旋） |
未结束(CASE2） |
| CASE4 |
S黑，远近侄子黑，父节点P红 |
P、S颜色互换 |
结束 |
| CASE5 |
S黑，远近侄子黑，父节点P黑 |
将S置红，将P作为起始点 |
未结束 |
判断类型的时候，先看兄弟节点的颜色，再看侄子节点的颜色（侄子节点先看远侄子再看近侄子），最后看父亲节点的颜色。这样就简单多了
伪代码 deleteFixUp(x):
While( x != tree_root && ( x != null || x.color == black)) //x不是根节点，且不是红节点
{
If(x == x.parent.left) //x是左节点
{
P = x.parent ; //父节点
S = P.right； //兄弟节点
If(S.color == red ) //CASE1
{
P.color = red ;
S.color = black ;
leftRotate( P ) ;
}
else if( S.right.color == red ) //CASE2
{
S.color == P.color ;
P.color = black ;
leftRotate( P ) ;
S.right.color = black ;
Return ;
}
else if ( S.left.color == red) //CASE3
{
S.color = red ;
S.left.color = black ;
rightRotate( S ) ;
}
else if( P.color == red ) //CASE4
{
P.color = black ;
S.color = red ;
Return ;
}
else if( P.color == black) //CASE5
{
S.color = red ;
x = P ;
}
else “some thing error happened? “ s
}
else //x 是右节点
{ same as then clause with "right" and "left" exchanged }
}
If(x != null ) x.color = black ; //x如果是根节点或者是红节点，直接置黑完事
C++ 代码：
template<class T, class K>
void MyRBTree<T, K>::removeFixUp(RBTNode<T, K>* node, RBTNode<T, K>* parentNode)
{
RBTNode<T,K>* bro;
while (node != rootNode && (!node || node->color == BLACK)) //node不是根节点，且不是红节点,null视为黑节点
{
if (node == parentNode->left)
{
bro = parentNode->right;
if (bro->color == RED) // CASE1 兄弟节点bro不可能为空
{
bro->color = BLACK;
parentNode->color = RED;
leftRotate(parentNode);
}
else if (bro->right && bro->right->color == RED) //CASE2
{
bro->color = parentNode->color;
parentNode->color = BLACK;
leftRotate(parentNode);
bro->right->color = BLACK;
return;
}
else if (bro->left && bro->left->color == RED) //CASE3
{
bro->color = RED;
bro->left->color = BLACK;
rightRotate(bro);
}
else if (parentNode->color == RED) //CASE 4
{
parentNode->color = BLACK;
bro->color = RED;
return;
}
else if (parentNode->color == BLACK) //CASE5
{
bro->color = RED;
node = parentNode;
parentNode = node->parent;
}
else
{
cout << "some thing error happend !!!";
return;
}
}
else //node = parent->right
{
bro = parentNode->left;
if (bro->color == RED) // CASE1
{
bro->color = BLACK;
parentNode->color = RED;
rightRotate(parentNode);
}
else if (bro->left && bro->left->color == RED) //CASE2
{
bro->color = parentNode->color;
parentNode->color = BLACK;
rightRotate(parentNode);
bro->left->color = BLACK;
return;
}
else if (bro->right && bro->right->color == RED) //CASE3
{
bro->color = RED;
bro->right->color = BLACK;
leftRotate(bro);
}
else if (parentNode->color == RED) //CASE 4
{
parentNode->color = BLACK;
bro->color = RED;
return;
}
else if (parentNode->color == BLACK) //CASE5
{
bro->color = RED;
node = parentNode;
parentNode = node->parent;
}
else
{
cout << "some thing error happend !!!";
return;
}
}
}
if (node) node->color = BLACK;
}
红黑树复杂一点的就是插入和删除了，最后贴一下完整代码吧：
实现代码：
#pragma once
#include <iostream>
#include <string>
#include <queue>
using namespace std;
enum RBColor {RED , BLACK};
template<class T , class K>
class RBTNode
{
public:
RBColor color; //节点颜色
T key; //键
K value; //值
RBTNode* left; //左儿子
RBTNode* right; //右儿子
RBTNode* parent; //父节点
RBTNode(T _key, K _value , RBColor _color = RED) :key(_key), value(_value), color(_color), left(NULL), right(NULL), parent(NULL) {}
};
template <class T , class K>
class MyRBTree
{
RBTNode<T , K>* rootNode;
public:
MyRBTree() :rootNode(NULL) {}
~MyRBTree();
RBTNode<T, K>* find(T _key ); //查找key对应的节点
bool insertNode(T _key , K _value); //插入节点
bool removeNode(T key); //删除一个节点
void printTree() const;
private:
//左旋
void leftRotate(RBTNode<T, K>* node);
//右旋
void rightRotate(RBTNode<T, K>* node);
bool insertNode(RBTNode<T , K>* node); //插入节点
void insertNodeFixUp(RBTNode<T, K>* node); //调整红黑树
bool removeNode(RBTNode<T, K>* node); //删除一个节点
void removeFixUp(RBTNode<T, K>* node, RBTNode<T, K>* parentNode);
void destroy(RBTNode<T,K>* node);
void inOrder() const; //中序遍历
//const 表示成员函数隐含传入的this指针为const指针，决定了在该成员函数中，任意修改它所在的类的成员的操作都是不允许的（因为隐含了对this指针的const引用）
};
/*
* 对红黑树的节点(x)进行左旋转
*
* 左旋示意图(对节点x进行左旋)：
* px px
* / /
* x y
* / \ --(左旋)--> / \ #
* lx y x ry
* / \ / \
* ly ry lx ly
*
*
*/
template<class T, class K>
void MyRBTree<T, K>::leftRotate(RBTNode<T, K>* node)
{
RBTNode<T, K>* y = node->right;
node->right = y->left;
if(node->right)node->right->parent = node;
y->parent = node->parent;
if (y->parent == NULL) this->rootNode = y;
else if (y->parent->left == node) node->parent->left = y;
else node->parent->right = y;
y->left = node;
node->parent = y;
return;
}
/*
* 对红黑树的节点(y)进行右旋转
*
* 右旋示意图(对节点y进行右旋)：
* px px
* / /
* x y
* / \ --(右旋)--> / \ #
* y rx ly x
* / \ / \ #
* ly ry ry rx
*
*/
template<class T, class K>
void MyRBTree<T, K>::rightRotate(RBTNode<T, K>* node)
{
RBTNode<T, K>* y = node->left;
node->left = y->right;
if (node->left) node->left->parent = node;
y->parent = node->parent;
if (y->parent == NULL) this->rootNode = y;
else if (y->parent->left == node) y->parent->left = y;
else y->parent->right = y;
node->parent = y;
y->right = node;
return;
}
template<class T, class K>
bool MyRBTree<T, K>::insertNode(RBTNode<T, K>* node)
{
if (node == NULL) return false;
RBTNode<T, K>* root = this->rootNode;
RBTNode<T, K>* parentNode = NULL; //待插入位置
while (root)
{
parentNode = root;
if (node->key > root->key) root = root->right;
else root = root->left;
}
node->parent = parentNode; //插入节点
if (parentNode == NULL)
{
this->rootNode = node; //父节点为空，当前节点为根节点
this->rootNode->color = BLACK;
}
else
{
if (parentNode->key > node->key) parentNode->left = node;
else parentNode->right = node;
}
insertNodeFixUp(node); //调整红黑树
return true;
}
template<class T, class K>
void MyRBTree<T, K>::insertNodeFixUp(RBTNode<T, K>* node)
{
RBTNode<T, K>* parentNode ;
while ((parentNode = node->parent) && parentNode->color == RED) //如果父节点存在且为红色
{
RBTNode<T, K>* gparent = parentNode->parent; //如果父节点存在且为红色，说明父节点不是root，所以必存在gparent
//如果父节点是左孩子
if (gparent->left == parentNode)
{
RBTNode<T, K>* uncle = gparent->right;
if (uncle && uncle->color == RED) //CASE1 叔叔节点为红
{
parentNode->color = BLACK;
gparent->color = RED;
uncle->color = BLACK;
node = gparent;
}
else if (node == parentNode->left) //CASE2 远侄子节点
{
parentNode->color = BLACK;
gparent->color = RED;
rightRotate(gparent);
return;
}
else if (node == parentNode->right) //CASE3 近侄子节点
{
leftRotate(parentNode);
node = parentNode;
}
else cout << " some thing error happend when INSERT !!!" << endl;
}
else //父节点是右孩子
{
RBTNode<T, K>* uncle = gparent->left;
if (uncle && uncle->color == RED) //CASE1
{
parentNode->color = BLACK;
gparent->color = RED;
uncle->color = BLACK;
node = gparent;
}
else if (node == parentNode->right) //CASE2 当前节点是远侄子
{
parentNode->color = BLACK;
gparent->color = RED;
leftRotate(gparent);
return;
}
else if (node == parentNode->left) //CASE3
{
rightRotate(parentNode);
node = parentNode;
}
else cout << " some thing error happend when INSERT !!!" << endl;
}
}
this->rootNode->color = BLACK; //当前调整节点为根节点，直接置黑即可
//当前节点父节点为黑，无需再调整
}
template<class T, class K>
bool MyRBTree<T, K>::removeNode(RBTNode<T, K>* node)
{
if (node == NULL) return false;
RBTNode<T, K>* child, *parentNode;
RBTNode<T, K>* deleteNode = node;
if (node->left && node->right) //左右子节点都不为null
{
//寻找后继节点, 即大于node的最小值
deleteNode = node->right;
while (deleteNode->left) deleteNode = deleteNode->left;
}
if (deleteNode != node) //需要删除的是后继节点
{
node->key = deleteNode->key;
node->value = deleteNode->value;
}
//接下来就是删除掉deleteNode
parentNode = deleteNode->parent;
//deleteNode 不可能左右节点都不为null
if (deleteNode->left) child = deleteNode->left;
else child = deleteNode->right;
if (child) child->parent = parentNode;
if (parentNode == NULL) rootNode = child;
else
{
if (deleteNode == parentNode->left) parentNode->left = child;
else parentNode->right = child;
}
//被删除的是黑节点，则需要调整红黑树
if (deleteNode->color == BLACK) removeFixUp(child, parentNode); //传两个参数主要是因为child可能为null（被删除节点没有子节点）
//parentNode 可能为空（被删除节点为根节点）
delete deleteNode;
return true;
}
template<class T, class K>
void MyRBTree<T, K>::removeFixUp(RBTNode<T, K>* node, RBTNode<T, K>* parentNode)
{
RBTNode<T,K>* bro;
while (node != rootNode && (!node || node->color == BLACK)) //node不是根节点，且不是红节点,null视为黑节点
{
if (node == parentNode->left)
{
bro = parentNode->right;
if (bro->color == RED) // CASE1 兄弟节点bro不可能为空
{
bro->color = BLACK;
parentNode->color = RED;
leftRotate(parentNode);
}
else if (bro->right && bro->right->color == RED) //CASE2
{
bro->color = parentNode->color;
parentNode->color = BLACK;
leftRotate(parentNode);
bro->right->color = BLACK;
return;
}
else if (bro->left && bro->left->color == RED) //CASE3
{
bro->color = RED;
bro->left->color = BLACK;
rightRotate(bro);
}
else if (parentNode->color == RED) //CASE 4
{
parentNode->color = BLACK;
bro->color = RED;
return;
}
else if (parentNode->color == BLACK) //CASE5
{
bro->color = RED;
node = parentNode;
parentNode = node->parent;
}
else
{
cout << "some thing error happend !!!";
return;
}
}
else //node = parent->right
{
bro = parentNode->left;
if (bro->color == RED) // CASE1
{
bro->color = BLACK;
parentNode->color = RED;
rightRotate(parentNode);
}
else if (bro->left && bro->left->color == RED) //CASE2
{
bro->color = parentNode->color;
parentNode->color = BLACK;
rightRotate(parentNode);
bro->left->color = BLACK;
return;
}
else if (bro->right && bro->right->color == RED) //CASE3
{
bro->color = RED;
bro->right->color = BLACK;
leftRotate(bro);
}
else if (parentNode->color == RED) //CASE 4
{
parentNode->color = BLACK;
bro->color = RED;
return;
}
else if (parentNode->color == BLACK) //CASE5
{
bro->color = RED;
node = parentNode;
parentNode = node->parent;
}
else
{
cout << "some thing error happend !!!";
return;
}
}
}
if (node) node->color = BLACK;
}
template<class T, class K>
MyRBTree<T, K>::~MyRBTree()
{
destroy(this->rootNode);
}
template<class T, class K>
RBTNode<T, K>* MyRBTree<T, K>::find(T _key)
{
if (rootNode == NULL) return NULL;
queue<RBTNode<T, K>* > tempQueue;
tempQueue.push(this->rootNode);
RBTNode<T, K>* node;
while (!tempQueue.empty())
{
node = tempQueue.front();
if (node->key == _key) return node;
if (_key > node->key && node->right) tempQueue.push(node->right);
else if (node->left) tempQueue.push(node->left);
tempQueue.pop();
}
return NULL;
}
//插入一个新节点，如果已存在，则更新value值
template<class T, class K>
bool MyRBTree<T, K>::insertNode(T _key , K _value)
{
RBTNode<T, K>* node = find(_key);
if (node) node->value = _value;
else
{
node = new RBTNode<T, K>(_key, _value, RED);
return insertNode(node);
}
return true;
}
template<class T, class K>
bool MyRBTree<T, K>::removeNode(T key)
{
RBTNode<T, K>* node = find(key);
if (node == NULL) return false;
return removeNode(node);
}
template<class T, class K>
void MyRBTree<T, K>::printTree() const
{
inOrder();
}
template<class T, class K>
void MyRBTree<T, K>::destroy(RBTNode<T,K>* node)
{
if (node == NULL) return;
destroy(node->left);
destroy(node->right);
delete node;
}
//前序输出红黑树所有节点
template<class T, class K>
void MyRBTree<T, K>::inOrder() const
{
queue<RBTNode<T,K>*> tempQue;
if (rootNode == NULL) return;
tempQue.push(rootNode);
RBTNode<T, K>* node;
cout << endl;
while (!tempQue.empty())
{
node = tempQue.front();
cout << node->key << ends;
if (node->left) tempQue.push(node->left);
if (node->right) tempQue.push(node->right);
tempQue.pop();
}
cout << endl;
}
简单测试下：
#include "MyRBTree.h"
#include <iostream>
#include <string>
using namespace std;
int main()
{
int a[] = { 10, 40, 30, 60, 90, 70, 20, 50, 80 };
int ilen = (sizeof(a)) / (sizeof(a[0]));
MyRBTree<int, string>* tree = new MyRBTree<int , string>();
cout << "== 原始数据: ";
for (int i = 0; i < ilen; i++)
cout << a[i] << " ";
cout << endl;
for (int i = 0; i < ilen; i++)
{
cout << endl << "insert a node : " << a[i] ;
tree->insertNode(a[i], to_string(a[i]));
tree->printTree();
}
for (int i = 0; i < ilen; i++)
{
cout << endl << "delete a node : " << a[i] ;
tree->removeNode(a[i]);
tree->printTree();
}
// 销毁红黑树
tree->~MyRBTree();
return 0;
}