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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 50: Строка 50:
  
 
   if (h == null)
 
   if (h == null)
       return new Node(key, value, RED);
+
       return new Node(key, value, RED)
  
 
*Расщепление узла с <tex>4</tex>-я потомками:
 
*Расщепление узла с <tex>4</tex>-я потомками:
Строка 56: Строка 56:
 
[[File:Split4node.png|310px|thumb|upright|Расщепление узла]]
 
[[File:Split4node.png|310px|thumb|upright|Расщепление узла]]
 
   if (isRed(h.left) && isRed(h.right))
 
   if (isRed(h.left) && isRed(h.right))
       colorFlip(h);
+
       colorFlip(h)
  
 
*Принудительное вращение влево:
 
*Принудительное вращение влево:
Строка 62: Строка 62:
 
Если правый предок красный, вращаем текущую вершину влево.
 
Если правый предок красный, вращаем текущую вершину влево.
 
   if (isRed(h.right))
 
   if (isRed(h.right))
       h = rotateLeft(h);
+
       h = rotateLeft(h)
  
 
*Балансировка узла с <tex>4</tex>-я потомками:
 
*Балансировка узла с <tex>4</tex>-я потомками:
Строка 68: Строка 68:
 
Если левый предок красный и левый предок левого предка красный, то вращаем текущую вершину вправо.
 
Если левый предок красный и левый предок левого предка красный, то вращаем текущую вершину вправо.
 
   if (isRed(h.left) && isRed(h.left.left))
 
   if (isRed(h.left) && isRed(h.left.left))
       h = rotateRight(h);
+
       h = rotateRight(h)
 
    
 
    
 
===Псевдокод===
 
===Псевдокод===
Строка 121: Строка 121:
 
===Исправление правых красных связей===
 
===Исправление правых красных связей===
 
*Использование Переворота цветов и вращений  сохраняет баланс черной связи.
 
*Использование Переворота цветов и вращений  сохраняет баланс черной связи.
*После удаления необходимо исправить правые красные связи и устранить узлы с <tex>4--</tex>я потомками
+
*После удаления необходимо исправить правые красные связи и устранить узлы с <tex>4 -- </tex>я потомками
 
       <span style="color:#008000">//Исправление правых красных связей</span>
 
       <span style="color:#008000">//Исправление правых красных связей</span>
 
   '''Node''' fixUp(h : '''Node''')   
 
   '''Node''' fixUp(h : '''Node''')   
 
       '''if''' (isRed(h.right))   
 
       '''if''' (isRed(h.right))   
           h = rotateLeft(h);  
+
           h = rotateLeft(h)   
 
       <span style="color:#008000">//Вращение <tex>2</tex>-ой красной пары пары</span>
 
       <span style="color:#008000">//Вращение <tex>2</tex>-ой красной пары пары</span>
 
       '''if''' (isRed(h.left) '''&&''' isRed(h.left.left))
 
       '''if''' (isRed(h.left) '''&&''' isRed(h.left.left))
           h = rotateRight(h);  
+
           h = rotateRight(h)   
 
       <span style="color:#008000">//Балансировка узла с <tex>4</tex>-я потомками</span>
 
       <span style="color:#008000">//Балансировка узла с <tex>4</tex>-я потомками</span>
 
       '''if''' (isRed(h.left) '''&&''' isRed(h.right))
 
       '''if''' (isRed(h.left) '''&&''' isRed(h.right))
           colorFlip(h);  
+
           colorFlip(h)   
   '''return''' h;
+
   '''return''' h
  
 
===Удаление максимума===
 
===Удаление максимума===
Строка 153: Строка 153:
 
===Псевдокод===
 
===Псевдокод===
 
  '''void''' deleteMax()               
 
  '''void''' deleteMax()               
     root = deleteMax(root);          
+
     root = deleteMax(root)         
     root.color = BLACK;                
+
     root.color = BLACK               
  
 
  '''Node''' moveRedLeft(h : '''Node''')
 
  '''Node''' moveRedLeft(h : '''Node''')
     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                                               
  
 
  '''Node''' deleteMax(h : '''Node''')
 
  '''Node''' deleteMax(h : '''Node''')
 
     if (isRed(h.left))                                         
 
     if (isRed(h.left))                                         
 
     <span style="color:#008000">//вращаем все 3-вершины вправо</span>
 
     <span style="color:#008000">//вращаем все 3-вершины вправо</span>
         h = rotateRight(h);
+
         h = rotateRight(h)
 
     <span style="color:#008000">//поддерживаем инвариант (h должен быть красным)</span>
 
     <span style="color:#008000">//поддерживаем инвариант (h должен быть красным)</span>
 
     if (h.right == null)   
 
     if (h.right == null)   
         return null;
