Изменения

''' 2-3 дерево ''' — структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. Является [[B-дерево|B-дерево]] cтепени 1, такое что из каждого узла может выходить две или три ветви.

Все данные хранятся в листьях, в вершинах хранится вспомогательная информация,необходимая для организации поиска по поддеревьям. Сыновья упорядочены по значению максимума поддерева сына. Нелистовые вершины содержат 1 или 2 ключа, указывающие на диапазон значений в их поддеревьях. Если нелистовая вершина имеет двух сыновей, то вершина хранит максимум поддерева; если трех, то первый ключ равен максимуму поддеревьев левого и среднего сыновей, а второй ключ равен максимуму всего поддерева. 2-3 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных. == Свойства ==* Все нелистовые вершины содержат один ключ и 2 поддерева или 2 ключа и 3 поддерева.* Все листовые вершины находятся на одном уровне (на нижнем уровне) и содержат 1 или 2 ключа.* Все данные отсортированы* 2-3 дерево - сливаемое дерево* Все пути от корня до любого листа имеют одинаковую длину* Высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> - количество элементов в дереве. Поэтому , поэтому операции над ним поиска, добавления, удаления, слияния выполняются за время <tex>O(\log{n})</tex>.