Удаление узла из в дерева

При удалении узла (ключа) могут возникнуть две проблемы:

1. Удалённый элемент является разделителем потомков внутри какого-либо нелистового узла;

2. После удаления в узле может остаться менее допустимого m/2 числа потомков.

Для того чтобы устранить эти проблемы, требуется перебалансировка дерева. Она может быть выполнена после удаления узла (ключа) или до него. Рассмотрим первый вариант.

Алгоритм удаления узла из В дерева

1. Если корень одновременно является листом (в дереве всего один узел), удаляем ключ из этого узла.

2. В противном случае находим узел, содержащий ключ, запоминая путь к нему. Пусть этот узел – X.

3. Если X – лист, удаляем оттуда ключ.

1. Если в узле X осталось не меньше t − 1 ключей, останавливаемся. Иначе проверяем количество ключей в следующем, а потом в предыдущем узле.

2. Если следующий узел есть, и в нём не менее t ключей, добавляем в X ключ-разделитель между ним и следующим узлом, а на его место ставим первый ключ следующего узла, после чего останавливаемся.

3. В противном случае, если есть предыдущий узел, и в нём не менее t ключей, добавляем в X ключ-разделитель между ним и предыдущим узлом, а на его место ставим последний ключ предыдущего узла, после чего останавливаемся.

4. Наконец, если и с предыдущим ключом не получилось, объединяем узел X со следующим или предыдущим узлом, и в объединённый узел перемещаем ключ, разделяющий два узла. При этом в родительском узле может остаться только t − 2 ключа. Тогда, если это не корень, выполняем аналогичную процедуру с ним.

5. Если в результате дошли до корня, и в нём осталось от 1 до t − 1 ключей, остановка, потому что корень может иметь и меньше t − 1 ключей.

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

1. Если X – не лист, а K – его i-й ключ, удаляем самый правый ключ из поддерева потомков i-го сына X, или, наоборот, самый левый ключ из поддерева потомков (i + 1)-го сына X.

Обход дерева

Обход дерева может выполняться одним из следующих способов:

1. «сверху вниз» или префиксный обход (функция_прямого_вызова) — обойти всё дерево по порядку (вершина, левое поддерево, правое поддерево);

2. «снизу вверх» или постфиксный обход (функция_обратного_вызова) — обойти всё дерево по порядку (левое поддерево, правое поддерево, вершина);

3. «симметричный обход» или инфиксный обход (функция_симметричного_вызова) — обойти всё дерево по порядку (левое поддерево, вершина, правое поддерево).

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

ИНФИКСНЫЙ_ОБХОД позволяет обойти все узлы дерева в порядке возрастания ключей и применить к каждому узлу заданную пользователем функцию обратного вызова. Эта функция обычно работает только c парой (K,V), хранящейся в узле. Операция ИНФИКСНЫЙ_ОБХОД реализуется рекурсивным образом: сначала она запускает себя для левого поддерева, потом выполняет функцию обратного вызова для корня, а затем вызывает себя для правого поддерева.