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