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 дереве необходимо последовательно просматривать ключи, хранящиеся во внутренних ячейках, спускаясь от корня к листьям. Вначале ключ искомого элемента сравнивается с первым ключом ячейки и, если искомый ключ не больше первого, то осуществляется переход в левое поддерево. Иначе, сравниваем искомый ключ со вторым ключом в ячейке (если второго ключа нет — поддерева всего два, то сразу переходим во второе поддерево) и если наш ключ не превосходит второй ключ, то осуществляется переход в среднее поддерево, а если превосходит, то идем в правое поддерево.

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

Т.к. вся информация в 2-3 деревьях хранится в листьях, а в вершинах хранится вспомогательная информация, то слияние двух деревьев представляет собой добавление общей вершины.

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

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

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

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

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

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

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