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

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

Left-leaning Red-Black Trees— .

Вращения

One way to view red-black BST algorithms is as maintaining the following invariant properties under insertion and deletion: • No path from the root to the bottom contains two consecutive red links. • The number of black links on every such path is the same. These invariants imply that the length of every path in a red-black tree with N nodes is no longer than 2 lg N . This worst case is realized, for example, in a tree whose nodes are all black except for those along a single path of alter- nating red and black nodes. The basic operations that bal- anced-tree algorithms use to main- tain balance under insertion and deletion are known as rotations. In the context of red-black trees, these operations are easily understood as the transformations needed to transform a 3-node whose red link leans to the left to a 3-node whose red link leans to the right and vice- versa. The Java code for these op- erations (for a Node type that we will consider late that contains a left link, a right link, and a color eld that can be set to the value RED to represent the color of the incoming link) is given to the left and to the right on this page. Rotations obvi- ously preserve the two invariants stated above. In red-black trees, we also use a simple operation known as a color ip (shown at the bottom of this page). In terms of 2-3-4 trees, a color ip is the essential operation: it corresponds to splitting a 4-node and passing the middle node up to the parent. A color ip obviously does not change the number of black links on any path from the root to the bottom, but it may introduce two consecu- tive red links higher in the tree, which must be corrected. Red-black BST algorithms differ on whether and when they do rotations and color ips, in order to maintain the global invariants stated at the top of this page.

  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)