Бинарные деревья поиска
Напомним, что под бинарным деревом понимается такая структура данных, которая либо является пустой, либо состоит из вершины, называемой корнем дерева и связанной с двумя другими бинарными деревьями, называемыми левым и правым сыновьями корня.
Мы будем рассматривать такие бинарные деревья, у которых с каждой вершиной связано значение этой вершины. Это значение может в общем случае состоять из поля ключа и поля данных, т.е. бинарное дерево можно рассматривать как иное представление таблицы, отличное от более привычного ее представления в виде массива. Как и раньше, мы для простоты будем считать, что значение вершины содержит только ключ.
Бинарным деревом поиска называется такое бинарное дерево, у которого для каждой вершины A все значения вершин левого поддерева A не превышают значения A, а все значения вершин правого поддерева A не меньше, чем значение A.
По-другому можно сказать, что бинарное дерево поиска – это такое дерево, при обходе которого слева направо значения вершин будут перечисляться в порядке возрастания.
Поиск ключа по бинарному дереву имеет много общего с процедурой бинарного поиска в массиве. В том и другом случае после проверки на совпадение с искомым ключом одного из значений (раньше это было значение из середины массива, теперь – значение корня дерева) выполняется переход либо к меньшим, либо к большим значениям ключей. Разница в том, что вместо вычисления индекса следующего проверяемого элемента здесь просто выполняется переход либо к левому, либо к правому сыну проверенной вершины.
Опишем структуры данных для представления таблицы в виде бинарного дерева.
type
Tree = ^Node; {Дерево есть указатель на его корень}
Node = record {Вершина дерева}
key: KeyType; {Ключ}
left, right: Tree; {Два сына (поддерева)}
end;
Функция поиска по дереву со вставкой может в рекурсивном варианте выглядеть, как показано ниже.
function TreeSearch(
var t: Tree; {Корень дерева}
x: KeyType; {Искомый ключ}
var found: Boolean {Найдено или вставлено?}
): Tree; {Возвращает указатель на вершину}
begin
if t = nil then begin {Вставка новой вершины}
found := false; {Не найдено, будет вставлено}
New(t);
t^.left := nil;
t^.right := nil;
t^.key := x;
TreeSearch := t;
end
else if t^.key < x then
TreeSearch := TreeSearch(t^.right, x, found)
else if t^.key > x then
TreeSearch := TreeSearch(t^.left, x, found)
else begin {t^.key = x}
found := true; {Найдено!}
TreeSearch := t;
end;
end; {TreeSearch}
Пока значение ключа текущей вершины не равно искомому, функция выполняет спуск по дереву, переходя к левому или правому сыну вершины. Спуск заканчивается либо когда будет найден искомый ключ, либо когда очередное поддерево оказывается пустым. Это означает, что искомый ключ отсутствует в дереве и должен быть вставлен в соответствующем месте. Значением функции будет указатель на найденную либо вставленную вершину.
Если функция выполнит вставку новой вершины, то исходное дерево изменится, однако оно сохранит свойства дерева поиска.
Время работы функции определяется числом шагов спуска по дереву выполненных при поиске. Время выполнения вставки не зависит от размеров дерева, поэтому оно не повлияет на оценку в смысле O-большое.
Максимальное число шагов спуска ограничено высотой дерева поиска. Как связана высота h с числом вершин дерева n? Это зависит от распределения вершин в дереве.
Наиболее предпочтительным для поиска видом деревьев являются идеально сбалансированные деревья (ИС-деревья). Это такие бинарные деревья, у которых для каждой вершины количества вершин в ее левом и правом поддеревьях различаются не больше, чем на 1. Легко доказать, что длины всех ветвей ИС-дерева также различаются не более, чем на 1.
Примеры ИС-деревьев поиска с разным числом вершин показаны на рис. 4.1.
Рис. 4.1. Примеры идеально сбалансированных деревьев поиска
Нетрудно доказать, что ИС-дерево высоты h может иметь от 2h–1 до 2h – 1 вершин. Отсюда можно получить и обратную зависимость – оценку высоты для данного числа вершин: h £ log2n + 1. Получается, что время поиска по ИС-дереву имеет логарифмическую оценку: T(n) = O(log(n)), аналогично бинарному поиску в сортированном массиве.
Проблема заключается в том, что сбалансированность дерева обеспечить трудно. Предположим, что на вход программы, строящей бинарное дерево поиска с помощью функции TreeSearch, поступает монотонно возрастающая последовательность ключей. Нетрудно видеть, что в этом случае каждая новая вершина будет включаться в дерево как правый сын предыдущей вершины, а левых сыновей в этом дереве не будет вовсе. Результатом будет крайне несбалансированное вырожденное дерево, по сути представляющее собой линейный список. Для вырожденного дерева его высота равна числу вершин, а стало быть, T(n) = O(n).
С другой стороны, пусть нам удалось каким-то образом построить ИС-дерево из n вершин. Если затем в это дерево будет добавлено еще хотя бы 1-2 вершины, то его балансировка может быть нарушена и для ее восстановления придется заново строить все дерево, затратив на это время порядка O(n).
Таким образом, для несбалансированного дерева время порядка O(n) может тратиться на каждый поиск ключа, а для идеально сбалансированного аналогичное время будет затрачиваться на процедуру перебалансировки после добавления вершины.
Разумеется, вырожденное дерево – это заведомо худший случай. В среднем дело обстоит не так плохо. Доказано, что если вершины добавляются в случайном порядке, то математическое ожидание высоты получившегося дерева будет иметь логарифмическую оценку и лишь примерно на 40 % превысит высоту ИС-дерева с тем же количеством вершин.
Ситуация напоминает ту, которая характерна для алгоритма QuickSort: в среднем все очень хорошо, но не исключен и худший случай, когда все становится плохо.
До сих пор мы говорили только о добавлении вершин (записей) в бинарное дерево поиска. Выполнение удаления вершин несколько сложнее, поскольку нужно уметь удалять не только листья, но и внутренние вершины дерева, и при этом нужно обеспечить сохранение целостности дерева. Не вдаваясь в подробности, покажем на рис. 4.2, как выполняется удаление на примере разных вершин одного и того же дерева.
Рис. 4.2. Удаление вершин из дерева поиска
На рис. 4.2, а показано удаление вершины A, не имеющей сыновей. Здесь проблем не возникает.
На рис. 4.2, б иллюстрируется удаление вершины B, имеющей одного сына. При этом у отца удаляемой вершины освобождается одна связь, к которой и присоединяется «осиротевший внук». Очевидно, что сортированность дерева поиска при этом сохраняется.
На рис. 4.2, в показан самый сложный случай – удаление вершины C, имеющей двух сыновей. Чтобы при этом не развалить дерево и сохранить его сортированность, поступают следующим образом. Для удаляемой вершины ищется ближайшая к ней слева вершина. Для этого нужно сначала перейти от C к ее левому сыну, а затем спускаться направо, пока не попадем в вершину, не имеющую правого сына. В данном примере это вершина D. Далее следует поменять местами удаляемую вершину C и ее левого соседа D (это можно сделать либо путем манипуляций указателями, либо просто обменяв записи таблицы, связанные с вершинами). На новом месте вершина C имеет не более одного сына (ибо правого сына она не имеет), а потому может быть удалена, как в случае а или б. Легко видеть, что сортированность дерева не будет нарушена после этих операций.
Удаление вершин, как и их добавление, может нарушить сбалансированность дерева и в худшем случае привести к его вырожденности.