一.什么是红黑树

红黑树是一棵二叉搜索树，其在每个结点上增加了一个存储位来表示颜色，可以是红(red)或者黑(black)。通过任何一条从"根到叶子的简单路径"上的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是近似于平衡的。红黑树是一种平衡二叉树。

红黑树的基本性质

(1)每个结点要么是红色的，要么是黑色的(废话..)

(2)根结点是黑色的

(3)叶子结点是黑色的(也可以说是NIL结点)

(4)如果一个结点是红色的，那么它的孩子一定是黑色！(也就是红色不可邻接)

(5)对于每个结点，从该结点到其所有后代的简单路径上，包含的黑色结点数目相同(即黑高相等)

其中，4、5两点是约束的关键。基本上，对于红黑树的更易操作，如增、删等，有可能破坏性质4、5，因而需要“修复”。

为了处理红黑树中代码的边界条件，使用一个哨兵NIL。对于一棵红黑树T,哨兵T.nil是一个与树中普通结点拥有相同属性的对象，它的颜色为黑。而其他属性为任意值。

 

二.红黑树的插入操作

我们规定，每当插入一个新的结点，都先将这个结点“涂”成红色。在确立了这条规则后，就可以讨论插入操作所引发的影响了。

在插入之前，红黑树已经满足了5条基本性质。现在考虑插入结点z的父结点z.p的颜色。

如果z.p是黑色的，因为插入的结点是红色，自然任何到达z.p的支路，所对应的黑高不变，故满足性质5.同时，红色结点的父亲是黑色，也满足性质4.所以，红黑树的基本性质依然满足，不需要再进行多余的操作了(插入就插入吧)

如果z.p是红色的，阿哦，很显然，这立刻就打破了性质4的约束。很显然，我们需要进行适当的“操作”来维持红黑树的性质。至于该如何操作，又要分三种情况来讨论:

1、如果z的叔叔结点和父亲一样是红色的(这里因为父亲结点是红色，所以爷爷结点必然是黑色，否则在插入前就不是红黑树了)。如下图。

 

很明显，由于性质4被破坏，最直白的方式是改变父亲结点的颜色。但是将父亲结点染黑以后，任何到达父亲结点的支路黑高+1，必然破坏了性质5.该怎么办？

等会，我们看到，父亲这一辈(父亲结点和叔叔结点)是同色的，那么如果我们交换父辈和爷爷的颜色，在局部范围，不就同时满足了性质4、5了吗？变换完成后，就如上述情况(a)中右侧所示。

而此时，由于爷爷的颜色染红，有可能又破坏了性质4(如果爷爷的父亲是红色的话),所以要将爷爷作为新的z，重新循环，进行修复操作。

 

2、如果z的叔叔结点是黑色的，并且z是父亲的左孩子。如下图情况所示

为了满足性质4，我们可以先交换z的爷爷和父亲的颜色。交换后，性质4得以满足。---但是，很明显可以看出，对于叔叔结点这条支路，显然黑高-1，这样一定不会满足性质5了。所以我们需要对爷爷结点进行一次右旋操作。右旋后，显然对于局部而言，性质4、5都可以得到满足。

那么，对于全局情况呢？因为右旋后，原本爷爷结点的位置是黑色的父亲结点。所以对于全局而言，性质4必然是满足的(黑结点的父亲可以是任何颜色)。而由于局部的黑高没有变动，所以整体的黑高也不变。故对于整棵红黑树，其基本性质得到了维护

 

3、如果z的叔叔结点是黑色的，但是z是父亲的右孩子，如下图所示

 

你可能会想说，这和情况2不是很像吗？能不能复现情况2的做法呢？

答案是否定的----至于为什么，这里不细致推敲，仅是简单说一下:

我们直到，如果对Z的爷爷结点进行右旋，那么在右旋后，Z的父亲结点也就会替代爷爷结点原本的位置。而父亲结点的右孩子，此时也就是Z，将会变成原本爷爷结点的左孩子---但是爷爷结点已经被染红(参照情况2的步骤)了呀，这下不又打破了性质4了吗？

