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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 100 промежуточных версий 14 участников)
Строка 1: Строка 1:
[[Файл:2_3tree.jpg|right|300px|thumb|Пример 2-3 дерева]]
+
[[Файл: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 дерево ''' — структура данных, предложенная в 1970 году Джоном Хопкрофтом,и представляющая собой [[B-дерево|B-дерево]] cтепени 1, такое что из каждого узла может выходить две или три ветви; при этом требуется, чтобы все внешние узлы находились на одном уровне. Каждый внутренний узел содержит либо один, либо два ключа.
+
== Свойства ==
 +
2-3 дерево {{---}} сбалансированное дерево поиска, обладающее следующими свойствами:
 +
*нелистовые вершины имеют либо <tex>2</tex>, либо <tex>3</tex> сына,
 +
*нелистовая вершина, имеющая двух сыновей, хранит максимум левого поддерева. Нелистовая вершина, имеющая трех сыновей, хранит два значения. Первое значение хранит максимум левого поддерева, второе максимум центрального поддерева,
 +
*сыновья упорядочены по значению максимума поддерева сына,
 +
*все листья лежат на одной глубине,
 +
*высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> {{---}} количество элементов в дереве.
 +
 
 +
== Операции ==
 +
Введем следующие обозначения:
 +
*<tex>\mathtt{root}</tex> {{---}} корень 2-3 дерева.
 +
Каждый узел дерева обладает полями:
 +
*<tex>\mathtt{parent}</tex> {{---}} родитель узла,
 +
*<tex>\mathtt{sons}</tex> {{---}} сыновья узла,
 +
*<tex>\mathtt{keys}</tex> {{---}} ключи узла,
 +
*<tex>\mathtt{length}</tex> {{---}} количество сыновей.
 +
=== Поиск ===
 +
*<tex>x</tex> {{---}} искомое значение,
 +
*<tex>t</tex> {{---}} текущая вершина в дереве.
 +
 
 +
Изначально <tex>t = \mathtt{root}</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>.
 +
 
 +
'''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]
 +
 
 +
[[Файл:23treesearch.png|thumb|center|600px|Поиск элемента 19, оранжевые стрелки обозначают путь по дереву при поиске]]
  
==Значения ==
+
=== Вставка элемента ===
Все данные хранятся в листьях, в вершинах хранится вспомогательная информация,необходимая для организации поиска по поддеревьям.Нелистовые вершины содержат 1 или 2 ключа, указывающие на диапазон значений в их поддеревьях.  
+
*<tex>x</tex> {{---}} добавляемое значение,
 +
*<tex>t</tex> {{---}} текущая вершина в дереве. Изначально <tex>t = \mathtt{root}</tex>.
 +
Если корня не существует {{---}} дерево пустое, то новый элемент и будет корнем (одновременно и листом). Иначе поступим следующим образом:
  
== Структура ==
+
Найдем сперва, где бы находился элемент, применив <tex>\mathtt{search(x)}</tex>. Далее проверим есть ли у этого узла родитель, если его нет, то в дереве всего один элемент {{---}} лист. Возьмем этот лист и новый узел, и создадим для них родителя, лист и новый узел расположим в порядке возрастания.
Информация в таких деревьях хранится в листьях, а остальные вершины содержат вспомогательную информацию для организации поиска.2-3 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных.
 
  
== Свойства ==
+
Если родитель существует, то подвесим к нему ещё одного сына. Если сыновей стало <tex>4</tex>, то разделим родителя на два узла, и повторим разделение теперь для его родителя, ведь у него тоже могло быть уже <tex>3</tex> сына, а мы разделили и у него стало на <tex>1</tex> сына больше. (перед разделением обновим ключи).
* Все нелистовые вершины содержат один ключ и 2 поддерева или 2 ключа и 3 поддерева.
+
 
* Все листовые вершины находятся на одном уровне (на нижнем уровне) и содержат 1 или 2 ключа.
+
'''function''' splitParent('''Node''' t):
* Все данные отсортированы
+
  '''if''' (t.length > 3)
* 2-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
* Высота 2-3 дерева лежит между <tex> \log_{2} n </tex> и <tex> \log_{2} n </tex>, где <tex> n </tex> - количество элементов в дереве.  
+
    t.sons[3].parent = a
Поэтому операции над ним выполняются за время  <tex>O(\log{n})</tex>.
+
    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'''                  <font color=green>// мы расщепили корень, надо подвесить его к общему родителю, который будет новым корнем</font>
 +
    Node t = root
 +
    root.sons[0] = t
 +
    root.sons[1] = a
 +
    t.parent = root
 +
    a.parent = root
 +
    root.length = 2
 +
    сортируем сыновей у root
 +
Если сыновей стало <tex>3</tex>, то ничего не делаем. Далее необходимо восстановить ключи на пути от новой вершины до корня:
 +
'''function''' updateKeys('''Node''' t):
 +
  Node a = t.parent
 +
  '''while''' (a != ''null'')
 +
    '''for''' i = 0 .. a.length - 1
 +
      a.keys[i] = max(a.sons[i]) <font color=green>// max {{---}} возвращает максимальное значение в поддереве.</font>
 +
    a = a.parent                <font color=green>// Примечание: max легко находить, если хранить максимум </font>
 +
                                <font color=green>// правого поддерева в каждом узле {{---}} это значение и будет max(a.sons[i])</font>
 +
 
 +
<tex>\mathtt{updateKeys}</tex> необходимо запускать от нового узла.
 +
Добавление элемента:
 +
'''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)
 +
