平衡搜索树——红黑树）
首先，在了解红黑树之前我们应该知道平衡搜索树是一种进阶版的二叉搜索树。可是，普通的二叉搜索树在进行插入，删除等操作时，虽然在树高较低时执行的很快。然而，如果树的高度较高时，执行效率可能并没有链表高。前人们为解决此问题，便有人提出了使搜索树平衡的想法。此后，便出现了各种使搜索树平衡的算法，红黑树便是其中的一种， 它可以保证在最坏情况下进行基本动态集合操作的时间复杂度为O(lgn)。
一.红黑树的性质
1.红黑树的基本性质
每棵红黑树都应该满足下面五条性质：
1.每个结点都是红色或黑色的。
2.根节点是黑色的。
3.每个叶节点都是黑色的。
4.如果一个结点是红色的，则它的两个结点都是黑色的。
5.对每个结点，从该结点到其所有后代叶节点的简单路径上，均包含相同数目的黑色结点。
下面为了便于处理，我们接下来红色结点将不涂色，我们会将上图的NIL用一个哨兵T.nil来代替。这个哨兵是一个拥有和树中其它结点相同属性的对象。它的color属性为BLACK，其它可以设为随意值。
2.红黑树为何可以将时间复杂度降为O(lgn)
在开始证明之前，我们先知道几个概念：
1.从某个结点出发(不含这个结点)到达一个叶节点的任意一条简单路径上的黑色结点个数称为该结点的黑高，记为bh(x)。
2.在算法领域，对时间复杂度的探讨只是探讨量级，常数是忽略掉的。
经过前人对红黑树的大量研究，发现了一个规律，以节点x为根结点的子树，至少包含2bh(x) - 1 个内结点。 可是规律是不能直接拿来用的，我们需要先把它证明出来。
证明过程:
- 首先，如果x的高度为0，则x必定为叶节点(NIL),并且以x为根节点的子树至少包含2bh(x) - 1 = 0 个内部结点。
- 接下来，考虑一个高度为正值且有两个子结点的内部结点x。我们可以知道x的左右子树的黑高，要么是bh(x)，要么是bh(x) - 1。这取决与子结点本身的颜色是红还是黑。我们利用归纳假设就可以得到每个子结点至少有2bh(x)-1 - 1个内部结点。 那么我们就可以得到以x为根的子树至少包含 (2bh(x)-1 - 1) + (2bh(x)-1 - 1) + 1 = 2bh(x) - 1。
现在，我们已经证明了这个规律是正确的。
接下来，我们来用这个定理来证明为什么红黑树可以将时间复杂度降为O(lgn)。
根据性质4，从根到叶结点(不包含根结点)的任意一条简单路径上都至少会有一半是黑色结点，所以，可以得到黑高至少为h/2，则可以得到n >= 2h/2 - 1。变形一下就可以得到h <= 2lg(n + 1)。
我们知道，二叉树的动态集合操作所需要时间与树高有关。所以，包含n个结点的红黑树的时间复杂度为O(lgn)。
可是，我们发现在我们直接进行普通二叉搜索树的插入和删除操作时会打乱红黑树，使得这个二叉树不再满足红黑树的性质。那么，为了让修改过的二叉树仍然使红黑树，我们就需要改进插入和删除的操作。
那么，我们应该怎么解决呢？答案是：我们要去改变树中某些结点的颜色以及指针结构。
二.维护红黑树
1.旋转
我们要进行指针结构的修改，那是绕不开旋转的。这种操作可以始终保持二叉搜索树的性质。
旋转操作分为左旋和右旋。
- 左旋：以x到y的链为支轴进行，让y成为该子树新的根结点，x成为y的左子树，y的左子树变为x的右子树。
- 右旋：以y到x的链为支轴进行，让x成为该子树新的根结点，y成为x的右子树，x的右子树变为y的左子树。
//左旋示意图(对结点x进行左旋)：
// px px
// / /
// x p
// / \ --(左旋)--> / \
// lx p x rp
// / \ / \
// lp rp lx lp
template<class T>
void RbTree<T>::Left_rotation(RbTreeNode<T>* &root, RbTreeNode<T> *x)
{
RbTreeNode<T> *p = x->right;
x->right = p->left;
if(p->left != nil)
{
p->left->parent = x;
}
p->parent = x->parent;
if(x->parent == nil)
{
root = p;
}
else
{
if(x->parent->left == x)
{
x->parent->left = p;
}
else
{
x->parent->right = p;
}
}
x->parent = p;
p->left = x;
}
// 右旋示意图(对结点y进行左旋)：
// py py
// / /
// y p
// / \ --(右旋)--> / \
// p ry lp y
// / \ / \
// lp rp rp ry
template<class T>
void RbTree<T>::Right_rotation(RbTreeNode<T>* &root, RbTreeNode<T> *y)
{
RbTreeNode<T> *p = y->left;
y->left = p->right;
if(p->right != nil)
{
p->right->parent = y;
}
p->parent = y->parent;
if(y->parent != nil)
{
if(y->parent->left = y)
{
y->parent->left = p;
}
else
{
y->parent->right = p;
}
}
else
{
root = p;
}
p->right = y;
y->parent = p;
}
2.插入
首先，红黑树的结点是有颜色的。那么，我们在插入一个新的结点的时候，这个结点应该是什么颜色呢？
- 我们假设这个插入结点的颜色为黑色，那么我们会使得性质5发生了改变，而且是绝对会发生改变。
- 我们假设这个插入结点的颜色为红色，我们发现只有当这个结点的父结点为红色结点时才会使得性质4发生了改变或者当这个树本身为空时违背了性质2。
通过假设我们可以看到，当插入结点的颜色为红色时对红黑树的影响最小。那么，我们就将插入结点的颜色设为红色吧。
这样红黑树的查找插入位置的函数就要将二叉搜索树的代码改动一下。
- 红黑树有父结点的属性，所以我们要将插入结点的父结点进行指定(为空则指向哨兵)。
- 由于红黑树插入结点有可能导致性质被破坏，所以在最后我们需要一个修正函数来维护红黑树。
//将结点x插入到红黑树中
template<class T>
void RbTree<T>::iinsert(RbTreeNode<T>* &r, RbTreeNode<T>* &x)
{
RbTreeNode<T> *y = nil; //用来记录插入结点的父结点
RbTreeNode<T> *z = r;
while(z != nil) //查找插入位置
{
y = z;
if(x->key < z->key)
{
z = z->left;
}
else
{
z = z->right;
}
}
x->parent = y;
if(y == nil)
{
r = x;
}
else if(x->key < y->key)
{
y->left = x;
}
else
{
y->right = x;
}
x->left = nil;
x->right = nil;
iinsert_fixup(r, x); //插入修正函数
}
template<class T>
void RbTree<T>::iinsert(T key)
{
RbTreeNode<T> *z = nil;
if((z = new RbTreeNode<T>(RED,key,nil, nil,nil)) == nil)
{
return;
}
iinsert(Root, z);
}
2.1 什么时候修复
下面，我们来探讨一下会有哪些情况导致红黑树的性质被破坏。
- 如果我们的树本来就为空的话，我们插入后破坏了性质2。
- 如果插入结点的父结点为黑色结点的话，我们发现红黑树的性质并没有被破坏。
- 如果插入结点的父结点为红色结点的话，我们发现红黑树的性质4被破坏了。并且此时叔叔结点颜色非红则为哨兵(如果为实际的黑色结点的话，插入前就已经违反了性质5)以及父结点在插入结点前没有孩子结点
好的，现在我们初步的知道了当出现情况1和情况3时，我们的红黑树性质发生了改变。情况1比较简单，方法我直接写了出来。我们主要分析情况3。
为了方便讨论，我们规定将插入结点设为i, 插入结点的父结点设为p，插入结点的祖父结点为pp，插入结点的叔叔结点为s。
这种情况下我们已经知道i，p，pp(因为p为红色，则pp只能为黑色)的颜色，那么我们操作的不同只与p与pp的位置和s有关。
既然pp的颜色已经知道，那么p与pp间只用考虑p是pp的右孩子还是左孩子。这导致的结果其实就是两种情况下操作是对称的，所以在下文中我们只讨论p为pp的左孩子的情况。
2.2 怎么去修复
2.2.1 树为空
这种情况下，我们直接将插入结点设为根结点，并将颜色设置为黑色。
2.2.2 当s是红色结点时
当这种情况时，我们无论怎么改变指针结构并改变颜色都会违反性质。由于只改变指针结构肯定错误，所以只能从颜色下手。
这种情况下s、p、i的颜色都为红色。那么我们将p和s变为黑色、pp变为红色。此时，由于pp变为红色可能会破坏pp上面的红黑树，我们应该将pp设置为i再进行一次情况判断进行维护。
2.2.3 s为黑色结点，且i为p的左孩子
当这种情况下。我们发现此时叔叔结点为哨兵，那么我们是可以通过旋转来使得3层树变为2层树的。对于2层树的话，我们只需要保证这段树的根结点为黑色结点，其它为红色结点的话便维护好了红黑树，并且不会破坏上面的树。
变为具体操作便是：先将pp设为红色，p设为黑色，然后以pp到p的支链进行右旋。
2.2.4 s为黑色结点，且i为p的右孩子
对于这种情况，由于i为p的右孩子，所以我们没有办法通过一次旋转就将树的层级减少。那既然一次不行，那就两次嘛。我们很轻易就能看出来，p和i都是红色结点的话，那么它们俩之间进行指针结构的变化也没差。这样看来，这种情况我们可以以p到i的支链进行左旋后变为2.3的情况后再进行2.3的操作。
template<class T>
void RbTree<T>::iinsert_fixup(RbTreeNode<T>* &root, RbTreeNode<T> *x)
{
RbTreeNode<T> *parent, *gparent;
while((parent = x->parent) && parent->color == RED) //父结点存在且为红色
{
gparent = parent->parent;
if(gparent->left == parent) //父结点为祖父结点的左孩子
{
RbTreeNode<T> *uncle = gparent->right;
//叔叔结点存在且为红色结点 ——> 将父亲结点和叔叔结点设为黑色，祖父结点设为红色，将祖父结点设为插入结点
if(uncle && uncle->color == RED)
{
parent->color = BLACK;
uncle->color = BLACK;
gparent->color = RED;
x= gparent;
continue;
}
//插入结点是其父亲结点的右孩子结点 ——> 对父亲结点进行左旋，将父亲结点设为插入结点得到，进行接下来操作
if(parent->right == x)
{
RbTreeNode<T> *t;
Left_rotation(root, parent);
t = parent;
parent = x;
x = t;
}
//插入结点是其父亲结点的左孩子结点 ——> 将父亲结点设为黑色，将祖父结点设为红色，对祖父结点进行右旋。
parent->color = BLACK;
gparent->color = RED;
Right_rotation(root,gparent);
}
else //父结点为祖父结点的右孩子
{
RbTreeNode<T> *uncle = gparent->left;
//叔叔结点存在且为红色结点 ——> 将父亲结点和叔叔结点设为黑色，祖父结点设为红色，将祖父结点设为插入结点
if(uncle && uncle->color == RED)
{
parent->color = BLACK;
uncle->color = BLACK;
gparent->color = RED;
x = gparent;
continue;
}
//插入结点是其父亲结点的左孩子结点 ——> 对父亲结点进行右旋，将父亲结点设为插入结点，进行接下来操作。
if(x == parent->left)
{
RbTreeNode<T> *t;
Right_rotation(root,parent);
t= parent;
parent = x;
x = t;
}
//插入结点是其父亲结点的右孩子结点 ——> 将父亲结点设为黑色，将祖父结点设为红色，对祖父结点进行左旋。
parent->color = BLACK;
gparent->color = RED;
Left_rotation(root, gparent);
}
}
root->color = BLACK;
}
3.删除
首先，红黑树的删除情景与普通的二叉搜索树一样，我们也是分析删除结点的孩子结点个数。
- 如果删除的结点是叶子结点，则直接删除即可。
- 如果删除的结点只有一个孩子，则将父结点的指针指向它的孩子。
- 如果删除的结点有两个孩子，则可以找它的后继，只将值覆盖过来，之后情况转变成删除这个后继结点，回到1和2。
3.1 什么情况应该去修复
为了方便讨论，我们以下将删除结点称为z，替代z位置的结点称为y(y为z的后继结点或z结点本身)，替代y本来位置的结点为x。
- 当y为红色结点时(性质1，3必然满足)：
(1).y肯定不为根结点，性质2满足。
(2). 删除后也不会影响祖宗结点的黑高，性质5满足。
(3).删除前z的位置必然满足红黑树，那么y代替z的位置时不会有两个红色结点相邻。如果y不为z的右孩子，则x代替y原本的位置，如果y为红色的话，那么x必然为黑色结点，不会有两个红色结点相邻，性质4满足 - 当y为黑色结点时：
(1).如果y是删除前的根结点，而且x为红色结点，那么这就违反了性质2。
(2).如果x是红色结点且y不为根结点，那么删除y后则有可能出现相邻的红色结点，这违反了性质4。
(3).由于y是黑色结点，那么当它被删掉的时候，它的每个祖先的黑高减1。也就是说，此时y的每个祖先都不满足性质5。
这样看来只有当y为黑色结点时我们才需要进行修复操作。
3.2 怎么去修复红黑树
为了方便讨论，我们以下将删除结点称为z，替代z位置的结点称为y(y为z的后继结点或z结点本身)，替代y本来位置的结点为x，x替换y后的兄弟结点为w，x替换y后的父亲结点为p
我们发现对于性质5的修复，如果通过指针结构的修改和颜色的改变来操作的话，不仅复杂而且没有效率(从y的祖先结点全都要操作一遍)。
既然没有好的直接解决办法，我们不妨将这个矛盾转移。我们的办法就是将y上的黑色下推给x结点(这个颜色是针对x这个结点的，x本身的color属性不变)，这样我们就将违反性质5变为了违反性质1。这样操作后，我们会发现可以大大提高修复的效率。
经过上述操作之后，我们发现对于3.1中y为黑色结点的(1)，(2)两种情况都可以直接将x的颜色设置为黑色来修复好红黑树，所以下面我们只讨论x为双重黑色的非根结点时怎么去修复。
由于x为p的左孩子与x为p的右孩子操作对称，以下我们只讨论x为p的左孩子的情况。由于删除可能是在树的中间进行，所以有些结点颜色不确定，我们在之后的图中用灰色来表示。
3.2.1 w为红色结点
由于这种情况下w为红色结点，那么我们可以得到的信息是p结点和w的两个孩子结点肯定为黑色结点。
这会导致什么情况呢？对于性质1的修复，我们是要将x上的额外黑色沿树上移。可是这种情况，我们只进行一次旋转以及变换颜色都没有办法重新恢复性质。
现在看来，当w为红色结点时，这个问题是没有办法一步解决的。那么，我们就只能想办法把w变为黑色结点然后再进行处理了。
这个思路可以通过p到x的链左旋后再将p的颜色变为红色，w的颜色变为黑色，然后将w指向之前w的左孩子。
3.2.2 w为黑色结点
首先，我们要知道进行左旋时，w的左孩子会变成p的右孩子。由于此时我们是为了将x上多出的黑色沿树上移，所以p的颜色我们自然要设置为黑色。那既然w也为黑色，那么左旋之前w的左孩子什么颜色就不重要。
我们知道旋转会让以旋转点为中心与旋转方向相反的那条外链上的结点取代它们各自父亲结点的位置。可是，红黑树并不只有位置，它的结点还有颜色。
我们旋转后，p已经被设置为了黑色。那么我们为了保证性质5的成立，w应该接替p的颜色才可以。但是，我们w的颜色也应该被接替。可是如果是黑色结点来接替的话，那么到这个点的黑高就少了1，这违背了性质5。而红色结点来替代的话，我们发现这并不会违背性质5。
综上所述，我们在w为黑色结点时，操作与它的孩子结点颜色有关。
我们可以得到4种可能：
- 左右孩子都为黑色结点。
- 左孩子为红色，右孩子为黑色。
- 左孩子为红色，右孩子为红色。
- 左孩子为黑色，右孩子为红色。
经过我们之前的讨论，情况3、4可以直接左旋，那么我们左孩子颜色就不重要。所以，3、4情况可以一起讨论。
3.2.2.1 w的两个孩子结点都为黑色结点
这种情况下，我们无法通过颜色和指针结构的改变来修复红黑树。但由于此时x和w都至少有一层黑色，那么我们就将它们都去掉一层黑色，并让p加上额外的一层黑色(将p变为新的x)。此时，去掉一层黑色的x和w应该分别为黑色结点和红色结点，这不会违背红黑树的性质5和性质4(w的孩子都是黑色结点，p至少有一层黑色)
3.2.2.2 w的左孩子为红色，右孩子为黑色
这种情况下，由于左孩子是红色结点。通过**以w到w左孩子的支链进行右旋，并将w左孩子的颜色设置为黑色，以及将w的颜色设置为红色。最后，将w指向原先w的左孩子。**进行完这步操作后，我们发现新的w的右孩子结点变为了红色，这样就可以直接进行左旋了。
3.2.2.3 w的右孩子为红色
这种情况我们之前已经得到结论，直接进行右旋即可。
template<class T>
void RbTree<T>::delete_fixup(RbTreeNode<T>* &root, RbTreeNode<T> *x)
{
while(x != root && x->color == BLACK)
{
if(x == x->parent->left) //1：x是p的左子结点
{
RbTreeNode<T> *w = x->parent->right;
//1.1：w是红色结点 ——> w设为黑色，p设为红色，对p左旋，得到1.2进行处理
if(w->color == RED)
{
w->color = BLACK;
x->parent->color = RED;
Left_rotation(root, x->parent);
w = x->parent->right;
}
//1.2：w是黑色结点
//1.2.3：wr与wl都为黑结点 ——> w设为红色，p作为新的代替待删除结点的结点，重新进行修复处理
if(w->left->color == BLACK && w->right->color == BLACK)
{
w->color = RED;
x = x->parent;
}
else
{
//1.2.2：wr是黑结点，wl是红结点 ——> w设为红色，wl设为黑色，对w进行右旋，得到1.2.1处理
if(w->right->color == BLACK)
{
w->color = RED;
w->left->color = BLACK;
Right_rotation(root, w);
w = x->parent->right;
}
//1.2.1：wr是红结点，wl任意颜色 ——> w设为p颜色，p设为黑色，wr设为黑色，对p进行左旋
w->color = x->parent->color;
x->parent->color = BLACK;
w->right->color = BLACK;
Left_rotation(root, x->parent);
x = root;
}
}
else //2：x是p的右子结点
{
RbTreeNode<T> *w = x->parent->left;
//2.1：w是红结点 ——> w设为黑色，p设为红色，对p右旋，得到2.2进行处理
if(w->color == RED)
{
w->color = BLACK;
x->parent->color = RED;
Right_rotation(root, x->parent);
w = x->parent->left;
}
//2.2：w是黑结点
//2.2.3：wr与wl都为黑结点 ——> w设为红色，p作为新的代替待删除结点的结点，重新进行修复处理
if(w->left->color == BLACK && w->right->color == BLACK)
{
w->color = RED;
x = x->parent;
}
else
{
//2.2.2：wl是黑结点，wr是红结点 ——> w设为红色，wr设为黑色，对w进行左旋，得到2.2.1处理
if(w->left->color == BLACK)
{
w->color = RED;
w->right->color = BLACK;
Left_rotation(root, w);
w = x->parent->left;
}
//2.2.1：wl是红结点，wr任意颜色 ——> w设为p颜色，p设为黑色，wl设为黑色，对p进行右旋
w->color = x->parent->color;
x->parent->color = BLACK;
w->left->color = BLACK;
Right_rotation(root, x->parent);
x = root;
}
}
}
x->color = BLACK;
}
template<class T>
void RbTree<T>::Rb_transplant(RbTreeNode<T>* &root, RbTreeNode<T>* &u, RbTreeNode<T>* &v)
{
if(u->parent == nil)
{
root = v;
}
else if(u == u->parent->left)
{
u->parent->left = v;
}
else u->parent->right = v;
v->parent = u->parent;
}
template<class T>
void RbTree<T>::ddelete(RbTreeNode<T>* &root, RbTreeNode<T> *z)
{
RbTreeNode<T> *y = z; //替代z位置的结点称为y
RbTreeNode<T> *x = z; //代替y位置的结点
int color = y->color;
if(z->left == nil) //如果删除结点为叶子结点直接删除或没有左孩子时让父指针指向右孩子
{
x = z->right;
Rb_transplant(root, z, z->right);
}
else if(z->right == nil) //如果删除结点为叶子结点直接删除或没有右孩子时让父指针指向左孩子
{
x = z->left;
Rb_transplant(root, z, z->left);
}
else //删除结点有两个孩子
{
y = successor(z); //y变为删除结点的后继结点
color = y->color;
x = y->right;
if(y->parent == z) //y恰好为删除结点的孩子结点
{
x->parent = y;
}
else //y不为删除结点的孩子结点
{
Rb_transplant(root, y, y->right); //先将y的父指针指向右孩子（将x变为y的位置）
y->right = z->right;
y->right->parent = y; //y与删除结点的右孩子连接
}
Rb_transplant(root, z, y); //将删除结点父指针指向y
y->left = z->left;
y->left->parent = y; //y与删除结点的左孩子连接
y->color = z->color;
}
if(color == BLACK) //y为黑色结点需要进行修复
{
delete_fixup(root, x);
}
}
template<class T>
void RbTree<T>::ddelete(T key)
{
RbTreeNode<T> *z = nil;
if((z = ssearch(key)) == nil)
{
return;
}
ddelete(Root, z);
}