+
         return null
 
     <span style="color:#008000">//заимствуем у брата если необходимо</span>
 
     <span style="color:#008000">//заимствуем у брата если необходимо</span>
 
     if (!isRed(h.right) '''&&''' !isRed(h.right.left))  
 
     if (!isRed(h.right) '''&&''' !isRed(h.right.left))  
         h = moveRedRight(h);
+
         h = moveRedRight(h)
 
     <span style="color:#008000">// опускаемся на один уровень глубже </span>
 
     <span style="color:#008000">// опускаемся на один уровень глубже </span>
     h.left = deleteMax(h.left);
+
     h.left = deleteMax(h.left)  
 
     <span style="color:#008000">//исправление правых красных ссылок и 4-вершин на пути вверх</span>
 
     <span style="color:#008000">//исправление правых красных ссылок и 4-вершин на пути вверх</span>
     '''return''' fixUp(h);
+
     '''return''' fixUp(h)
  
 
==Удаление минимума==
 
==Удаление минимума==
Строка 187: Строка 187:
 
===Псевдокод===  
 
===Псевдокод===  
 
  '''Node''' moveRedLeft(h : '''Node''')
 
  '''Node''' moveRedLeft(h : '''Node''')
     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
  
 
  '''void''' deleteMin()
 
  '''void''' deleteMin()
     root = deleteMin(root);
+
     root = deleteMin(root)
     root.color = BLACK;
+
     root.color = BLACK
  
 
  '''Node''' deleteMin(h : '''Node''')
 
  '''Node''' deleteMin(h : '''Node''')
 
     <span style="color:#008000">//удаляем узел на нижнем уровне(h должен быть красным по инварианту)</span>
 
     <span style="color:#008000">//удаляем узел на нижнем уровне(h должен быть красным по инварианту)</span>
 
     if (h.left == ''null'')     
 
     if (h.left == ''null'')     
         '''return''' ''null'';
+
         '''return''' ''null''
 
       <span style="color:#008000">//Если необходимо, пропушим  красную ссылку вниз</span>
 
       <span style="color:#008000">//Если необходимо, пропушим  красную ссылку вниз</span>
 
     '''if  (!'''isRed(h.left) '''&&  !'''isRed(h.left.left))
 
     '''if  (!'''isRed(h.left) '''&&  !'''isRed(h.left.left))
           h = moveRedLeft(h);
+
           h = moveRedLeft(h)
 
       <span style="color:#008000">//опускаемся на уровень ниже </span>
 
       <span style="color:#008000">//опускаемся на уровень ниже </span>
     h.left = deleteMin(h.left);
+
     h.left = deleteMin(h.left)
  '''return''' fixUp(h);
+
  '''return''' fixUp(h)
  
 
==Асимптотика==
 
==Асимптотика==

Версия 14:36, 15 июня 2018

Определение:
Левосторонние красно-черные деревья — модификация красно-черных деревьев, имеющая ряд преимуществ на классической структурой. Разработана Робертом Соджевиском в [math]2008[/math] году.

Преимущества

  • необходимо менее [math]80[/math] строчек кода для реализации структуры
  • более быстрая вставка, удаление элементов
  • простота

Вращения

Чтобы поддерживать красно-черные двоичное деревья поиска необходимо соблюдать следующие инвариантные свойства при вставке и удалении:

  • Ни один обход от корня до листьев дерева не содержит двух последовательных красных узлов.
  • Количество черных узлов на каждом таком пути одинаково.

Из этих инвариантов следует, что длина каждого пути от корня до листьев в красно-черном дереве с [math]N[/math] узлами не превышает [math]2 \cdot \log(N)[/math] .

Основные операции, используемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, называются вращениями. Эти операции трансформируют [math]3[/math]-узел,левый потомок которого окрашен в красный, в [math]3[/math]-узел, правый потомок которого окрашен в красный и наоборот. Вращения сохраняют два указанных выше инварианта, не изменяют поддеревья узла.

Псевокод

Rotate Right
  Node rotateRight(h : Node) :
      x = h.left
      h.left= x.right
      x.right= h
      x.color = h.color
      h.color = RED
   return x
Rotate Left
  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 = [math] ![/math] h.right.color

Вставка

Вставка в ЛСКЧД базируется на [math]4[/math] простых операциях:

  • Вставка нового узла к листу дерева:

Если высота узла нулевая, возвращаем новый красный узел.

Вставка нового узла
 if (h == null)
      return new Node(key, value, RED)
  • Расщепление узла с [math]4[/math]-я потомками:

Если левый предок и правый предок красные, запускаем вращение цветов от текущего узла.

