Изменения

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

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

Дональд Кнут . "Искусство программирования", том 3. Глава "Сортировка и поиск".