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

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

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

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

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

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

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

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

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

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

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

 

Обход дерева

 

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

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

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

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

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

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

 

Инфиксный (симметричный) обход дерева

 

Дано: дерево Т и функция f

Задача: применить f ко всем узлам дерева Т в порядке возрастания ключей

Алгоритм обхода дерева

1. Если дерево пусто, остановиться.

1.1. Иначе

1.1.1.Рекурсивно обойти правое поддерево Т.

1.1.2.Применить функцию f к корневому узлу.

1.1.3.Рекурсивно обойти левое поддерево Т.

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

 

Поиск элемента в дереве

 

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

d) совпадению,

e) близости снизу

f) близости сверху.

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

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

 

Поиск элемента двоичного дерева

 

Рассмотрим алгоритм поиска по совпадению.

Поиск элемента (ИСКАТЬ)

Дано: дерево Т и ключ K.

Задача: проверить, есть ли узел с ключом K в дереве Т, и если да, то вернуть ссылку на этот узел.