Расщепление узла
 if (isRed(h.left) && isRed(h.right))
     colorFlip(h)
  • Принудительное вращение влево:
Принудительное вращение

Если правый предок красный, вращаем текущую вершину влево.

 if (isRed(h.right))
     h = rotateLeft(h)
  • Балансировка узла с [math]4[/math]-я потомками:
Балансировка

Если левый предок красный и левый предок левого предка красный, то вращаем текущую вершину вправо.

 if (isRed(h.left) && isRed(h.left.left))
     h = rotateRight(h)
  

Псевдокод

 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)
      //Расщепление узла с [math]4[/math]-я потомками
     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)
          //Балансировка узла с [math]4[/math]-я потомками
         if (isRed(h.left) && isRed(h.left.left))
             h = rotateRight(h)
 return h

Поиск

Поиск в левосторонних красно-черных деревьях эквивалентен поиску в наивной реализации дерева поиска. Для поиска элемента в красно-черных деревьях дереве поиска можно воспользоваться циклом, проходит от вершины до искомого элемента. Если же элемент отсутствует цикл пройдет то листа дерева и прервется. Для каждого узла цикл сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае цикл повторяет для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы [math]O(h)[/math], где [math]h[/math] — высота дерева.

Псевдокод

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

Удаление

Исправление правых красных связей

  • Использование Переворота цветов и вращений сохраняет баланс черной связи.
  • После удаления необходимо исправить правые красные связи и устранить узлы с [math]4 -- [/math]я потомками
      //Исправление правых красных связей
  Node fixUp(h : Node)  
      if (isRed(h.right))  
          h = rotateLeft(h)  
      //Вращение [math]2[/math]-ой красной пары пары
      if (isRed(h.left) && isRed(h.left.left))
          h = rotateRight(h)  
      //Балансировка узла с [math]4[/math]-я потомками
      if (isRed(h.left) && isRed(h.right))
          colorFlip(h)  
  return h

Удаление максимума

  • Спускаемся вниз по правому краю дерева.
  • Если поиск заканчивается на узле с [math]4[/math]-мя или [math]5[/math]-ю потомками, просто удаляем узел.
Узлы до и после удаления
  • Удаление узла с [math]2[/math]-я потомками разрушает баланс

Соответственно спускаясь вниз по дереву необходимо поддерживать следующий инвариант : количество потомков узла не должно быть ровно [math]2[/math]-м.

ChangeNode.png

Будем поддерживать инвариант : Для любого узла либо сам узел, либо правый предок узла красный. Будем придерживаться тактики , что удалять лист легче, чем внутренний узел.

Заметим, что если правый потомок вершины и правый потомок правого потомка вершины черные, необходимо переместить левую красную ссылку вправо для сохранения инварианта.

Перемещение красной ссылки. Простой случай
Перемещение красной ссылки. Сложный случай

Псевдокод

void deleteMax()              
    root = deleteMax(root)         
    root.color = BLACK               
Node moveRedLeft(h : Node)
    colorFlip(h)                     
    if (isRed(h.right.left)                
        h.right = rotateRight(h.right)       
        h = rotateLeft(h)                   
        colorFlip(h)                          
return h                                              
Node deleteMax(h : Node)
    if (isRed(h.left))                                         
    //вращаем все 3-вершины вправо
        h = rotateRight(h)
    //поддерживаем инвариант (h должен быть красным)
    if (h.right == null)   
        return null
    //заимствуем у брата если необходимо
    if (!isRed(h.right) && !isRed(h.right.left)) 
        h = moveRedRight(h)
    // опускаемся на один уровень глубже 
    h.left = deleteMax(h.left) 
    //исправление правых красных ссылок и 4-вершин на пути вверх
    return fixUp(h)

Удаление минимума

Поддерживаем инвариант: вершина или левый ребенок вершины красный.

Заметим, что если левый потомок вершины и левый потомок левого потомка вершины черные, необходимо переместить красную ссылку для сохранения инварианта.

Перемещение красной ссылки. Простой случай
Перемещение красной ссылки. Сложный случай

Псевдокод

Node moveRedLeft(h : Node)
    colorFlip(h)
    if (isRed(h.right.left))
        h.right = rotateRight(h.right)
        h = rotateLeft(h)
        colorFlip(h)
return h
void deleteMin()
    root = deleteMin(root)
    root.color = BLACK
Node deleteMin(h : Node)
    //удаляем узел на нижнем уровне(h должен быть красным по инварианту)
    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)

Асимптотика

Асимптотика методов в левосторонних красно-черных деревьях эквивалентна асимптотике левосторонних красно-черных деревьях.


См.также

Источники информации

  • Robert Sedgewick "Left-leaning Red-Black Trees" ,Department of Computer Science, Princeton University