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

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

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