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

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

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

  public Value search(Key key)
  Node x = root;
  while (x != null)
      int cmp = key.compareTo(x.key);
      if (cmp == 0) return x.val;
         else
              if (cmp < 0) 
                 x = x.left;
                  else 
                      if (cmp > 0) 
                         x = x.right;
         return null;

Удаление

void deleteMin()
  root = deleteMin(root);
  root.color = BLACK;

Node deleteMin( h : Node)
  if (h.left == null) return null;
  if (!isRed(h.left) && !isRed(h.left.left))
     h = moveRedLeft(h);
  h.left = deleteMin(h.left);
  return fixUp(h);