Изменения
Нет описания правки
:*Сыновья упорядочены по значению максимума поддерева сына.
:*Нелистовые вершины содержат 1 или 2 ключа, указывающие на диапазон значений в их поддеревьях.
:*Если нелистовая вершина имеет двух сыновей, то вершина хранит минимум правого поддерева; если трех, то первый ключ равен минимуму среднего поддерева, а второй ключ равен минимуму правого поддерева.
:*2-3 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных.
:*Высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> - количество элементов в дереве, поэтому операции поиска, добавления, удаления, слияния выполняются за время <tex>O(\log{n})</tex>.
Для поиска в 2-3 дереве необходимо последовательно просматривать ключи,
хранящиеся во внутренних ячейках, спускаясь от корня к листьям. Вначале ключ искомого
элемента сравнивается с первым ключом ячейки и, если искомый ключ не больше первогоменьше,
то осуществляется переход в левое поддерево. Иначе, сравниваем искомый ключ со вторым
ключом в ячейке (если второго ключа нет — поддерева всего два, то сразу переходим во
[[Файл:23treemerge1.png|400px|border]] [[Файл:23treemerge2.png|400px|border]]
2) Если два дерева разной высоты, то при слиянии меньшее добавляем как поддерево к одной из вершин большего.Если возникает ситуация,когда у необходимого узла уже есть три ребенка, то делим его на два узла с двумя поддеревьями и проверяем , переходим в родителя.Таким образом будем проходим по дереву вверх до полной сбалансировкипока дерево не станет корректным.
[[Файл:23treemerge3.png|400px|border]] [[Файл:23treemerge4.png|400px|border]]
