48
правок
Изменения
Нет описания правки
== Структура ==
Все данные хранятся в листьях, в вершинах хранится вспомогательная информация,необходимая для организации поиска по поддеревьям. Сыновья упорядочены по значению максимума поддерева сына. Нелистовые вершины содержат 1 или 2 ключа, указывающие на диапазон значений в их поддеревьях. Если нелистовая вершина имеет двух сыновей, то вершина хранит максимум минимум поддерева; если трех, то первый ключ равен максимуму поддеревьев левого и минимуму среднего сыновейподдерева, а второй ключ равен максимуму всего минимуму правого поддерева. 2-3 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных. Высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> - количество элементов в дереве, поэтому операции поиска, добавления, удаления, слияния выполняются за время <tex>O(\log{n})</tex>.
== Операции ==
Чтобы поместить новый ключ в узел, в котором содержится ровно один ключ, необходимо просто добавить его как второй ключ к узлу.
[[Файл:23treeadd3.png|220px440px|border]] [[Файл:23treeadd4.png|200px400px|border]]
Если же в узле уже содержатся два ключа, делим его на два "одноключевых" узла и вставляем средний ключ в родительский узел.Это может привести к тому, что придется делить родительский узел. Тогда таким же образом проходим до корня дерева.
[[Файл:23treeadd1.png|245px490px|border]] [[Файл:23treeadd2.png|200px400px|border]]
=== Удаление элемента ===
Если же у ключа после удаления остался один элемент, то проверяем количество потомков второго ребенка того узла, ребенком которого является узел с удаляемым ключом. Если у него два ребенка, то присваиваем ему оставшийся один элемент. Вершину, оставшуюся без детей, удаляем рекурсивно.
[[Файл:23treedel1.png|220px440px|border]] [[Файл:23treedel2.png|200px400px|border]]
Иначе у него три ребенка. Тогда присваиваем узлу с одним ключом один из этих ключей, таким образом получая два узла с двумя ключами.
[[Файл:23treedel3.png|200px400px|border]] [[Файл:23treedel4.png|215px430px|border]]
=== Слияние двух деревьев ===
