Изменения

''' 2-3 дерево ''' — структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. Является частным случаем [[B-дерево#B.2B-.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.BE|B+-дерева]], когда нелистовые вершины могут иметь только 2 или 3 сыновей.

*нелистовая вершина, имеющая двух сыновей, хранит максимум левого поддерева. Нелистовая вершина, имеющая трех сыновей, хранит два значения.Первое значение хранит максимум левого поддерева, второе максимум центрального поддерева,

*<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>.Будем просматривать ключи в узлах, пока узел не является листом.Рассмотрим два случая:

Пример поиска в 2-3 дереве, так как элемент 6 существует, то был возвращен корректный узел, так как элемента 10 нет, возвращается некорректный узел. На основе этого можно сделать метод <tex>\mathtt{exist}</tex>, проверяющий наличии элемента в дереве.

*<tex>x</tex> {{-- -}} добавляемое значение.,*<tex>t</tex> {{-- -}} текущая вершина в дереве. Изначально <tex>t = \mathtt{root}</tex>.

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

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

Так как мы спускаемся один раз, и поднимаемся вверх при расщеплении родителей не более одного раза, то <tex>\mathtt{insert}</tex> работает за <tex>O(\log{n})</tex>. Примеры добавления: [[Файл:23treeinsert.png|border|600px]]

[[Файл:23treeinsert23treeinsert2.png|800px|border]]

[[Файл:23treeinsert223treeinsert3.png|1150px800px|border]]

Пусть изначально <tex>t = \mathtt{search(x)}</tex>{{---}} узел, где находится x.

=== Слияние двух деревьев Следующий и предыдущий ===*<tex>x</tex> {{---}} поисковый параметр,*<tex>t</tex> {{---}} текущий узел.В силу того, что наши узлы отсортированы по максимуму в поддереве, то следующий объект это соседний лист справа. Попасть туда можно следующим образом:будем подниматься вверх, пока у нас не появится первой возможности свернуть направо вниз. Как только мы свернули направо вниз, будем идти всегда влево. Таким образом, мы окажемся в соседнем листе. Если мы не смогли ни разу свернуть направо вниз, и пришли в корень, то следующего объекта не существует. Случай с предыдущим симметричен. Node next('''int x''') Node t = search(x) '''if''' (t.keys[0] > x) //x не было в дереве, и мы нашли следующий сразу '''return''' t '''while''' (t != '''null''') t = t.parent if (можно свернуть направо вниз) в t помещаем вершину, в которую свернули '''while''' (пока t {{---}} не лист) t = t.sons[0] '''return''' t '''return''' t; [[Файл:Treenext.png|border|325px]] [[Файл:Treeprev.png|border|300px]] === Find ===B+ деревья, поддерживают операцию <tex>\mathtt{find}</tex>, которая позволяет находить m следующих элементов. Так как все листья отсортированы в порядке возрастания, то просто свяжем каждый лист с соседями.*<tex>\mathtt{right}</tex> - правый лист,*<tex>\mathtt{left}</tex> - левый лист.Доработаем добавление. Когда мы уже добавили элемент и обновили ключи, найдем для него следующий, и запишем на него ссылку в <tex>\mathtt{right}</tex>, найдем предыдущий и запишем на него ссылку в <tex>\mathtt{left}</tex>,так же и его соседям укажем ссылка на него. Доработаем удаление. При удалении элемента, мы просто связываем его соседей за <tex>O(1)</tex>. [[Файл:23treefind.png|border]]

== Cсылки Источники информации ==* [http://is.ifmo.ru/vis/tree23/tree23_ru.html is.ifmo.ru {{- --}} Визуализатор 2-3 дерева — 1]* [http://rain.ifmo.ru/cat/view.php/vis/trees/2-3-2002 rain.ifmo.ru {{--- }} Визуализатор 2-3 дерева — 2]* [http://ru.wikipedia.org/wiki/2-3-дерево Википедия — {{---}} 2-3 дерево]