http://blog.csdn.net/sun_tttt/article/details/65445754

 

红黑树是一个平衡的二叉树，但不是一个完美的平衡二叉树。虽然我们希望一个所有查找都能在~lgN次比较内结束，但是这样在动态插入中保持树的完美平衡代价太高，所以，我们稍微放松逛一下限制，希望找到一个能在对数时间内完成查找的数据结构。这个时候，红黑树站了出来。 

 

阅读以下需要了解普通二叉树的插入以及删除操作。 

红黑树是在普通二叉树上，对没个节点添加一个颜色属性形成的，同时整个红黑二叉树需要同时满足一下五条性质 

 

红黑树需要满足的五条性质： 

 

性质一：节点是红色或者是黑色； 

在树里面的节点不是红色的就是黑色的，没有其他颜色，要不怎么叫红黑树呢，是吧。 

性质二：根节点是黑色； 

根节点总是黑色的。它不能为红。 

性质三：每个叶节点（NIL或空节点）是黑色； 

这个可能有点理解困难，可以看图： 

 

这个图片就是一个红黑树，NIL节点是个空节点，并且是黑色的。 

性质四：每个红色节点的两个子节点都是黑色的（也就是说不存在两个连续的红色节点）； 

就是连续的两个节点不能是连续的红色，连续的两个节点的意思就是父节点与子节点不能是连续的红色。

性质五：从任一节点到其没个叶节点的所有路径都包含相同数目的黑色节点；

从上图可以看见相同数量的黑色节点有三个；

 

 

当我们进行插入或者删除操作时所作的一切操作都是为了调整树使之符合这五条性质。 

 

下面我们先介绍两个基本操作，旋转。 

旋转的目的是将节点多的一支出让节点给另一个节点少的一支，旋转操作在插入和删除操作中经常会用到，所以要熟记。

下面是左旋和右旋： 左旋：

 

右旋： 

 

下面讲讲插入

我们先明确一下各节点的叫法 

 

 

因为要满足红黑树的这五条性质，如果我们插入的是黑色节点，那就违反了性质五，需要进行大规模调整，如果我们插入的是红色节点，那就只有在要插入节点的父节点也是红色的时候违反性质四或者是当插入的节点是根节点时，违反性质二，所以，我们把要插入的节点的颜色变成红色。

 

下面是可能遇到的插入的几种状况： 

1、当插入的节点是根节点时，直接涂黑即可； 

2、当要插入的节点的父节点是黑色的时候。 

 

这个时候插入一个红色的节点并没有对这五个性质产生破坏。所以直接插入不用在进行调整操作。

 

3、如果要插入的节点的父节点是红色且父节点是祖父节点的左支的时候。 

这个要分两种情况，一种是叔叔节点为黑的情况，一种是叔叔节点为红的情况。 

当叔叔为黑时，也分为两种情况，一种是要插入的节点是父节点的左支，另一种是要插入的节点是父亲的右支。 

我们先看一下当要插入的节点是父节点的左支的情况：

 

这个时候违反了性质四，我们就需要进行调整操作，使之符合性质四，我们可以通过对祖父节点进行右旋同时将祖父节点和父节点的颜色进行互换，这样就变成了： 

 

经过这样的调整可以符合性质四并且不对其他性质产生破坏。 

当插入的节点是父节点的右支的时候： 

 

当要插入的节点是父节点的右支的时候，我们可以先对父节点进行左旋，变成如下： 

 

如果我们把原先的父节点看做是新的要插入的节点，把原先要插入的节点看做是新的父节点，那就变成了当要插入的节点在父节点的左支的情况，对，是的，就是按照当要插入的节点在父节点的左支的情况进行旋转，旋转完之后变成如下： 

 

4、如果要插入的节点的父节点是红色且父节点是祖父节点的右支的时候； 

这个时候的情况跟情况3所表述的情况是一个镜像，将情况3的左和右互换一下就可以了。 

 

5、如果要插入的节点的父节点是红色并且叔叔节点也为红色，如下： 

 

 

 

这个时候，只需将父亲节点和叔叔节点涂黑，将祖父节点涂红。

以上就是插入的全部过程。 

 

首先你要了解普通二叉树的删除操作： 
1.如果删除的是叶节点，可以直接删除； 
2.如果被删除的元素有一个子节点，可以将子节点直接移到被删除元素的位置； 
3.如果有两个子节点，这时候就可以把被删除元素的右支的最小节点（被删除元素右支的最左边的节点）和被删除元素互换，我们把被删除元素右支的最左边的节点称之为后继节点（后继元素），然后在根据情况1或者情况2进行操作。如图： 
 
将被删除元素与其右支的最小元素互换，变成如下图所示：

 
然后再将被删除元素删除：

我们下面所称的被删除元素，皆是指已经互换之后的被删除元素。 
加入颜色之后，被删除元素和后继元素互换只是值得互换，并不互换颜色，这个要注意。

 

 

下面开始讲一下红黑树删除的规则： 
1.当被删除元素为红时，对五条性质没有什么影响，直接删除。 
2.当被删除元素为黑且为根节点时，直接删除。 
3.当被删除元素为黑，且有一个右子节点为红时，将右子节点涂黑放到被删除元素的位置，如图： 
由 
 
变成 

4.当被删除元素为黑，且兄弟节点为黑，兄弟节点两个孩子也为黑，父节点为红，此时，交换兄弟节点与父节点的颜色；NIL元素是指每个叶节点都有两个空的，颜色为黑的NIL元素，需要他的时候就可以把它看成两个黑元素，不需要的时候可以忽视他。 
如图： 
由 
 
变成： 
 
5.当被删除元素为黑、并且为父节点的左支，且兄弟颜色为黑，兄弟的右支为红色，这个时候需要交换兄弟与父亲的颜色，并把父亲涂黑、兄弟的右支涂黑，并以父节点为中心左转。如图： 
由：

 
变成：

 
6.当被删除元素为黑、并且为父节点的左支，且兄弟颜色为黑，兄弟的左支为红色，这个时候需要先把兄弟与兄弟的左子节点颜色互换，进行右转，然后就变成了规则5一样了，在按照规则5进行旋转。如图： 
由 
 
先兄弟与兄弟的左子节点颜色互换，进行右转，变成：

 
然后在按照规则5进行旋转，变成： 
 
7.当被删除元素为黑且为父元素的右支时，跟情况5.情况6 互为镜像。 
8.被删除元素为黑且兄弟节点为黑，兄弟节点的孩子为黑，父亲为黑，这个时候需要将兄弟节点变为红，再把父亲看做那个被删除的元素（只是看做，实际上不删除），看看父亲符和哪一条删除规则，进行处理变化如图： 
由： 
 
变成： 
 
8.当被删除的元素为黑，且为父