Левосторонние красно-чёрные деревья

Определение:

Left-leaning Red-Black Trees .

Вращения

• [math] \mathrm{push}(i, x)[/math] — добавляет элемент [math]x[/math] в стек узла [math]i[/math],

 Stack push(i : Node, x : T):
   k.value = x
   k.prev = i
   s.top = k
   return s

• [math]\mathrm{pop}(i)[/math] — возвращает значение, хранящееся в узле [math]i[/math] и копирует элемент, предыдущий для него.

 pair<T, Stack> pop(i : Node):
   T val = i.value 
   i = i.prev
   return pair(val, s)

  Node rotateRight(h : Node ):
  x = h.left
  h.left= x.right
  x.right= h
  x.color = h.color
  h.color = RED
   return  x

  Node rotateLeft(h : Node):
  x = h.right
  h.right = x.left
  x.left = h
  x.color = h.color
  h.color = RED
  return x

 void flipColors(h : Node h):
  h.color = !h.color
  h.left.color =  !h.left.color
  h.right.color = !h.right.color

Методы

  void insert( key : Key, value : Value ): 
   root = insert(root, key, value);
    root.color = BLACK;

     Node insert( h : Node, key : Key, value : Value)
          if (h == null)     
              return new Node(key, value);
          if (isRed(h.left) && isRed(h.right)) colorFlip(h);
          int cmp = key.compareTo(h.key); 
          if (cmp == 0) 
              h.val = value;
          else 
              if (cmp < 0) 
                  h.left = insert(h.left, key, value);  
              else 
                  h.right = insert(h.right, key, value);
          if (isRed(h.right) && !isRed(h.left))    
              h = rotateLeft(h);
          if (isRed(h.left) && isRed(h.left.left)) 
              h = rotateRight(h);
     return h