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

 Определение

|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)