Так как мы спускаемся один раз, и поднимаемся вверх при расщеплении родителей не более одного раза, то <tex>\mathtt{insert}</tex> работает за <tex>O(\log{n})</tex>.
 +
 
 +
Примеры добавления:
 +
 
 +
[[Файл:23treeinsert.png|thumb|center|Добавление элемента с ключом 6|600px]]
 +
 
 +
=== Удаление элемента ===
 +
*<tex>x</tex> {{---}} значение удаляемого узла,
 +
*<tex>t</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> уменьшим количество детей.
* ''' Поиск '''
 
Для поиска в 2-3  дереве необходимо последовательно просматривать ключи,  
 
хранящиеся во внутренних ячейках, спускаясь от корня к листьям. Вначале ключ искомого
 
элемента сравнивается с первым ключом ячейки и, если искомый ключ не больше первого,
 
то осуществляется переход в левое поддерево. Иначе, сравниваем искомый ключ со вторым
 
ключом в ячейке  (если второго ключа нет —  поддерева всего два,  то сразу переходим во
 
второе поддерево) и если наш ключ не превосходит второй ключ, то осуществляется переход
 
в среднее поддерево, а если превосходит, то идем в правое поддерево.  
 
  
* ''' Вставка элемента '''
+
Если у родителя <tex>t</tex> два сына, рассмотрим возможные случаи (сперва везде удаляем <tex>t</tex>):
Есть два варианта вставки в 2-3 дерево.
+
*<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 дерева корректны.
  
Чтобы поместить новый ключ в узел, в котором содержится ровно один ключ, необходимо просто добавить его как второй ключ к узлу.
 
  
[[Файл:23treeadd3.png|220px|border]]  [[Файл:23treeadd4.png|200px|border]]
 
  
Если же в узле уже содержатся два ключа, делим его на два "одноключевых" узла и вставляем средний ключ в родительский узел.Это может привести к тому, что придется делить родительский узел. Тогда таким же образом проходим до корня дерева.
+
Обобщим алгоритм при удалении когда у родителя <tex>t</tex> два сына:
 +
*Если <tex>np</tex> не существует, то оказывается, что мы сейчас удаляем какого-то из сыновей корня (для определенности далее левого, с правым аналогично). Тогда теперь правый сын становится корнем. На этом удаление заканчивается.
  
[[Файл:23treeadd1.png|245px|border]]  [[Файл:23treeadd2.png|200px|border]]
+
*Если <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>.
  
* ''' Удаление элемента '''
+
В результате мы получаем корректное по структуре 2-3 дерево, но у нас есть нарушение в ключах в узлах, исправим их с помощью <tex>\mathtt{updateKeys()}</tex>, запустившись от <tex>b</tex>.
При удалении ключа из узла возникают три варианта.
+
[[Файл:23treedelete.png|thumb|center|Удаление элемента с ключом 2|1150px]]
  
Если до удаления ключа в узле содержалось два ключа, то после удаления ничего не меняется.
+
=== Следующий и предыдущий ===
 +
*<tex>x</tex> {{---}} поисковый параметр,
 +
*<tex>t</tex> {{---}} текущий узел.
 +
В силу того, что наши узлы отсортированы по максимуму в поддереве, то следующий объект {{---}} это соседний лист справа. Попасть туда можно следующим образом:
 +
