2-3 дерево

Пример 2-3 дерева

‎

2-3 дерево — структура данных, предложенная в 1970 году Джоном Хопкрофтом,и представляющая собой B-дерево cтепени 1, такое что из каждого узла может выходить две или три ветви; при этом требуется, чтобы все внешние узлы находились на одном уровне. Каждый внутренний узел содержит либо один, либо два ключа.

Значения

Все данные хранятся в листьях, в вершинах хранится вспомогательная информация,необходимая для организации поиска по поддеревьям.Нелистовые вершины содержат 1 или 2 ключа, указывающие на диапазон значений в их поддеревьях.

Структура

Информация в таких деревьях хранится в листьях, а остальные вершины содержат вспомогательную информацию для организации поиска.2-3 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных.

Свойства

• Все нелистовые вершины содержат один ключ и 2 поддерева или 2 ключа и 3 поддерева.
• Все листовые вершины находятся на одном уровне (на нижнем уровне) и содержат 1 или 2 ключа.
• Все данные отсортированы
• 2-3 дерево - сливаемое дерево
• Все пути от корня до любого листа имеют одинаковую длину
• Высота 2-3 дерева лежит между [math] \log_{2} n [/math] и [math] \log_{2} n [/math], где [math] n [/math] - количество элементов в дереве.

Поэтому операции над ним выполняются за время [math]O(\log{n})[/math].

Операции

• Поиск

Для поиска в 2-3 дереве необходимо последовательно просматривать ключи, хранящиеся во внутренних ячейках, спускаясь от корня к листьям. Вначале ключ искомого элемента сравнивается с первым ключом ячейки и, если искомый ключ не больше первого, то осуществляется переход в левое поддерево. Иначе, сравниваем искомый ключ со вторым ключом в ячейке (если второго ключа нет — поддерева всего два, то сразу переходим во второе поддерево) и если наш ключ не превосходит второй ключ, то осуществляется переход в среднее поддерево, а если превосходит, то идем в правое поддерево.

• Вставка элемента

Есть два варианта вставки в 2-3 дерево.

Чтобы поместить новый ключ в узел, в котором содержится ровно один ключ, необходимо просто добавить его как второй ключ к узлу.

Если же в узле уже содержатся два ключа, делим его на два "одноключевых" узла и вставляем средний ключ в родительский узел.Это может привести к тому, что придется делить родительский узел. Тогда таким же образом проходим до корня дерева.

• Удаление элемента

При удалении ключа из узла возникают три варианта.

Если до удаления ключа в узле содержалось два ключа, то после удаления ничего не меняется.

Если же у ключа после удаления остался один элемент, то проверяем количество потомков второго ребенка того узла, ребенком которого является узел с удаляемым ключом. Если у него два ребенка, то присваиваем ему оставшийся один элемент. Вершину, оставшуюся без детей, удаляем рекурсивно.

Иначе у него три ребенка. Тогда присваиваем узлу с одним ключом один из этих ключей, таким образом получая два узла с двумя ключами.

• Слияние двух деревьев (merge())

Возможно два варианта слияния двух деревьев.

Если два дерева одной высоты, то слияние представляет собой добавление общей вершины.

Если два дерева разной высоты, то при слиянии меньшее добавляем как поддерево к одной из вершин большего.Если возникает ситуация,когда у необходимого узла уже есть три ребенка, то делим его на два узла с двумя поддеревьями и проверяем родителя.Таким образом проходим по дереву вверх до полной сбалансировки.

Дополнительные ссылки

Визуализатор 2-3 дерева - 1

Визуализатор 2-3 дерева - 2

Использованные источники

2-3 дерево

Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0