143
правки
Изменения
Нет описания правки
''' 2-3 дерево ''' — структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. Является частным случаем [[B-дерево#B.2B-.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.BE|B+-дерева]], когда нелистовые вершины могут иметь только 2 или 3 сыновей.
== Свойства ==
2-3 дерево {{---}} сбалансированное дерево поиска, обладающее следующими свойствами:
*нелистовые вершины имеют либо 2, либо 3 сына,
*нелистовая вершина, имеющая двух сыновей, хранит максимум левого поддерева. Нелистовая вершина, имеющая трех сыновей, хранит два значения.Первое значение хранит максимум левого поддерева, второе максимум центрального поддерева,
*сыновья упорядочены по значению максимума поддерева сына,
*все листья лежат на одной глубине,
*Высота 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>.Будем просматривать ключи в узлах, пока узел не является листом.Рассмотрим два случая:
1)у текущей вершины два сына. Если её значение меньше <tex>x</tex>, то <tex>t = \mathtt{t.sons[1]}</tex>, иначе <tex>t = \mathtt{t.sons[0]}</tex>.
=== Вставка элемента ===
*<tex>x</tex> {{-- -}} добавляемое значение.,*<tex>t</tex> {{-- -}} текущая вершина в дереве. Изначально <tex>t = \mathtt{root}</tex>.
Если корня не существует {{---}} дерево пустое, то новый элемент и будет корнем (одновременно и листом). Иначе поступим следующим образом:
Найдем сперва, где бы находился элемент, применив search(x). Далее проверим есть ли у этого узла родитель, если его нет, то в дереве всего один элемент {{- --}} лист. Возьмем этот лист и новый узел, и создадим для них родителя, лист и новый узел расположим в порядке возрастания.
Если родитель существует, то подвесим к нему ещё одного сына. Если сыновей стало 4, то разделим родителя на два узла, и повторим разделение теперь для его родителя(перед разделением обновим ключи).
split(n)
updateKeys(n)
Так как мы спускаемся один раз, и поднимаемся вверх при расщеплении родителей не более одного раза, то <tex>\mathtt{insert}</tex> работает за <tex>O(\log{n})</tex>. Примеры добавления:
[[Файл:23treeinsert.png|border]]
[[Файл:23treeinsert2.png|1150px|border]]
[[Файл:23treeinsert3.png|1150px|border]]
=== Удаление элемента ===
