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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Методы)
Строка 1: Строка 1:
−
{{Определение
+
  Определение
 
|definition = Left-leaning Red-Black Trees .  
 
|definition = Left-leaning Red-Black Trees .  
−
}}
+
 
 
==Вращения==
 
==Вращения==
−
 
−
* <tex> \mathrm{push}(i, x)</tex> {{---}} добавляет элемент <tex>x</tex> в стек узла <tex>i</tex>,
 
−
  '''Stack''' push(i : '''Node''', x : '''T'''):
 
−
    k.value = x
 
−
    k.prev = i
 
−
    s.top = k
 
−
    '''return''' s
 
−
 
−
* <tex>\mathrm{pop}(i)</tex> {{---}} возвращает значение, хранящееся в узле <tex>i</tex> и копирует элемент, предыдущий для него.
 
−
  '''pair<T, Stack>''' pop(i : '''Node'''):
 
−
    '''T''' val = i.value
 
−
    i = i.prev
 
−
    '''return''' pair(val, s)
 
−
 
  
 
<code>
 
<code>
−
   '''Node '''rotateRight(h : '''Node '''):
+
   '''Node''' rotateRight(h : '''Node'''):
 
   x = h.left
 
   x = h.left
 
   h.left= x.right
 
   h.left= x.right
Строка 25: Строка 11:
 
   x.color = h.color
 
   x.color = h.color
 
   h.color = RED
 
   h.color = RED
−
     '''return ''' x
+
     '''return''' x
 
</code>
 
</code>
  
Строка 48: Строка 34:
 
<code>
 
<code>
 
   '''void''' insert( '''key''' : Key, '''value''' : Value ):  
 
   '''void''' insert( '''key''' : Key, '''value''' : Value ):  
−
     root = insert(root, key, value);
+
     root = insert(root, key, value)
−
     root.color = BLACK;
+
     root.color = BLACK
 
</code>
 
</code>
  
 
<code>
 
<code>
−
       '''Node''' insert( h : Node, key : Key, value : Value)
+
       '''Node''' insert( h : '''Node''', key : '''Key''', value : '''Value'''):
−
           if (h == null)      
+
           '''if''' h == null     
−
               '''return''' ''new Node(key, value)'';
+
               '''return''' '''new''' Node(key, value)
−
          if (isRed(h.left) && isRed(h.right)) colorFlip(h);
+
          '''if''' isRed(h.left) '''&&''' isRed(h.right)
−
           int cmp = key.compareTo(h.key);
+
              colorFlip(h)
−
           if (cmp == 0)
+
           '''int''' cmp = key.compareTo(h.key)  
−
               h.val = value;
+
           '''if'''  cmp == 0
−
           else  
+
               h.val = value
−
               if (cmp < 0)
+
           '''else'''
−
                   h.left = insert(h.left, key, value);  
+
               '''if''' cmp < 0  
 +
                   h.left = insert(h.left, key, value)   
 
               '''else'''  
 
               '''else'''  
−
                   h.right = insert(h.right, key, value);
+
                   h.right = insert(h.right, key, value)
−
           if (isRed(h.right) && !isRed(h.left))     
+
           '''if''' isRed(h.right) '''&&''' !isRed(h.left)     
−
               h = rotateLeft(h);
+
               h = rotateLeft(h)
−
           if (isRed(h.left) && isRed(h.left.left))  
+
           '''if''' isRed(h.left) '''&&''' isRed(h.left.left)
−
               h = rotateRight(h);
+
               h = rotateRight(h)
 
       '''return''' ''h''
 
       '''return''' ''h''
 
</code>
 
</code>
  
 
<code>
 
<code>
−
   public Value search(Key key)
+
   '''Value''' search(key : '''Key'''):
−
   Node x = root;
+
   '''Node''' x = root
 
   while (x != null)
 
   while (x != null)
−
       int cmp = key.compareTo(x.key);
+
       '''int''' cmp = key.compareTo(x.key)
−
       if (cmp == 0) return x.val;
+
       if cmp == 0) '''return''' x.val
 
           else
 
           else
−
               if (cmp < 0)  
+
               if cmp < 0)  
−
                   x = x.left;
+
                   x = x.left
 
                   else  
 
                   else  
−
                       if (cmp > 0)  
+
                       if cmp > 0)  
−
                           x = x.right;
+
                           x = x.right
−
           return null;
+
           '''return''' null
 
</code>
 
</code>
 
==Удаление==
 
==Удаление==
 
<code>
 
<code>
−
  void deleteMin()
+
  void deleteMin():
−
   root = deleteMin(root);
+
   root = deleteMin(root)
−
   root.color = BLACK;
+
   root.color = BLACK
 +
</code>
 +
<code>
 +
'''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)
 
</code>
 
</code>
 
<code>
 
<code>
−
Node deleteMin( h : Node)
+
    '''Node''' moveRedLeft('''Node''' h):
−
   if (h.left == null) return null;
+
−
   if (!isRed(h.left) && !isRed(h.left.left))
+
  colorFlip(h):
−
      h = moveRedLeft(h);
+
   '''if''' isRed(h.right.left)
−
  h.left = deleteMin(h.left);
+
   
−
  return fixUp(h);
+
      h.right = rotateRight(h.right)
 +
      h = rotateLeft(h)
 +
      colorFlip(h)
 +
 +
  '''return''' h 
 +
</code> 
 +
 
 +
<code>
 +
    '''Node’’’ moveRedRight(h :'''Node''' ):
 +
    colorFlip(h)
 +
    '''if''' isRed(h.left.left))
 +
   
 +
      h = rotateRight(h)
 +
      colorFlip(h)
 +
   
 +
  '''return''' h 
 +
</code>
 +
<code>
 +
'''void''' delete(key : '''Key'''):
 +
  root = delete(root, key)
 +
  root.color = BLACK
 +
</code>
 +
 
 +
<code>
 +
   '''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)
 
</code>
 
</code>

Версия 02:15, 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)

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Левосторонние_красно-чёрные_деревья&oldid=62515»