2-3 дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Нахождение m следующих элементов)
м (rollbackEdits.php mass rollback)
 
(не показано 55 промежуточных версий 8 участников)
Строка 1: Строка 1:
[[Файл:23treemain.png|400px|пример 2-3 дерева|thumb]]''' 2-3 дерево '''(англ. ''Heapsort'') — структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. Является частным случаем [[B-дерево#B.2B-.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.BE|B+ дерева]].
+
[[Файл:23treemain.png|400px|Пример 2-3 дерева|thumb]]''' 2-3 дерево '''(англ. ''2-3 tree'') — структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. Является частным случаем [[B-дерево#B.2B-.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.BE|B+ дерева]].
 
== Свойства ==
 
== Свойства ==
 
2-3 дерево {{---}} сбалансированное дерево поиска, обладающее следующими свойствами:
 
2-3 дерево {{---}} сбалансированное дерево поиска, обладающее следующими свойствами:
Строка 6: Строка 6:
 
*сыновья упорядочены по значению максимума поддерева сына,
 
*сыновья упорядочены по значению максимума поддерева сына,
 
*все листья лежат на одной глубине,
 
*все листья лежат на одной глубине,
*Высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> {{---}} количество элементов в дереве.
+
*высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> {{---}} количество элементов в дереве.
  
 
== Операции ==
 
== Операции ==
Строка 25: Строка 25:
 
*у текущей вершины три сына. Если второе значение меньше <tex>x</tex>, то <tex>t = \mathtt{t.sons[2]}</tex>. Если первое значение меньше <tex>x</tex>, то <tex>t = \mathtt{t.sons[1]}</tex>, иначе <tex>t = \mathtt{t.sons[0]}</tex>.
 
*у текущей вершины три сына. Если второе значение меньше <tex>x</tex>, то <tex>t = \mathtt{t.sons[2]}</tex>. Если первое значение меньше <tex>x</tex>, то <tex>t = \mathtt{t.sons[1]}</tex>, иначе <tex>t = \mathtt{t.sons[0]}</tex>.
  
  '''Node''' search('''int''' x):
+
  '''T''' search('''T''' x):
 
   Node t = root
 
   Node t = root
 
   '''while''' (t не является листом)
 
   '''while''' (t не является листом)
Строка 31: Строка 31:
 
       '''if''' (t.keys[0] < x)
 
       '''if''' (t.keys[0] < x)
 
         t = t.sons[1]
 
         t = t.sons[1]
       '''else''' t = t.sons[0]
+
       '''else'''  
     '''else'''
+
        t = t.sons[0]
      '''if''' (t.keys[1] < x)
+
     '''else''' '''if''' (t.keys[1] < x)
        t = t.sons[2]
+
      t = t.sons[2]
      '''else'''
+
    '''else''' '''if''' (t.keys[0] < x)
        '''if''' (t.keys[0] < x)
+
      t = t.sons[1]
          t = t.sons[1]
+
    '''else'''  
        '''else''' t = t.sons[0]
+
      t = t.sons[0]
   '''return''' t
+
   '''return''' t.keys[0]
Пример поиска в 2-3 дереве, так как элемент <tex>6</tex> существует, то был возвращен корректный узел, так как элемента <tex>10</tex> нет, возвращается некорректный узел. На основе этого можно сделать метод <tex>\mathtt{exist}</tex>, проверяющий наличии элемента в дереве.
 
  
[[Файл:23treesearch.png|thumb|center|600px|поиск элемента 2]]
+
[[Файл:23treesearch.png|thumb|center|600px|Поиск элемента 19, оранжевые стрелки обозначают путь по дереву при поиске]]
  
 
=== Вставка элемента ===
 
=== Вставка элемента ===
Строка 51: Строка 50:
 
Найдем сперва, где бы находился элемент, применив <tex>\mathtt{search(x)}</tex>. Далее проверим есть ли у этого узла родитель, если его нет, то в дереве всего один элемент {{---}} лист. Возьмем этот лист и новый узел, и создадим для них родителя, лист и новый узел расположим в порядке возрастания.
 
Найдем сперва, где бы находился элемент, применив <tex>\mathtt{search(x)}</tex>. Далее проверим есть ли у этого узла родитель, если его нет, то в дереве всего один элемент {{---}} лист. Возьмем этот лист и новый узел, и создадим для них родителя, лист и новый узел расположим в порядке возрастания.
  
Если родитель существует, то подвесим к нему ещё одного сына. Если сыновей стало <tex>4</tex>, то разделим родителя на два узла, и повторим разделение теперь для его родителя (перед разделением обновим ключи).
+
Если родитель существует, то подвесим к нему ещё одного сына. Если сыновей стало <tex>4</tex>, то разделим родителя на два узла, и повторим разделение теперь для его родителя, ведь у него тоже могло быть уже <tex>3</tex> сына, а мы разделили и у него стало на <tex>1</tex> сына больше. (перед разделением обновим ключи).
  
  splitParent('''Node''' t):
+
  '''function''' splitParent('''Node''' t):
 
   '''if''' (t.length > 3)  
 
   '''if''' (t.length > 3)  
    Node a;
+
    Node a = Node(sons = {t.sons[2], t.sons[3]}, keys = {t.keys[2]}, parent = t.parent, length = 2)
    a.sons[0] = t.sons[2]
+
    t.sons[2].parent = a
    a.sons[1] = t.sons[3]
+
    t.sons[3].parent = a
    t.sons[2].parent = a
+
    t.length = 2
    t.sons[3].parent = a
+
    t.sons[2] = ''null''
    a.keys[0] = t.keys[2]
+
    t.sons[3] = ''null''
    a.length = 2
+
    '''if''' (t.parent != ''null'')
    t.length = 2
+
      t.parent[t.length] = a
    t.sons[2] = '''null'''
+
      t.length++
    t.sons[3] = '''null'''
+
      сортируем сыновей у t.parent
    '''if''' (t.parent != '''null''')
+
      splitParent(t.parent)
      t.parent[t.length] = a
+
    '''else'''                  <font color=green>// мы расщепили корень, надо подвесить его к общему родителю, который будет новым корнем</font>
      t.length++
+
    Node t = root
      сортируем сыновей у t.parent
+
    root.sons[0] = t
      splitParent(t.parent)
+
    root.sons[1] = a
    '''else'''                  //мы расщепили корень, надо подвесить его к общему родителю, который будет новым корнем
+
    t.parent = root
      Node t = root
+
    a.parent = root
      root.sons[0] = t
+
    root.length = 2
      root.sons[1] = a
+
    сортируем сыновей у root
      t.parent = root
 
      a.parent = root
 
      root.length = 2
 
      сортируем сыновей у root
 
 
Если сыновей стало <tex>3</tex>, то ничего не делаем. Далее необходимо восстановить ключи на пути от новой вершины до корня:
 
Если сыновей стало <tex>3</tex>, то ничего не делаем. Далее необходимо восстановить ключи на пути от новой вершины до корня:
  updateKeys('''Node''' t):  
+
  '''function''' updateKeys('''Node''' t):  
 
   Node a = t.parent
 
   Node a = t.parent
   '''while''' (a != '''null''')
+
   '''while''' (a != ''null'')
 
     '''for''' i = 0 .. a.length - 1
 
     '''for''' i = 0 .. a.length - 1
       a.keys[i] = max(a.sons[i]) //max {{---}} возвращает максимальное значение в поддереве.
+
       a.keys[i] = max(a.sons[i]) <font color=green>// max {{---}} возвращает максимальное значение в поддереве.</font>
     a = a.parent                //Примечание: max легко находить, если хранить максимум  
+
     a = a.parent                <font color=green>// Примечание: max легко находить, если хранить максимум </font>
                                 //правого поддерева в каждом узле {{---}} это значение и будет max(a.sons[i])
+
                                 <font color=green>// правого поддерева в каждом узле {{---}} это значение и будет max(a.sons[i])</font>
  
 
<tex>\mathtt{updateKeys}</tex> необходимо запускать от нового узла.
 
<tex>\mathtt{updateKeys}</tex> необходимо запускать от нового узла.
 
Добавление элемента:
 
Добавление элемента:
  insert('''int''' x):
+
  '''function''' insert('''T''' x):
Node n = Node(x)
+
  Node n = Node(x)
'''if''' (root == null)  
+
  '''if''' (root == ''null'')  
  root = n
+
    root = n
  return
+
    '''return'''
Node a = search(x)
+
  Node a = searchNode(x)    
'''if''' (a.parent == '''null''')  
+
  '''if''' (a.parent == ''null'')  
  Node t = root
+
    Node t = root
  root.sons[0] = t
+
    root.sons[0] = t
  root.sons[1] = n
+
    root.sons[1] = n
  t.parent = root
+
    t.parent = root
  n.parent = root
+
    n.parent = root
  root.length = 2
+
    root.length = 2
  сортируем сыновей у root
+
    сортируем сыновей у root
'''else'''  
+
  '''else'''  
  Node p = a.parent
+
    Node p = a.parent
  p.sons[p.length] = n
+
    p.sons[p.length] = n
  p.length++
+
    p.length++
  n.parent = p
+
    n.parent = p
  сортируем сыновей у p
+
    сортируем сыновей у p
 +
    updateKeys(n)
 +
    split(n)
 
   updateKeys(n)  
 
   updateKeys(n)  
  split(n)
 
updateKeys(n)
 
 
Так как мы спускаемся один раз, и поднимаемся вверх при расщеплении родителей не более одного раза, то <tex>\mathtt{insert}</tex> работает за <tex>O(\log{n})</tex>.
 
Так как мы спускаемся один раз, и поднимаемся вверх при расщеплении родителей не более одного раза, то <tex>\mathtt{insert}</tex> работает за <tex>O(\log{n})</tex>.
  
 
Примеры добавления:
 
Примеры добавления:
  
[[Файл:23treeinsert.png|thumb|center|добавление элемента с ключом 6|600px]]
+
[[Файл:23treeinsert.png|thumb|center|Добавление элемента с ключом 6|600px]]
  
 
=== Удаление элемента ===
 
=== Удаление элемента ===
 
*<tex>x</tex> {{---}} значение удаляемого узла,
 
*<tex>x</tex> {{---}} значение удаляемого узла,
*<tex>t</tex> {{---}} текущий узел.
+
*<tex>t</tex> {{---}} текущий узел,
Пусть изначально <tex>t = \mathtt{search(x)}</tex> {{---}} узел, где находится <tex>x</tex>.
+
*<tex>b</tex> {{---}} брат <tex>t</tex>,
 +
*<tex>p</tex> {{---}} отец <tex>t</tex>,
 +
*<tex>np</tex> {{---}} соседний брат <tex>p</tex>,
 +
*<tex>gp</tex> {{---}} отец <tex>p</tex>.
 +
Пусть изначально <tex>t = \mathtt{searchNode(x)}</tex> {{---}} узел, где находится <tex>x</tex>.
 +
 
 +
Если у <tex>t</tex> не существует родителя, то это корень (одновременно и единственный элемент в дереве). Удалим его.
 +
 
 +
Если <tex>p</tex> существует, и у него строго больше <tex>2</tex> сыновей, то просто удалим <tex>t</tex>, а у <tex>p</tex> уменьшим количество детей.
 +
 
 +
Если у родителя <tex>t</tex> два сына, рассмотрим возможные случаи (сперва везде удаляем <tex>t</tex>):
 +
*<tex>np</tex> не существует, тогда мы удаляем одного из сыновей корня, следовательно, другой сын становится новым корнем,
 +
*у <tex>gp</tex> оказалось <tex>2</tex> сына, у <tex>np</tex> оказалось <tex>2</tex> сына. Подвесим <tex>b</tex> к <tex>np</tex> и удалим <tex>p</tex>. Так как у <tex>gp</tex> {{---}} родителя <tex>p</tex>, оказалось тоже два сына, повторяем для <tex>p</tex> такие же рассуждения,
 +
*у <tex>gp</tex> оказалось <tex>2</tex> или <tex>3</tex> сына, у <tex>np</tex> оказалось <tex>3</tex> сына. Просто заберем ближайшего к нам сына у <tex>np</tex> и прицепим его к <tex>p</tex>. Восстановим порядок в сыновьях <tex>p</tex>. Теперь у <tex>p</tex> оказалось снова два сына и все узлы 2-3 дерева корректны,
 +
*у <tex>gp</tex> оказалось <tex>3</tex> сына, у <tex>np</tex> оказалось <tex>2</tex> сына. Подвесим <tex>b</tex> к <tex>np</tex> и удалим <tex>p</tex>, а у <tex>gp</tex> уменьшим количество детей. Так как у <tex>np</tex> оказалось три сына, а у <tex>gp</tex> все ещё больше одного сына, то все узлы 2-3 дерева корректны.
 +
 
 +
 
  
Если у <tex>t</tex> не существует родителя, то это корень. Удалим его.
+
Обобщим алгоритм при удалении когда у родителя <tex>t</tex> два сына:
 +
*Если <tex>np</tex> не существует, то оказывается, что мы сейчас удаляем какого-то из сыновей корня (для определенности далее левого, с правым аналогично). Тогда теперь правый сын становится корнем. На этом удаление заканчивается.
  
Если у <tex>t</tex> существует родитель, и у него <tex>3</tex> сына, то просто удалим <tex>t</tex>. Обновим ключи, запустив <tex>\mathtt{updateKeys}</tex> от любого брата <tex>t</tex>.
+
*Если <tex>np</tex> существует, то удалим <tex>t</tex>, а его брата (<tex>b</tex>) перецепим к <tex>np</tex>. Теперь у <tex>np</tex> могло оказаться <tex>4</tex> сына, поэтому повторим аналогичные действия из <tex>\mathtt{insert}</tex>: вызовем <tex>\mathtt{updateKeys}(b)</tex> и <tex>\mathtt{splitParent}(np)</tex>. Теперь рекурсивно удалим <tex>p</tex>.
  
Если у родителя(<tex>\mathtt{t.parent}</tex>) <tex>2</tex> сына, то удалим <tex>t</tex>, а его брата(<tex>b</tex> перецепим к родителю соседнего листа(обозначим его за <tex>p</tex>). Вызовем <tex>\mathtt{updateKeys}(b)</tex> и <tex>\mathtt{splitParent}(p)</tex>, так как у <tex>p</tex> могло оказаться <tex>4</tex> сына. Удалим теперь и <tex>\mathtt{t.parent}</tex>. После возврата из рекурсии обновим все ключи с помощью <tex>\mathtt{updateKeys()}</tex>, запустившись от <tex>b</tex>.
+
В результате мы получаем корректное по структуре 2-3 дерево, но у нас есть нарушение в ключах в узлах, исправим их с помощью <tex>\mathtt{updateKeys()}</tex>, запустившись от <tex>b</tex>.
[[Файл:23treedelete.png|thumb|center|удаление элемента с ключом 2|1150px]]
+
[[Файл:23treedelete.png|thumb|center|Удаление элемента с ключом 2|1150px]]
  
 
=== Следующий и предыдущий ===
 
=== Следующий и предыдущий ===
 
*<tex>x</tex> {{---}} поисковый параметр,
 
*<tex>x</tex> {{---}} поисковый параметр,
 
*<tex>t</tex> {{---}} текущий узел.
 
*<tex>t</tex> {{---}} текущий узел.
В силу того, что наши узлы отсортированы по максимуму в поддереве, то следующий объект это соседний лист справа. Попасть туда можно следующим образом:
+
В силу того, что наши узлы отсортированы по максимуму в поддереве, то следующий объект {{---}} это соседний лист справа. Попасть туда можно следующим образом:
 
будем подниматься вверх, пока у нас не появится первой возможности свернуть направо вниз. Как только мы свернули направо вниз, будем идти всегда влево. Таким образом, мы окажемся в соседнем листе. Если мы не смогли ни разу свернуть направо вниз, и пришли в корень, то следующего объекта не существует. Случай с предыдущим симметричен.
 
будем подниматься вверх, пока у нас не появится первой возможности свернуть направо вниз. Как только мы свернули направо вниз, будем идти всегда влево. Таким образом, мы окажемся в соседнем листе. Если мы не смогли ни разу свернуть направо вниз, и пришли в корень, то следующего объекта не существует. Случай с предыдущим симметричен.
   Node next('''int x''')
+
   '''T''' next('''T''' x):
  Node t = search(x)
+
    Node t = searchNode(x)
  '''if''' (t.keys[0] > x) //x не было в дереве, и мы нашли следующий сразу
+
    '''if''' (t.keys[0] > x) <font color=green> //x не было в дереве, и мы нашли следующий сразу</font>
    '''return''' t
+
      '''return''' t.keys[0]
  '''while''' (t != '''null''')
+
    '''while''' (t != ''null'')
    t = t.parent
+
      t = t.parent
    if (можно свернуть направо вниз)
+
      '''if''' (можно свернуть направо вниз)
    в t помещаем вершину, в которую свернули
+
      в t помещаем вершину, в которую свернули
    '''while''' (пока t {{---}} не лист)
+
      '''while''' (пока t {{---}} не лист)
      t = t.sons[0]
+
        t = t.sons[0]
 
       '''return''' t
 
       '''return''' t
  '''return''' t;
+
    '''return''' t.keys[0]
 
      
 
      
  
[[Файл:23treenext.png|thumb|center|400px|путь при поиске следующего элемента после 2]]
+
[[Файл:23treenext.png|thumb|center|400px|Путь при поиске следующего элемента после 2]]
  
 
=== Нахождение m следующих элементов ===
 
=== Нахождение m следующих элементов ===
B+ деревья, поддерживают операцию <tex>\mathtt{find}</tex>, которая позволяет находить m следующих элементов. Наивная реализация выглядит следующим образом, будем вызывать <tex>m</tex> раз поиск следующего элемента, такое решение работает за <tex>O(m * \log{n})</tex>. Но 2-3 деревья, позволяют находить m следующих элементов за <tex>O(m + \log{n})</tex>, что значительно ускоряет поиск при больших <tex>m</tex>.
+
B+ деревья, поддерживают операцию <tex>\mathtt{find}</tex>, которая позволяет находить m следующих элементов. Наивная реализация выглядит следующим образом: будем вызывать <tex>m</tex> раз поиск следующего элемента, такое решение работает за <tex>O(m \log{n})</tex>. Но 2-3 деревья, позволяют находить m следующих элементов за <tex>O(m + \log{n})</tex>, что значительно ускоряет поиск при больших <tex>m</tex>.
 
По построению, все листья у нас отсортированы в порядке возрастания, воспользуемся этим для нахождения m элементов. Нам необходимо связать листья, для этого модифицируем
 
По построению, все листья у нас отсортированы в порядке возрастания, воспользуемся этим для нахождения m элементов. Нам необходимо связать листья, для этого модифицируем
 
<tex>\mathtt{insert}</tex> и <tex>\mathtt{delete}</tex>. Добавим к узлам следующие поля:
 
<tex>\mathtt{insert}</tex> и <tex>\mathtt{delete}</tex>. Добавим к узлам следующие поля:
Строка 160: Строка 172:
 
Изменим <tex>\mathtt{insert}</tex> следующим образом: в самом конце, после того как мы уже обновили все ключи, найдем <tex>\mathtt{next(t)}</tex> и запишем ссылку на него в <tex>\mathtt{t.right}</tex>. Аналогично с левым.
 
Изменим <tex>\mathtt{insert}</tex> следующим образом: в самом конце, после того как мы уже обновили все ключи, найдем <tex>\mathtt{next(t)}</tex> и запишем ссылку на него в <tex>\mathtt{t.right}</tex>. Аналогично с левым.
  
Пусть <tex>t</tex> {{---}} удаляемый узел. Изменим <tex>\mathtt{insert}</tex> следующим образом: в самом начале, до удаления <tex>t</tex>, найдем следующий (<tex>mathtt{next}</tex>) и запишем в (<tex>mathtt{next.left}</tex>) правый лист относительно <tex>t</tex>. С левым поступим аналогично.
+
Пусть <tex>t</tex> {{---}} удаляемый узел. Изменим <tex>\mathtt{delete}</tex> следующим образом: в самом начале, до удаления <tex>t</tex>, найдем следующий <tex>\mathtt{next}</tex> и запишем в <tex>\mathtt{next.left}</tex> правый лист относительно <tex>t</tex>. С левым поступим аналогично.
  
 
В итоге, мы имеем двусвязный список в листьях, и чтобы нам вывести <tex>m</tex> элементов, нам достаточно один раз найти нужный элемент и пробежаться вправо на <tex>m</tex> элементов.
 
В итоге, мы имеем двусвязный список в листьях, и чтобы нам вывести <tex>m</tex> элементов, нам достаточно один раз найти нужный элемент и пробежаться вправо на <tex>m</tex> элементов.
Строка 166: Строка 178:
  
  
[[Файл:23treefindm.png|thumb|изменение ссылок при добавлении нового элемента|thumb|center|800px]]
+
[[Файл:23treefindm.png|thumb|Изменение ссылок при добавлении нового элемента|thumb|center|800px]]
  
 
== См. также ==
 
== См. также ==
Строка 179: Строка 191:
 
* [http://rain.ifmo.ru/cat/view.php/vis/trees/2-3-2002 rain.ifmo.ru {{---}} Визуализатор 2-3 дерева]
 
* [http://rain.ifmo.ru/cat/view.php/vis/trees/2-3-2002 rain.ifmo.ru {{---}} Визуализатор 2-3 дерева]
 
* [http://ru.wikipedia.org/wiki/2-3-дерево Википедия {{---}} 2-3 дерево]
 
* [http://ru.wikipedia.org/wiki/2-3-дерево Википедия {{---}} 2-3 дерево]
* Д. Кнут «Искусство программирования. Сортировка и поиск» {{---}} стр. 508 - 509
+
* Д. Кнут «Искусство программирования. Сортировка и поиск» {{---}} стр. 508-509
  
  

Текущая версия на 19:39, 4 сентября 2022

Пример 2-3 дерева
2-3 дерево (англ. 2-3 tree) — структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. Является частным случаем B+ дерева.

Свойства

2-3 дерево — сбалансированное дерево поиска, обладающее следующими свойствами:

  • нелистовые вершины имеют либо [math]2[/math], либо [math]3[/math] сына,
  • нелистовая вершина, имеющая двух сыновей, хранит максимум левого поддерева. Нелистовая вершина, имеющая трех сыновей, хранит два значения. Первое значение хранит максимум левого поддерева, второе максимум центрального поддерева,
  • сыновья упорядочены по значению максимума поддерева сына,
  • все листья лежат на одной глубине,
  • высота 2-3 дерева [math]O(\log{n})[/math], где [math] n [/math] — количество элементов в дереве.

Операции

Введем следующие обозначения:

  • [math]\mathtt{root}[/math] — корень 2-3 дерева.

Каждый узел дерева обладает полями:

  • [math]\mathtt{parent}[/math] — родитель узла,
  • [math]\mathtt{sons}[/math] — сыновья узла,
  • [math]\mathtt{keys}[/math] — ключи узла,
  • [math]\mathtt{length}[/math] — количество сыновей.

Поиск

  • [math]x[/math] — искомое значение,
  • [math]t[/math] — текущая вершина в дереве.

Изначально [math]t = \mathtt{root}[/math]. Будем просматривать ключи в узлах, пока узел не является листом. Рассмотрим два случая:

  • у текущей вершины два сына. Если её значение меньше [math]x[/math], то [math]t = \mathtt{t.sons[1]}[/math], иначе [math]t = \mathtt{t.sons[0]}[/math].
  • у текущей вершины три сына. Если второе значение меньше [math]x[/math], то [math]t = \mathtt{t.sons[2]}[/math]. Если первое значение меньше [math]x[/math], то [math]t = \mathtt{t.sons[1]}[/math], иначе [math]t = \mathtt{t.sons[0]}[/math].
T search(T x):
  Node t = root
  while (t не является листом)
    if (t.length == 2)
      if (t.keys[0] < x)
        t = t.sons[1]
      else 
        t = t.sons[0]
    else if (t.keys[1] < x)
      t = t.sons[2]
    else if (t.keys[0] < x)
      t = t.sons[1]
    else 
      t = t.sons[0]
  return t.keys[0]
Поиск элемента 19, оранжевые стрелки обозначают путь по дереву при поиске

Вставка элемента

  • [math]x[/math] — добавляемое значение,
  • [math]t[/math] — текущая вершина в дереве. Изначально [math]t = \mathtt{root}[/math].

Если корня не существует — дерево пустое, то новый элемент и будет корнем (одновременно и листом). Иначе поступим следующим образом:

Найдем сперва, где бы находился элемент, применив [math]\mathtt{search(x)}[/math]. Далее проверим есть ли у этого узла родитель, если его нет, то в дереве всего один элемент — лист. Возьмем этот лист и новый узел, и создадим для них родителя, лист и новый узел расположим в порядке возрастания.

Если родитель существует, то подвесим к нему ещё одного сына. Если сыновей стало [math]4[/math], то разделим родителя на два узла, и повторим разделение теперь для его родителя, ведь у него тоже могло быть уже [math]3[/math] сына, а мы разделили и у него стало на [math]1[/math] сына больше. (перед разделением обновим ключи).

function splitParent(Node t):
 if (t.length > 3) 
   Node a = Node(sons = {t.sons[2], t.sons[3]}, keys = {t.keys[2]}, parent = t.parent, length = 2)
   t.sons[2].parent = a
   t.sons[3].parent = a
   t.length = 2
   t.sons[2] = null
   t.sons[3] = null
   if (t.parent != null)
     t.parent[t.length] = a
     t.length++
     сортируем сыновей у t.parent
     splitParent(t.parent)
   else                   // мы расщепили корень, надо подвесить его к общему родителю, который будет новым корнем
    Node t = root
    root.sons[0] = t
    root.sons[1] = a
    t.parent = root
    a.parent = root
    root.length = 2
    сортируем сыновей у root

Если сыновей стало [math]3[/math], то ничего не делаем. Далее необходимо восстановить ключи на пути от новой вершины до корня:

function updateKeys(Node t): 
  Node a = t.parent
  while (a != null)
   for i = 0 .. a.length - 1
     a.keys[i] = max(a.sons[i]) // max — возвращает максимальное значение в поддереве.
   a = a.parent                 // Примечание: max легко находить, если хранить максимум 
                                // правого поддерева в каждом узле — это значение и будет max(a.sons[i])

[math]\mathtt{updateKeys}[/math] необходимо запускать от нового узла. Добавление элемента:

function insert(T x):
  Node n = Node(x)
  if (root == null) 
   root = n
   return
  Node a = searchNode(x)     
  if (a.parent == null) 
    Node t = root
    root.sons[0] = t
    root.sons[1] = n
    t.parent = root
    n.parent = root
    root.length = 2
    сортируем сыновей у root
  else 
    Node p = a.parent
    p.sons[p.length] = n
    p.length++
    n.parent = p
    сортируем сыновей у p
    updateKeys(n) 
    split(n)
  updateKeys(n) 

Так как мы спускаемся один раз, и поднимаемся вверх при расщеплении родителей не более одного раза, то [math]\mathtt{insert}[/math] работает за [math]O(\log{n})[/math].

Примеры добавления:

Добавление элемента с ключом 6

Удаление элемента

  • [math]x[/math] — значение удаляемого узла,
  • [math]t[/math] — текущий узел,
  • [math]b[/math] — брат [math]t[/math],
  • [math]p[/math] — отец [math]t[/math],
  • [math]np[/math] — соседний брат [math]p[/math],
  • [math]gp[/math] — отец [math]p[/math].

Пусть изначально [math]t = \mathtt{searchNode(x)}[/math] — узел, где находится [math]x[/math].

Если у [math]t[/math] не существует родителя, то это корень (одновременно и единственный элемент в дереве). Удалим его.

Если [math]p[/math] существует, и у него строго больше [math]2[/math] сыновей, то просто удалим [math]t[/math], а у [math]p[/math] уменьшим количество детей.

Если у родителя [math]t[/math] два сына, рассмотрим возможные случаи (сперва везде удаляем [math]t[/math]):

  • [math]np[/math] не существует, тогда мы удаляем одного из сыновей корня, следовательно, другой сын становится новым корнем,
  • у [math]gp[/math] оказалось [math]2[/math] сына, у [math]np[/math] оказалось [math]2[/math] сына. Подвесим [math]b[/math] к [math]np[/math] и удалим [math]p[/math]. Так как у [math]gp[/math] — родителя [math]p[/math], оказалось тоже два сына, повторяем для [math]p[/math] такие же рассуждения,
  • у [math]gp[/math] оказалось [math]2[/math] или [math]3[/math] сына, у [math]np[/math] оказалось [math]3[/math] сына. Просто заберем ближайшего к нам сына у [math]np[/math] и прицепим его к [math]p[/math]. Восстановим порядок в сыновьях [math]p[/math]. Теперь у [math]p[/math] оказалось снова два сына и все узлы 2-3 дерева корректны,
  • у [math]gp[/math] оказалось [math]3[/math] сына, у [math]np[/math] оказалось [math]2[/math] сына. Подвесим [math]b[/math] к [math]np[/math] и удалим [math]p[/math], а у [math]gp[/math] уменьшим количество детей. Так как у [math]np[/math] оказалось три сына, а у [math]gp[/math] все ещё больше одного сына, то все узлы 2-3 дерева корректны.


Обобщим алгоритм при удалении когда у родителя [math]t[/math] два сына:

  • Если [math]np[/math] не существует, то оказывается, что мы сейчас удаляем какого-то из сыновей корня (для определенности далее левого, с правым аналогично). Тогда теперь правый сын становится корнем. На этом удаление заканчивается.
  • Если [math]np[/math] существует, то удалим [math]t[/math], а его брата ([math]b[/math]) перецепим к [math]np[/math]. Теперь у [math]np[/math] могло оказаться [math]4[/math] сына, поэтому повторим аналогичные действия из [math]\mathtt{insert}[/math]: вызовем [math]\mathtt{updateKeys}(b)[/math] и [math]\mathtt{splitParent}(np)[/math]. Теперь рекурсивно удалим [math]p[/math].

В результате мы получаем корректное по структуре 2-3 дерево, но у нас есть нарушение в ключах в узлах, исправим их с помощью [math]\mathtt{updateKeys()}[/math], запустившись от [math]b[/math].

Удаление элемента с ключом 2

Следующий и предыдущий

  • [math]x[/math] — поисковый параметр,
  • [math]t[/math] — текущий узел.

В силу того, что наши узлы отсортированы по максимуму в поддереве, то следующий объект — это соседний лист справа. Попасть туда можно следующим образом: будем подниматься вверх, пока у нас не появится первой возможности свернуть направо вниз. Как только мы свернули направо вниз, будем идти всегда влево. Таким образом, мы окажемся в соседнем листе. Если мы не смогли ни разу свернуть направо вниз, и пришли в корень, то следующего объекта не существует. Случай с предыдущим симметричен.

 T next(T x):
   Node t = searchNode(x)
   if (t.keys[0] > x)  //x не было в дереве, и мы нашли следующий сразу
     return t.keys[0]
   while (t != null)
     t = t.parent
     if (можно свернуть направо вниз)
      в t помещаем вершину, в которую свернули
      while (пока t — не лист)
       t = t.sons[0]
     return t
   return t.keys[0]
    
Путь при поиске следующего элемента после 2

Нахождение m следующих элементов

B+ деревья, поддерживают операцию [math]\mathtt{find}[/math], которая позволяет находить m следующих элементов. Наивная реализация выглядит следующим образом: будем вызывать [math]m[/math] раз поиск следующего элемента, такое решение работает за [math]O(m \log{n})[/math]. Но 2-3 деревья, позволяют находить m следующих элементов за [math]O(m + \log{n})[/math], что значительно ускоряет поиск при больших [math]m[/math]. По построению, все листья у нас отсортированы в порядке возрастания, воспользуемся этим для нахождения m элементов. Нам необходимо связать листья, для этого модифицируем [math]\mathtt{insert}[/math] и [math]\mathtt{delete}[/math]. Добавим к узлам следующие поля:

  • [math]\mathtt{right}[/math] — указывает на правый лист,
  • [math]\mathtt{left}[/math] — указывает на левый лист.

Пусть [math]t[/math] — добавленный узел. Изменим [math]\mathtt{insert}[/math] следующим образом: в самом конце, после того как мы уже обновили все ключи, найдем [math]\mathtt{next(t)}[/math] и запишем ссылку на него в [math]\mathtt{t.right}[/math]. Аналогично с левым.

Пусть [math]t[/math] — удаляемый узел. Изменим [math]\mathtt{delete}[/math] следующим образом: в самом начале, до удаления [math]t[/math], найдем следующий [math]\mathtt{next}[/math] и запишем в [math]\mathtt{next.left}[/math] правый лист относительно [math]t[/math]. С левым поступим аналогично.

В итоге, мы имеем двусвязный список в листьях, и чтобы нам вывести [math]m[/math] элементов, нам достаточно один раз найти нужный элемент и пробежаться вправо на [math]m[/math] элементов.


thumb

См. также

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