红黑树 插入

一、满足下面几个条件的二叉搜索树，称为红黑树：

1.       任何一个节点都被着色――红色或是黑色。

2.       根节点是黑色的。

3.       所有的NIL节点都看成黑色（NIL节点是就是一个假想的或是无实在意义的节点，所有应该指向NULL的指针，都看成指向了NIL节点。包括叶节点的子节点指针或是根节点的父指针）。

4.       如果一个节点是红色的，那么它的子节点一定是黑色的。

5.       对于任何一个节点而言，从该节点到它的子孙节点中的NIL节点路径中，所包含的黑节点个数相同。



二、黑高度的定义：

      从任何一个节点，向下到底部的路径中，包含的黑节点的个数，称为这个节点的黑高度。从红黑树的第５条性质可以看出，黑高度是唯一的、确定的。



      只要同时满足红黑树的这些条件，就一定会有“红黑树可以保证任何两条从根部到树叶的路径节点个数相差不超过２倍”这个平衡的性质。

我们可以假设，如果存在两条路径L和S，L比S长两倍以上（S路径上有n个节点，L上有大于2n个节点）。可知，S的黑高度最大只可能是n，那么根据第５条性质，L的黑高度也大也只可能是n，也就是，L路径上一定有超过n个红色节点（因为节点不是黑的就必定是红的）。所以，肯定会有两个以上的红色节点是相邻的。这就与第４个条件矛盾了。所以，红黑树可以保证任何两条从根部到树叶的路径节点个数相差不超过２倍。



      红黑树的高度h<2lg(n+1)（这个在《算法导论》13.1节中有证明）。也就是说，红黑树的操作的时间复杂度是O(lgn)的。



      二叉搜索树的操作时间复杂度，取决于树高h，因此，我们当然就希望h尽量地小以提高操作的效率。从直观上就可以发现，二叉搜索树各子树的规模越平均，它的高度就会越小。所以在应用中，一般都会将二叉搜索树实现成一种平衡树，以保证最差时间复杂度为O(lgn)。红黑树就是其中的一种，应用得很广泛（SGI STL的set和map就是基于红黑树来实现，Linux内核中也用到这个数据结构）

红黑树是二叉搜索树的一种。它与普通二叉搜索树不同的是，红黑树的每个节点都附加了另一个属性――颜色，可以是红色，也可以是黑色。通过对于每条路径上节点颜色的规则进行限定，红黑树可以保证任何两条从根部到树叶的路径节点个数相差不超过２倍。所以，红黑树是一种近似平衡的二叉搜索树。



      红黑树的查找、最大值、最小值、前趋、后继等操作，与普通的二叉搜索树没有什么区别。插入和删除操作需要重新实现。仅仅用普通的二叉搜索树的插入和删除动作，可能会破坏红黑树本身的一些性质，因此，需要进行额外的处理。这些额外的处理主要是改变树节点的颜色，或是改变树的结构。



三、树的旋转

      改变树的结构，主要是用旋转。旋转有两种，左旋和右旋，下面是这两种旋转的：

这种旋转的操作，是在二叉搜索树的局部对树的结构进行调整的一种方式，经过旋转之后，二叉搜索树的性质是不会发生改变的。如下图：




      向红黑树插入节点，先将需要插入的节点着成红色，用普通二叉搜索树的方法将这个节点插入到树中，然后再想办法把被破坏的红黑性质恢复。（将新插入的节点颜色着成红色，呆以尽量减少对红黑性质的破坏，恢复起来也容易。因为插入红色节点的话，那么被破坏的部分会在局部，考虑的问题也就比较少，恢复过程也容易形成递归，详细见下文说明）


      我们考虑下，如果一个红色节点（下文称用Z指向它）被插入到树中，那么有哪些红黑性质可能被破坏呢？只有第2条（根节点是黑色的）以及第4条（红色节点的子节点一定是黑色节点），其它都不会被破坏。

如果插入的节点的父节点是黑色的，那么不需要做任何调整，这红黑树是正常的。如果父节点是红色，或没有父节点（也就是插在了树根的位置），那么就要进行调整以保证红黑树是正确的。


      首先对第4 条进行分析，我们知道，插入一个新的节点，这个节点肯定会被放到树的底部成为一个叶节点（参考普通二叉树的插入过程），那么这个红色节点就没有可能和自己的子节点同色（因为叶节点的子节点是NIL节点，都是黑色的），如果第4条被破坏的话，肯定是Z指向的节点的父节点是红色的。因此，为了使分析和解决更加容易和清晰，我们在对树进行调整以恢复红黑特性时，始终使得Z总是指向相邻红色的节点中的子节点（指针Z可能会向上升到树的中部或根部）。基于这个做法，我们可以知道，如果是第2条被破坏了的话，也就是Z指向根节点了，那么第4条肯定就符合了（因为Z的父节点是NIL，黑色的），因此对第2条性质的恢复变得很简单，只需要被根从红色变为黑色即可。这时，所有性质都会被满足了（因为是根节点，所以根节点被着为黑色时，所有路径都黑高会统一加1，也就是第5条不会被破坏，操作之后的红黑树仍然是正确的）。好了，现在只留下第4条性质的恢复的问题了。

      如果第4条被破坏了，也就是说，Z的父节点是红色的，那么，说明，Z一定有祖父节点，而且是黑色的（否则插入前原树就有问题，又或是调整时的方法不正确）。因此可以把问题放到以Z的祖父节点为根节点的子树内进行解决，这样可以把调整的范围最小化，而且这也是有可能的：只要不改变这子树的黑高度，那么就不会对树的其它部分产生影响。我们要做的就是在这个子树范围内把红黑性质调整回来。再看子树的根是否与其父节点同为红色，是的话，就再次用前面所说的去解决它，一直向上递归到红黑性质被恢复为止。



四、红黑树的节点插入

       对第4条性质的恢复，根据Z的父节点是Z的祖节点的左子节点还是右子节点，分为两组对称的情况，每组有3种情况。下面我们只对其中一组进行说明，以Z的父节点是Z祖节点的左子节点为例： 

RBT-Insert3

第一种：Z的“叔父”节点是红色。



             RBTree1



      如上图所示，在这种情况下，将父、叔节点都着为黑色，再将子树根节点着为红色，那么子树的黑高度没有发生改变，而且红黑性质得得到了调整。此时，再将Z指向子树的根节点，向上递归恢复红黑特性。



第二种：Z的“叔父”节点是黑色的，Z的父节点的左子节点。


     

      如上图，将Z的父节点与祖节点进行一次右旋，并把父节点着黑色，原来的祖节点着红色。这些子树的红黑特性得到了恢复，而且子树的黑高度没有变化。另外，由于子树根节点已经是黑色了（这个节点不会出现父子同为红色的问题了），所以不必再向上递归了，此时整个树的红黑特性都已经是正确的了。



第三种：Z的“叔父”节点是黑色的，Z的父节点的右子节点。



      如上图，将Z本身与其父节点进行一次左旋，让Z指向原来的父节点，就可以调整为情况二，而情况二已经得到解决。


这样，红黑树的节点插入问题就得到了解决。

原文来自：:http://liyiwen.iteye.com/blog/345800