红黑树插入删除

一.红黑树的基本性质：
    1.首先是一棵二叉查找树。
    2.所有节点要么是红色，要么是黑色。
    3.跟节点是黑色。
    4.红色节点的孩子节点必须为黑色节点。
    5.从跟节点到叶子结点的任意一条路径上，黑色节点的数目是相同的。
    另外为了算法的方便，规定空的叶子结点的颜色为黑色。
二.红黑树的插入
        红黑树的插入分为插入和调整，插入是将新节点根据二叉查找树的规则插入到红黑树中，如果因为插入而导致了红黑树的性质遭到破坏，则需要调整。
        （一） 插入：规定所有新插入的节点的颜色为红色，所以所有的插入操作并不会破坏红黑树的性质1，性质2和性质5. 但当插入节点是跟节点是，破坏了性质3；如果插入节点的父节点的颜色是红色，则破坏了红黑树的性质4；其他情况下都不需要调整，只有这两种情况下需要调整。
        （二）调整：
           1. 如果破坏了性质3，即插入的节点是跟节点，只需要将新插入节点的颜色变为黑色，即可调整完毕。
           2. 如果破坏的是性质4，则需要进行旋转调整。具体分为四种情况.
              
         注：在上面A子树上插入和B子树上插入，调整方法是一样的，所以只记录在A子树上插入的情况。为了描述方便，规定新插入的节点为N，父节点为P，叔父节点为U，爷爷节点为GP，兄弟节点为S。由红黑树的性质可知，因为父节点P是红色，所以GP一定是黑色。
         情况1:N是父节点的左孩子，并且U是黑色（空节点也视为黑色）。调整方案为，交换P和GP的颜色，然后对P做右旋转，调整即可完成，调整结果如下图所示。
                              

        情况2:N是父节点的右孩子，并且U是黑色（空节点也视为黑色）。调整方案为，先对P节点做一次坐旋转，之后就会变成和情况1一样，在对N进行右旋转，交换N和GP的颜色即可。
                                        
     情况3:N是父节点的左孩子，并且U是红色。调整方案为，把P和U变为红色，在把GP设置为红色。这样调整之后，就相当于新插入的节点是GP，继续对GP进行考虑如下图所示。GP的父节点有可能是黑色，也有可能是红色，如果是黑色，则不需要调整，如果是红色，就需要看看是情况1，2，3，4中的哪一种情况，继续进行调整。
    
                                  
    
         情况4：N是P的右孩子，并且U的颜色是红色。调整方案为，先对P进行右旋转，转换为情况3，然后改变N和U的颜色为黑色，变GP为红色。现在，考虑GP节点是否需要在此调整。

                                  
红黑树的插入就分为着四种情况。

三.红黑树的删除。
    红黑树的删除要比红插入复杂。与插入相同，删除过程也分为删除和调整两个步骤。删除会把节点从红黑树中删除，如果删除后破坏了红黑树的性质，则需要进行调整。
   （一）删除：为了保证红黑树的二叉查找树的性质，删除一个红黑树的节点时，需要在红黑树中找到他的中序遍历的后继节点或者前驱节点来代替要删除的节点，问题转换为删除要删除节点的后继或者前驱。由二叉查找树的性质可以知道，树中的一个节点的前驱节点为它左子树的最右节点，后继结点为它右子树的最左节点，无论是最右节点还是最左节点，他们都只有一个孩子，所以红黑树的删除最终转换成删除一个只有一个孩子的节点。
      在红黑树中删除一个只有一个孩子的节点时，直接用它的孩子节点来代替它即可。
      当删除节点的颜色是红色的时候，我们并不会破坏红黑树的性质，因为如果删除节点是红色，则它的孩子和父亲必定是黑色，这样并不会导致两个红色节点在一起的情况（即红父红孩子）。又由于删除的是红色节点，并不会改变通过它到自节点路径上黑色节点的个数。
      当删除节点是黑色的情况是，无论如何都会破坏红黑树的性质，所有需要进行调整。
   （二）调整：
           如果删除节点是黑色，但是它的孩子节点是红色，那么只需要简单的用它的红色孩子节点替换它，并且更改孩子的颜色为黑色即可。所以下文并不对这种情的调整进行介绍。    
              
         注：在上面A子树上插入和B子树上的删除，调整方法是一样的，所以只记录在A子树上删除的情况。为了描述方便，删除节点的孩子节点为N（要删除节点已经从树上删除），删除节点的父节点为P（现在为N的父节点），兄弟节点为S，祖父节点为GP。

        情况1:N是新的跟节点。这种情况表明红和树的跟节点只有一个子树，不需要任何调整。
        情况2:S是红色。此时N和S的父节点一定是黑色，而且S的孩子也一定是黑色。调整方法为，对P节点进行做选择，更改P和S的颜色。调整之后，经过S到SN的所有自节点路径上的黑色节点数目没有改变，经过S到P再到N所有子节点的路径上的黑色节点数目少一个（需要注意的是在图中是看不出来，少是因为N的黑父节点被删除了，这就是为什么要调整的原因了），经过S->P->SL 到所有自节点的路径上黑色节点数没有改变。所以需要继续调整N，经过这一步的调整，N的兄弟节点已经变成黑色的了，具体调整见后面的几种情况。
                           
       情况3:S是黑色，但是S的孩子全是黑色，而且S的父亲也是黑色。调整方案为，简单的将S的颜色绘制成红色，这样通过P到所以子节点的路径上黑色节点的个数是相同的，但是相对于不同过P的路径还是少了一个黑色节点。所以问题转换成调整P节点，而调整P节点又可以看看是符合这六种情况中那种情况。
               
    情况4:S是黑色，S的儿子都是黑色，但是N的父亲是红色。在这种情形下，我们简单的交换S和P的颜色。这样调整之后，红黑树的性质已经恢复了，整个调整结束。
                  
  情况5：S是黑色，S的右孩子是红色，P的颜色任意。这种情况，对P作左旋转，交换P和S的颜色，把S的右孩子变成黑色。经过这个变换之后，经过N到子节点的路径上多了一个黑色节点，正好补充了因删除少的一个黑色节点，经过SL和SN路径上的路径上的黑色节点数目并没有变化。所以红黑树的性质得到满足。
             
情况6:S是黑色，S的左孩子是红色，P的颜色任意。这种情况，先对S进行右旋转，这样SL的左孩子变成了N的兄弟，而且因为SL为红色，所以它的左孩子的颜色比为黑色。经过旋转之后，N的兄弟SL的左孩子为黑色，有孩子为红色，变成情况5，按情况5再做一次调整即可。

           
红黑树的删除比较复杂的就着6种情况。