будем подниматься вверх, пока у нас не появится первой возможности свернуть направо вниз. Как только мы свернули направо вниз, будем идти всегда влево. Таким образом, мы окажемся в соседнем листе. Если мы не смогли ни разу свернуть направо вниз, и пришли в корень, то следующего объекта не существует. Случай с предыдущим симметричен.
 +
  '''T''' next('''T''' x):
 +
    Node t = searchNode(x)
 +
    '''if''' (t.keys[0] > x) <font color=green> //x не было в дереве, и мы нашли следующий сразу</font>
 +
      '''return''' t.keys[0]
 +
    '''while''' (t != ''null'')
 +
      t = t.parent
 +
      '''if''' (можно свернуть направо вниз)
 +
      в t помещаем вершину, в которую свернули
 +
      '''while''' (пока t {{---}} не лист)
 +
        t = t.sons[0]
 +
      '''return''' t
 +
    '''return''' t.keys[0]
 +
   
  
Если же у ключа после удаления остался один элемент, то проверяем количество потомков второго ребенка того узла, ребенком которого является узел с удаляемым ключом. Если у него два ребенка, то присваиваем ему оставшийся один элемент.
+
[[Файл:23treenext.png|thumb|center|400px|Путь при поиске следующего элемента после 2]]
  
[[Файл:23treedel1.png|220px|border]]  [[Файл:23treedel2.png|200px|border]]
+
=== Нахождение 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>.
 +
По построению, все листья у нас отсортированы в порядке возрастания, воспользуемся этим для нахождения m элементов. Нам необходимо связать листья, для этого модифицируем
 +
<tex>\mathtt{insert}</tex> и <tex>\mathtt{delete}</tex>. Добавим к узлам следующие поля:
 +
*<tex>\mathtt{right}</tex> {{---}} указывает на правый лист,
 +
*<tex>\mathtt{left}</tex> {{---}} указывает на левый лист.
 +
Пусть <tex>t</tex> {{---}} добавленный узел.
 +
Изменим <tex>\mathtt{insert}</tex> следующим образом: в самом конце, после того как мы уже обновили все ключи, найдем <tex>\mathtt{next(t)}</tex> и запишем ссылку на него в <tex>\mathtt{t.right}</tex>. Аналогично с левым.
  
Иначе у него три ребенка. Тогда присваиваем узлу с одним ключом один из этих ключей, таким образом получая два узла с двумя ключами.
+
Пусть <tex>t</tex> {{---}} удаляемый узел. Изменим <tex>\mathtt{delete}</tex> следующим образом: в самом начале, до удаления <tex>t</tex>, найдем следующий <tex>\mathtt{next}</tex> и запишем в <tex>\mathtt{next.left}</tex> правый лист относительно <tex>t</tex>. С левым поступим аналогично.
  
[[Файл:23treedel3.png|200px|border]]  [[Файл:23treedel4.png|215px|border]]
+
В итоге, мы имеем двусвязный список в листьях, и чтобы нам вывести <tex>m</tex> элементов, нам достаточно один раз найти нужный элемент и пробежаться вправо на <tex>m</tex> элементов.
  
* ''' Слияние двух деревьев (merge()) '''
 
Возможно два варианта слияния двух деревьев.
 
  
Если два дерева одной высоты, то слияние представляет собой добавление общей вершины.
 
  
Если два дерева разной высоты, то при слиянии меньшее добавляем как поддерево к одной из вершин большего.Если возникает ситуация,когда у необходимого узла уже есть три ребенка, то делим его на два узла с двумя поддеревьями и проверяем родителя.Таким образом проходим по дереву вверх до полной сбалансировки.
+
[[Файл:23treefindm.png|thumb|Изменение ссылок при добавлении нового элемента|thumb|center|800px]]
  
== Дополнительные ссылки ==
+
== См. также ==
 +
* [[B-дерево]]
 +
* [[Splay-дерево]]
 +
* [[АВЛ-дерево]]
 +
* [[Декартово дерево]]
 +
* [[Красно-черное дерево]]
  
[http://is.ifmo.ru/vis/tree23/tree23_ru.html Визуализатор 2-3 дерева - 1]
+
== Источники информации ==
 +
* [http://is.ifmo.ru/vis/tree23/tree23_ru.html is.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 дерево]
 +
* Д. Кнут «Искусство программирования. Сортировка и поиск» {{---}} стр. 508-509
  
[http://rain.ifmo.ru/cat/view.php/vis/trees/2-3-2002 визуализатор 2-3 дерева - 2]
 
  
== Использованные источники ==
 
[http://ru.wikipedia.org/wiki/2-3-дерево 2-3 дерево]
 
  
Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0
+
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория:Структуры данных]]
 +
[[Категория:Деревья поиска]]

Текущая версия на 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

См. также

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