2-3 дерево

2021-04-14T12:41:52Z

178.207.178.183: /* Свойства */

[[Файл: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 дерево {{---}} сбалансированное дерево поиска, обладающее следующими свойствами:
*нелистовые вершины имеют либо <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, оранжевые стрелки обозначают путь по дереву при поиске]]

=== Вставка элемента ===
*<tex>x</tex> {{---}} добавляемое значение,
*<tex>t</tex> {{---}} текущая вершина в дереве. Изначально <tex>t = \mathtt{root}</tex>.
Если корня не существует {{---}} дерево пустое, то новый элемент и будет корнем (одновременно и листом). Иначе поступим следующим образом:

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

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

'''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
Если сыновей стало <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]) // max {{---}} возвращает максимальное значение в поддереве.
a = a.parent // Примечание: max легко находить, если хранить максимум 
// правого поддерева в каждом узле {{---}} это значение и будет max(a.sons[i])

<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> уменьшим количество детей.

Если у родителя <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>np</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>.

В результате мы получаем корректное по структуре 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) //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]

[[Файл:23treenext.png|thumb|center|400px|Путь при поиске следующего элемента после 2]]

=== Нахождение 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>. С левым поступим аналогично.

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

[[Файл:23treefindm.png|thumb|Изменение ссылок при добавлении нового элемента|thumb|center|800px]]

== См. также ==
* [[B-дерево]]
* [[Splay-дерево]]
* [[АВЛ-дерево]]
* [[Декартово дерево]]
* [[Красно-черное дерево]]

== Источники информации ==
* [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

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Структуры данных]]
[[Категория:Деревья поиска]]

Викиконспекты - Вклад участника [ru]

2-3 дерево