143
правки
Изменения
Нет описания правки
''' 2-3 дерево ''' — структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. Является частным случаем [[B-дерево#B.2B-.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.BE|B+ дерева]], когда нелистовые вершины могут иметь только 2 или 3 сыновей.
== Свойства ==
2-3 дерево {{---}} сбалансированное дерево поиска, обладающее следующими свойствами:
=== Поиск ===
*<tex>x</tex> {{---}} искомое значение,
*<tex>t</tex> {{---}} текущая вершина в дереве. Изначально <tex>t = \mathtt{root}</tex>.Будем просматривать ключи в узлах, пока узел не является листом. Рассмотрим два случая:1)*у текущей вершины два сына. Если её значение меньше <tex>x</tex>, то <tex>t = \mathtt{t.sons[1]}</tex>, иначе <tex>t = \mathtt{t.sons[0]}</tex>.
'''Node''' search('''int''' x):
'''else''' t = t.sons[0]
'''return''' t
Пример поиска в 2-3 дереве, так как элемент 6 существует, то был возвращен корректный узел, так как элемента 10 нет, возвращается некорректный узел. На основе этого можно сделать метод <tex>\mathtt{exist}</tex>, проверяющий наличии элемента в дереве.
[[Файл:23treesearch.png|border]]
Найдем сперва, где бы находился элемент, применив search(x). Далее проверим есть ли у этого узла родитель, если его нет, то в дереве всего один элемент {{---}} лист. Возьмем этот лист и новый узел, и создадим для них родителя, лист и новый узел расположим в порядке возрастания.
Если родитель существует, то подвесим к нему ещё одного сына. Если сыновей стало 4, то разделим родителя на два узла, и повторим разделение теперь для его родителя(перед разделением обновим ключи).
splitParent('''Node''' t):
*<tex>t</tex> {{---}} текущий узел.
В силу того, что наши узлы отсортированы по максимуму в поддереве, то следующий объект это соседний лист справа. Попасть туда можно следующим образом:
Node next('''int x''')
Node t = search(x)
*<tex>\mathtt{left}</tex> - левый лист.
Доработаем добавление. Когда мы уже добавили элемент и обновили ключи, найдем для него следующий, и запишем на него ссылку в <tex>\mathtt{right}</tex>, найдем предыдущий и запишем на него ссылку в <tex>\mathtt{left}</tex>,так же и его соседям укажем ссылка на него.
Доработаем удаление. При удалении элемента, мы просто связываем его соседей за <tex>O(1)</tex>.
== Источники информации ==
* [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 дерево]
* Д. Кнут «Искусство программирования. Сортировка и поиск», часть 6.2.4
