/* -------------------------------------------- */
   /* Восстановление красно-чёрных свойств дерева  */
   /* после удаления узла с ключом x               */
   /* -------------------------------------------- */
   RB-DeleteFixup(T,x)
   /* x    - удаляемый узел; */
   /* p(x) - "отец" узла x;  */
   /* w    - "брат" узла x   */
   {
     while (x!=root(T) and color(x)==BLACK)
       if x==left(p(x))
       {
         w<-right(p(x))
       /* Если у вершины x брат красного цвета, то произ-  */
       /* водится левый поворот вокруг отца, при этом брат */
       /* становится родителем отца и его цвет меняется на */
       /* чёрный, а цвет отца - на красный                 */
         if color(w)==RED
         {
           color(w)<-BLACK
           color(p(x))<-RED
           LeftRotate(T,p(x))
           w<-right(p(x))
         }
         /* Если у вершины x брат чёрного цвета и оба его */
         /* ребёнка - чёрные, то  цвет  брата  становится */
         /* красным. Таким образом, проблема перемещается */
         /* на уровень вверх, и  цикл  while  повторяется */
         /* уже для узла-отца                             */
         if color(left(w))==BLACK and color(right(w))==BLACK
         {
           color(w)<-RED
           x<-p(x)
         }
         /* Если у брата вершины x ребёнок (правый) - чёрно- */
         /* го цвета, то цвет брата меняется на красный цвет */
         /* и производится правый поворот вокруг брата       */
         else {
                if color(right(w))==BLACK
                {
                  color(left(w))<-BLACK
                  color(w)<-RED
                  RightRotate(T,w)
                  w<-right(p(x))
                }
                /* В противном случае цвет брата вершины x меня- */
                /* ется на цвет отца, а цвет отца - на чёрный.   */
                /* Далее производится левый поворот вокруг отца, */
                /* полностью устраняя нарушение                  */
                /* --------------------------------------------- */
                color(w)<-color(p(x))
                color(p(x))<-BLACK
                color(right(w))<-BLACK
                LeftRotate(T,p(x))
                x<-root(T)
              }
       }
       else {
              w<-left(p(x))
              if color(w)==RED
              {
                color(w)<-BLACK
                color(p(x))<-RED
                RightRotate(T,p(x))
                w<-left(p(x))
              }
              if color(left(w))==BLACK and color(right(w))==BLACK
              {
                color(w)<-RED
                x<-p(x)
              }
              else {
                     if color(left(w))==BLACK
                     {
                       color(right(w))<-BLACK
                       color(w)<-RED
                       LeftRotate(T,w)
                       w<-left(p(x))
                     }
                     color(w)<-color(p(x))
                     color(p(x))<-BLACK
                     color(left(w))<-BLACK
                     RightRotate(T,p(x))
                     x<-root(T)
                   }
            }
     color(x)<-BLACK
   }

   O(log2n),