算法导论笔记：1302红黑树插入

       红黑树的插入可在O(lg n)完成，红黑树的插入类似于二叉搜索树的插入，为了尽量维护红黑树的性质，将插入的新节点标记为RED，然后调用RB-INSERT-FIXUP对红黑树的性质进行维护，RB-INSERT代码如下：

RB-INSERT(T,z)        

       y = T.nil              

       x = T.root             

       while x != T.nil       

              y = x                  

              if z.key

                     x = x.left             

              else x = x.right       

       z.p = y   

       if y == T.nil          

             T.root= z            

      else  if  z.key

             y.left= z            

      else  y.right = z  

      z.left = T.nil        

      z.right = T.nil       

      z.color = RED     

       RB-INSERT-FIXUP(T, z) 

       RB-INSERT-FIXUP负责在插入之后，维护红黑树的性质，代码如下：

RB-INSERT-FIXUP(T,z)                

       while z.p.color == RED               

              if z.p == z.p.p. left                

                     y = z.p.p.right                      

                     if y.color == RED                    

                            z.p.color = BLACK                   // case 1          

                            y.color = BLACK                      // case 1            

                            z.p.p.color = RED                    // case 1          

                            z = z.p.p                                  // case 1  

                     else 

                            if z == z.p.right               

                                  z= z.p                                             //case 3                   

                                  LEFT-ROTATE(T,z)                      // case 3   

                           z.p.color= BLACK                             // case 2         

                           z.p.p.color= RED                              // case 2         

                           RIGHT-ROTATE(T,z.p.p)                 // case 2    

             else(same as then clause with “right” and “left” exchanged)

                     y = z.p.p.left                      

                     if y.color == RED                     

                            z.p.color = BLACK                    // case 1          

                            y.color = BLACK                       // case 1            

                            z.p.p.color = RED                    // case 1          

                            z = z.p.p                                  // case 1  

                     else 

                            if z == z.p.left               

                                  z = z.p                                          //case 3                   

                                  RIGHT-ROTATE(T,z)                 // case 3   

                           z.p.color= BLACK                          // case2         

                           z.p.p.color= RED                           // case2         

                           LEFT-ROTATE(T,z.p.p)                    // case 2 

 T.root.color = BLACK                

1：z的叔叔结点y的颜色为RED，记为case1：

       这种情况，不管z是左孩子，还是右孩子，都是同样的处理方法：

z是右孩子

z是左孩子。

       这种情况的处理代码是：

                            z.p.color = BLACK                   // case 1          

                            y.color = BLACK                       // case 1            

                            z.p.p.color = RED                    // case 1          

                            z = z.p.p                                  // case 1  

       得到下面的图：

z是右孩子

z是左孩子

     这种情况就是把z的父节点和叔叔结点y都变成BLACK，然后z的祖父结点变为RED，然后使祖父结点成为新的z，继续向上处理。

       这种处理方式，各个分支的黑高没有发生变化，同时维护了原红色z的父节点为BLACK的性质。

2：z的叔叔结点y的颜色为BLACK，z为左孩子，记为case2：

       这种情况下， 因为z的父节点是RED，所以z的祖父节点是BLACK，如下图：

       这种情况下的调整代码为：

                     z.p.color = BLACK                          // case 2         

                    z.p.p.color= RED                           // case 2         

                    RIGHT-ROTATE(T,z.p.p)  

       将z的父节点变为BLACK，祖父节点变为RED，同时对祖父节点进行右旋，得到下面的图：

3：z的叔叔结点y的颜色为BLACK，z为右孩子，记为case3：

       这种情况与case2类似，如下图;

       这种情况下的调整代码为：

                            z = z.p                                      // case 3                   

                           LEFT-ROTATE(T, z)                    // case 3 

调整后得到下面的图：

分析：

       n个结点的红黑树高度为O(lg n)，插入操作中，除了最后一步外，剩下的操作与二叉搜索树的插入相同，也就是时间复杂度为O(lg n)。在RD-INSERT-FIXUP中，仅当case1时，z才沿着树上升，while循环才会重复执行。所以while的重复次数为O(lgn)。如果是case2或者3，则while循环直接结束。所以，RB-INSERT的时间复杂度为O(lg n)。