[[Файл:23дерево_new.jpg |right|300px|thumb|Пример 2-3 дерева]]
''' 2-3 дерево ''' — структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. 2-3 дерево можно обобщить до [[B-дерево#B.2B-.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.BE|B+-дерева]].
== Свойства ==
2-3 дерево {{---}} сбалансированное дерево поиска, обладающее следующими свойствами:
*нелистовые вершины имеют либо 2, либо 3 сына,
*нелистовая вершина, имеющая двух сыновей, хранит максимум левого поддерева. Нелистовая вершина, имеющая трех сыновей, хранит два значения.Первое значение хранит максимум левого поддерева, второе максимум центрального поддерева,
*сыновья упорядочены по значению максимума поддерева сына,
*все листья лежат на одной глубине,
*Высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> - количество элементов в дереве.
== Структура ==
:*Все данные хранятся в листьях, в вершинах хранится вспомогательная информация,необходимая для организации поиска по поддеревьям.
:*Сыновья упорядочены по значению максимума поддерева сына.
:*Нелистовые вершины содержат 1 или 2 ключа, указывающие на диапазон значений в их поддеревьях.
:*Если нелистовая вершина имеет двух сыновей, то вершина хранит минимум правого поддерева; если трех, то первый ключ равен минимуму среднего поддерева, а второй ключ равен минимуму правого поддерева.
:*2-3 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных.
:*Высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> - количество элементов в дереве, поэтому операции поиска, добавления, удаления, слияния выполняются за время <tex>O(\log{n})</tex>.
{{Теорема
|statement= Высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> - количество элементов в дереве.
|proof=
Из построения следует, что все листья лежат на одной глубине, так как элементов <tex>n</tex>, то получаем что высота равна <tex>O(\log{n})</tex>
}}
== Операции ==
Введем следующие обозначения:
*<tex>\mathtt{root}</tex> - корень 2-3 дерева
Каждый узел дерева обладает полями:
*<tex>\mathtt{sons}</tex> - сыновья узла,
*<tex>\mathtt{keys}</tex> - ключи узла,
*<tex>\mathtt{length}</tex> - количество сыновей.
=== Поиск ===
Для поиска в 2*<tex>x</tex> -3 дереве необходимо последовательно просматривать ключи, хранящиеся во внутренних ячейках, спускаясь от корня к листьямискомое значение. Вначале ключ искомогоэлемента сравнивается с первым ключом ячейки и, если искомый ключ меньше, то осуществляется переход *<tex>t</tex> - текущая вершина в левое поддереводереве. Иначе, сравниваем искомый ключ со вторымИзначально <tex>t = \mathtt{root}</tex>ключом Будем просматривать ключи в ячейке (если второго ключа нет — поддерева всего дваузлах, то сразу переходим вовторое поддерево) и если наш ключ пока узел не превосходит второй ключ, то осуществляется переходв среднее поддерево, а если превосходит, то идем в правое поддеревоявляется листом. Рассмотрим два случая:
1)у текущей вершины два сына. Если её значение меньше <tex>x</tex>, то <tex>t =\mathtt{t.sons[1]}</tex>, иначе <tex>t == Вставка элемента === Есть два варианта вставки в 2-3 дерево\mathtt{t.sons[0]}</tex>.
12) Чтобы поместить новый ключ в узелу текущей вершины три сына. Если второе значение меньше <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>.
[[Файл:23treeadd3.png|440px|border]] [[Файл'''Node''' search('''int''' x):23treeadd4.png|400px|border]] 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[Файл:23treeadd12] '''else''' '''if''' (t.png|490px|borderkeys[0]< x) t = t.sons[1] [ '''else''' t = t.sons[Файл:23treeadd2.png|400px|border]0] '''return''' t=== Вставка элемента ===
=== Удаление элемента ===
При удалении ключа из узла возникают три варианта.
1) Если после удаления ключа в узле содержится два ключа, то после удаления ничего не меняется.
2) Если же у ключа после удаления остался один элемент, то проверяем количество потомков второго ребенка того узла, ребенком которого является узел с удаляемым ключом. Если у него два ребенка, то присваиваем ему оставшийся один элемент. Вершину, оставшуюся без детей, удаляем рекурсивно.
[[Файл:23treedel1.png|330px|border]] [[Файл:23treedel2.png|300px|border]] [[Файл:23treedel5.png|300px|border]]
3) Иначе у него три ребенка. Тогда присваиваем узлу с одним ключом один из этих ключей, таким образом получая два узла с двумя ключами.
[[Файл:23treedel3.png|300px|border]] [[Файл:23treedel4.png|320px|border]] [[Файл:23treedel6.png|300px|border]]
=== Слияние двух деревьев ===
Возможно два варианта слияния двух деревьев.
1) Если два дерева одной высоты, то слияние представляет собой добавление общей вершины.
[[Файл:23treemerge1.png|400px|border]] [[Файл:23treemerge2.png|400px|border]]
2) Если два дерева разной высоты, то при слиянии меньшее добавляем как поддерево к одной из вершин большего. Если возникает ситуация,когда у необходимого узла уже есть три ребенка, то делим его на два узла с двумя поддеревьями, переходим в родителя.Таким образом будем проходим по дереву вверх пока дерево не станет корректным.
[[Файл:23treemerge3.png|400px|border]] [[Файл:23treemerge4.png|400px|border]]
== Cсылки ==
