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

 Определение

|definition = Left-leaning Red-Black Trees .

Вращения

  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

  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)

   Node moveRedLeft(Node h):
   colorFlip(h):
   if isRed(h.right.left)
     h.right = rotateRight(h.right)
     h = rotateLeft(h)
     colorFlip(h)
   return h  

    Node moveRedRight(h :Node ):
    colorFlip(h)
    if isRed(h.left.left))
      h = rotateRight(h)
      colorFlip(h)
    return h  

void delete(key : Key):
  root = delete(root, key)
  root.color = BLACK

  Node delete(Node : h, Key : key):
   if key.compareTo(h.key) < 0)     
          if !isRed(h.left) && !isRed(h.left.left)
            h = moveRedLeft(h)
          h.left =  delete(h.left, key)
   else  
     if isRed(h.left)
       h = rotateRight(h)
     if key.compareTo(h.key) == 0 && (h.right == null)
       return null
     if !isRed(h.right) && !isRed(h.right.left)
       h = moveRedRight(h)
     if key.compareTo(h.key) == 0
       h.val = get(h.right, min(h.right).key)
       h.key = min(h.right).key
       h.right = deleteMin(h.right)
     else 
       h.right = delete(h.right, key)
  return fixUp(h)