Левосторонние красно-чёрные деревья — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Методы)
(Удаление)
Строка 81: Строка 81:
 
   root.color = BLACK
 
   root.color = BLACK
 
</code>
 
</code>
 +
 
<code>
 
<code>
 
  '''Node''' deleteMin( h : '''Node'''):
 
  '''Node''' deleteMin( h : '''Node'''):
Строка 90: Строка 91:
 
   '''return''' fixUp(h)
 
   '''return''' fixUp(h)
 
</code>
 
</code>
 +
 
<code>
 
<code>
 
     '''Node''' moveRedLeft('''Node''' h):
 
     '''Node''' moveRedLeft('''Node''' h):
+
    colorFlip(h):
  colorFlip(h):
+
    '''if''' isRed(h.right.left)
  '''if''' isRed(h.right.left)
 
   
 
 
       h.right = rotateRight(h.right)
 
       h.right = rotateRight(h.right)
 
       h = rotateLeft(h)
 
       h = rotateLeft(h)
 
       colorFlip(h)
 
       colorFlip(h)
+
    '''return''' h   
  '''return''' h   
 
 
</code>   
 
</code>   
  
 
<code>  
 
<code>  
 
     '''Node’’’ moveRedRight(h :'''Node''' ):
 
     '''Node’’’ moveRedRight(h :'''Node''' ):
    colorFlip(h)
+
    colorFlip(h)
    '''if''' isRed(h.left.left))
+
    '''if''' isRed(h.left.left))
   
 
 
       h = rotateRight(h)
 
       h = rotateRight(h)
 
       colorFlip(h)
 
       colorFlip(h)
      
+
     '''return''' h   
  '''return''' h   
 
 
</code>
 
</code>
 
<code>
 
<code>
Строка 123: Строка 120:
 
     '''if''' key.compareTo(h.key) < 0)     
 
     '''if''' key.compareTo(h.key) < 0)     
 
           '''if''' !isRed(h.left) '''&&''' !isRed(h.left.left)
 
           '''if''' !isRed(h.left) '''&&''' !isRed(h.left.left)
                h = moveRedLeft(h)
+
            h = moveRedLeft(h)
            h.left =  delete(h.left, key)
+
          h.left =  delete(h.left, key)
        '''else'''   
+
    '''else'''   
  '''if''' isRed(h.left)
+
      '''if''' isRed(h.left)
    h = rotateRight(h)
+
        h = rotateRight(h)
  '''if''' key.compareTo(h.key) == 0 '''&&''' (h.right == null)
+
      '''if''' key.compareTo(h.key) == 0 '''&&''' (h.right == null)
    '''return''' null
+
        '''return''' null
  '''if''' !isRed(h.right) && !isRed(h.right.left)
+
      '''if''' !isRed(h.right) && !isRed(h.right.left)
    h = moveRedRight(h)
+
        h = moveRedRight(h)
  '''if''' key.compareTo(h.key) == 0
+
      '''if''' key.compareTo(h.key) == 0
 
         h.val = get(h.right, min(h.right).key)
 
         h.val = get(h.right, min(h.right).key)
 
         h.key = min(h.right).key
 
         h.key = min(h.right).key
 
         h.right = deleteMin(h.right)
 
         h.right = deleteMin(h.right)
  '''else'''  
+
      '''else'''  
    h.right = delete(h.right, key)
+
        h.right = delete(h.right, key)
  '''return''' fixUp(h)
+
  '''return''' fixUp(h)
 
</code>
 
</code>

Версия 02:46, 8 декабря 2017

 Определение

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