所以，对于情况3，我们要做的事很简单，其与情况2的区别无非就是父亲结点和p的相对位置有差，那么，只要进行简单的旋转操作就可以改变相对位置了呀。----所以，我们对父亲结点进行一次左旋，这时候就变成情况2了(现在把旋转后的父亲结点当作孩子，而原本的孩子成为了父亲)。

 

下面是插入操作的伪代码，可以结合上文阅读（摘自《算法导论》）

 

 

 

三.删除操作

与n个结点的红黑树上的其他操作基本一样，删除一个结点要花费O(logn)时间，与插入相比，删除操作要稍微复杂些。

从一棵红黑树中删除结点的过程是基于二叉搜索树的删除过程来的，在我的上一篇博客中对二叉搜索树已进行了介绍，这里不多赘述。

可以说，红黑树的删除的过程几乎与二叉搜索树的删除过程大同小异:

1. 如果被删除结点没有孩子，就直接删除
2. 如果被删除结点没有左孩子，就用它的右孩子代替之
3. 如果被删除结点没有右孩子，就用它的左孩子代替之
4. 如果被删除结点既有右孩子，又有左孩子，就用它的后继替代之

那么区别在哪？

---在于红黑树除了具有二叉搜索树的基本性质外，也具有自身的基本5个性质呀。

显然，删除操作很容易对红黑树本身的性质造成影响，尤其当被删除结点有孩子结点的时候(这个...很容易看出吧)

好了，我们的目的只有一个，那就是维护红黑树的性质。所以我们将目光着眼于删除操作后，代替被删除结点的那个结点。假设被删除结点是p，替代结点是x，我们现在从结点x看起。(对于上述情况4，这里存在两个替代，分别是后继替代p 和 p的右孩子替代后继，这种情况我们则先看后继的替代，也就是后继结点的右孩子，将之视作x)

那么，现在一共可以归纳出4种情况，如下图所示(这里只讨论x目前作为父结点的左孩子的情况，因为作为右孩子时，完全对称，只需要简单交换left和right字样就可以了)

情况a、x的兄弟结点是红色的。

这时候，应将兄弟和父亲换色，然后左旋，变成b、c、d情况之一。

情况b、x的兄弟结点是黑色，但是其兄弟结点的孩子均黑

这时候，直接把兄弟染红，这下该层以下的支路黑高平衡了，然后把x上移动，如果x.p原本为红，则染黑即可，此时满足红黑树性质。否则，继续循环修复黑高

情况c、x的兄弟结点是黑色，但是其兄弟结的右孩子是黑色，且左孩子为红色

这时候，交换兄弟和兄弟左孩子的颜色，让兄弟做一次右旋，变成情况d

情况d、x的兄弟结点是黑色，但是其兄弟结点右孩子是红色

这时候，交换兄弟结点和父亲结点的颜色，然后将兄弟结点的右孩子染黑，再让父亲结点做一次左旋。over

 

好吧，以上结论出自《算法导论》。第一次看的时候觉得实在有些“绕”，所以本人也基于个人理解，将之做了总结。

 

红黑树在删除操作后的修复过程总结：

红黑树性质修复主要取决于被删除结点(p)的替代结点(x). 所以，实际上可以这么分类:

1、如果x的兄弟是红色(情况a)，就转换为b、c、d情况

2、如果不是情况a，只需要讨论x兄弟的右孩子的颜色:

如果x的兄弟的右孩子为红色(包含红红、黑红两种孩子情况,此时就是情况d)，那么先进行一些染色步骤，再进行一次左旋即可让整体红黑性质得到维护。

如果x的兄弟结点的右孩子非红.无非只可能是：

(1)孩子为双黑，那么就把兄弟结点染红。这时候达到局部红黑平衡。再让x上升到其父节点的位置。如果父节点原本为红色，那么就将其染黑，这样达到全局红黑平衡。否则，继续迭代。

(2)孩子为左红右黑，那就按照情况c的操作，转换为情况d。

 

 

 

下面是操作过程的伪代码:(摘自《算法导论》)

 

说到底，要让红黑树整体平衡，只有通过情况b和d的方法能够进行修复。所以，竭尽所能地把任何情况都转换为b、d中之一！