// p[x] : parent of x


procedure RT_Insert(inout T : RB_Tree; in x : Node)
begin

  // Conventional insertion into sorted binary tree:
  // x will become a new leaf of T
  Tree_Insert(T,x);
  color[x] = RED;
  
  while ( x != root[T] and color[p[x]] == RED ) do
    if ( p[x] == left[p[p[x]]] ) then
      y = right[p[p[x]]];
      if ( color[y] == RED ) then
         color[p[x]] = BLACK;
         color[y] = BLACK;
         color[p[p[x]]] = RED;
         x = p[p[x]];
      else 
         if ( x == right[p[x]] ) then
           x = p[x];
           Left_Rotate(T,x);
         endif
         color[p[x]] = BLACK;
         color[p[p[x]]] = RED;
         Right_Rotate(T,p[p[x]]);
      endif
    else
      // same as then-clause, with right and left exchanged
      y = left[p[p[x]]];
      if ( color[y] == RED ) then
         color[p[x]] = BLACK;
         color[y] = BLACK;
         color[p[p[x]]] = RED;
         x = p[p[x]];
      else 
         if ( x == left[p[x]] ) then
           x = p[x];
           Right_Rotate(T,x);
         endif
         color[p[x]] = BLACK;
         color[p[p[x]]] = RED;
         Left_Rotate(T,p[p[x]]);
      endif      
    endif
  enddo

  color[root[T]] = BLACK;

end


procedure Left_Rotate(inout T : RB_Tree; in x : Node)
begin

  y = right[x];
  right[x] = left[y];

  if ( left[y] != NIL ) then
    p[left[y]] = x;
  endif

  p[y] = p[x];

  if ( p[x] == NIL ) then
    root[T] = y;
  else if ( x == left[p[x]] ) then
    left[p[x]] = y;
  else
    right[p[x]] = y;
  endif

  left[y] = x;
  p[x] = y;

end