Фундаментальные алгоритмы и структуры данных в Delphi - Джулиан Бакнелл
Шрифт:
Интервал:
Закладка:
-----------------
Важно иметь в виду следующее. Рассмотренные алгоритмы вставки и удаления гарантированно создают допустимое дерево бинарного поиска. Однако при этом весьма вероятно, что дерево будет скошенным и несбалансированным. Для небольших деревьев бинарного поиска это не имеет особого значения (в конце концов, для малых значений n log(n) и n - величины более-менее одного порядка, поэтому выигрыш в значении О большого будет небольшим), тем не менее, для больших деревьев такое различие поистине огромно.
-----------------
Возвращаясь к простому алгоритму вставки, мы видим, что для вставки n элементов в дерево бинарного поиска в среднем требуется время, пропорциональное O(n log(n)) (другими словами, для каждой вставки используется алгоритм O(log(n)) для выяснения места, в которое должен быть помещен новый элемент, а количество вставляемых элементов равно n). В случае вырождения вставка n элементов превращается в операцию типа O(n(^2^)).
Листинг 8.14. Вставка в дерево бинарного поиска
function TtdBinarySearchTree.bstInsertPrim(aItem : pointer;
var aChildType : TtdChildType): PtdBinTreeNode;
begin
{вначале предпринять попытку найти элемент; если он найден, сгенерировать ошибку}
if bstFindItem(aItem, Result, aChildType) then
bstError(tdeBinTreeDupItem, 'bstInsertPrim');
{эта операция возвращает узел, поэтому вставку потребуется выполнить здесь}
Result := FBinTree.InsertAt(Result, aChildType, aItem);
inc(FCount);
end;
procedure TtdBinarySearchTree.Insert(aItem : pointer);
var
ChildType : TtdChildType;
begin
bstInsertPrim(aItem, ChildType);
end;
Для выполнения большей части работы мы используем внутреннюю процедуру bstInsertPrim. Это делается для того, чтобы разделить код собственно вставки и код метода Insert, что впоследствии упростит нашу задачу при создании производных деревьев от дерева бинарного поиска для выполнения операции балансировки. Как видите, процедура bstInsertPrim возвращает вставленный узел и использует метод bstFindItem, который уже встречался в листинге 8.13.
Таким образом, фактическую вставку мы делегируем объекту бинарного дерева, который использует свой метод InsertAt.
Удаление из дерева бинарного поиска
Как и при выполнении предыдущей операции, большая часть проблем может быть скрыта от пользователя дерева бинарного поиска. Однако дерево должно выполнить определенную, более сложную задачу.
Естественно, первым шагом является поиск элемента в дереве с применением стандартного алгоритма. Если найти элемент не удастся, придется как-то сообщить о неудаче. В случае обнаружения элемента, поиск может быть прерван в узле одного из трех типов, как это имеет место в стандартном бинарном дереве.
Первый тип узла - узел без дочерних узлов, обе дочерние связи которого являются нулевыми. Иначе говоря, лист. Чтобы удалить узел этого типа, мы просто разрываем его связь с родительским узлом и удаляем его. Это удаление не нарушает порядок узлов в дереве - в конце концов, узел был листом и не имел дочерних узлов.
Второй тип узла - узел только с одним дочерним узлом. В случае стандартного бинарного дерева мы просто перемещаем дочерний узел на один уровень вверх, чтобы заменить удаляемый узел. Можно ли это же сделать в данном случае? Рассмотрим родительский узел узла, который должен быть удален. Удаленный узел является либо левым дочерним узлом (в этом случае его ключ меньше ключа родительского узла), либо правым дочерним узлом (в этом случае его ключ больше ключа родительского узла). Не только этот узел, но и все дочерние, "внучатые" и так далее узлы удаленного узла обладают тем же свойством. Все они будут либо меньше родительского узла, либо больше. Таким образом, до тех пор, пока речь идет о родительском узле, при замене узла одним из его дочерних узлов свойство упорядочения будет сохраняться. Если дочерний узел имеет свои дочерние узлы, это перемещение не сказывается на них или на их порядке. Следовательно, в случае дерева бинарного поиска мы по-прежнему можем выполнить эту простую операцию.
Третий тип узла - узел с двумя дочерними узлами. В стандартном дереве бинарного поиска мы считали попытку удаления узла этого типа ошибкой. Удаление не могло быть выполнено, поскольку не существовало никакого общего способа выполнения операции удаления, который имел бы смысл. В случае дерева бинарного поиска это не так: в данном случае можно воспользоваться свойством упорядочения дерева бинарного поиска.
Ситуация выглядит следующим образом: нам нужно удалить определенный узел (т.е. элемент в этом узле), но он имеет два дочерних узла (каждый из которых имеет собственные дочерние узлы). Алгоритм удаления несколько сложен, поэтому вначале он будет описан словесно, а затем будет показано, как он работает. На практике мы ищем узел, содержащий наибольший элемент, который меньше только того, который мы пытаемся удалить. Затем мы меняем местами элементы в этих двух узлах. И, наконец, мы удаляем второй узел. Он всегда будет соответствовать одному из ранее рассмотренных случаев удаления.
Первый шаг заключается в отыскании наибольшего элемента, меньшего того элемента, который мы пытаемся удалить. Понятно, что он находится в левом дочернем дереве (все элементы этого дерева меньше удаляемого элемента). Кроме того, он является наибольшим элементом этого дерева. Иначе говоря, все остальные элементы, которые могут находиться в левом дочернем дереве, меньше этого элемента. В действительности все элементы в правом дочернем дереве больше этого выбранного элемента (поскольку он меньше элемента, который должен быть удален, а этот элемент, в свою очередь, меньше всех элементов в правом дочернем дереве). Следовательно, он вполне может заменить удаляемый элемент, и это действие не нарушит порядок элементов в дереве.
Но как насчет узла, с позиции которого он был перемещен, и который теперь нужно удалить? В отношении этого конкретного узла важно уяснить, что он не имеет никакого правого дочернего узла. Если бы он имел правый дочерний узел, элемент в дочернем узле должен был бы быть больше элемента, с которым мы поменяли его местами, и, следовательно, первоначально выбранный элемент не мог бы быть наибольшим. Он может иметь левый дочерний узел, но независимо от этого мы знаем, как удалить узел, имеющий не более одного дочернего узла.
При этом все еще остается проблема обнаружения наибольшего элемента, который меньше исходного, предназначенного для удаления. По существу, мы выполняем перемещение по дереву. Начиная с элемента, который нужно удалить, мы переходим к левой дочерней связи. С этого места мы продолжаем перемещаться по правым дочерним связям до тех пор, пока не доберемся до узла, не имеющего никакой правой дочерней связи. Этот элемент гарантированно содержит наибольший элемент, меньший только того элемента, который мы пытаемся удалить.
Обратите также внимание, что удаление, как и вставка, может приводить к созданию вырожденного дерева. Эту проблему решают алгоритмы балансировки, которые мы рассмотрим при ознакомлении с красно-черным вариантом дерева бинарного поиска.
Листинг 8.15. Удаление из дерева бинарного поиска
function TtdBinarySearchTree.bstFindNodeToDelete(aItem : pointer)
: PtdBinTreeNode;
var
Walker : PtdBinTreeNode;
Node : PtdBinTreeNode;
Temp : pointer;
ChildType : TtdChildType;
begin
{попытаться найти элемент; если элемент не найден, сгенерировать признак ошибки}
if not bstFindItem(aItem, Node, ChildType) then
bstError(tdeBinTreeItemMissing, 1bstFindNodeToDelete');
{если узел имеет два дочерних узла, найти наибольший узел, который меньше удаляемого, и поменять местами элементы}
if (Node^.btChild[ctLeft]<> nil) and (Node^.btChild[ctRight]<> nil) then begin
Walker := Node^.btChild[ctLeft];
while (Walker^.btChild[ctRight] <> nil) do
Walker := Walker^.btChild[ctRight];
Temp := Walker^.btData;
Walker^.btData := Node^.btData;
Node^.btData := Temp;
Node := Walker;
end;
{вернуть узел, который нужно удалить}
Result := Node;
end;
procedure TtdBinarySearchTree.Delete(aItem : pointer);
begin
FBinTree.Delete(bstFindNodeToDelete(aItem));
dec(FCount);
end;
Большая часть работы выполняется методом bstFindNodeToDelete. Он вызывает метод bstFindItem, чтобы найти элемент, который требуется удалить (естественно, если он не найден, генерируется ошибка), а затем проверяет, имеет ли найденный узел два дочерних узла. Если имеет, мы ищем узел с наибольшим элементом, который меньше удаляемого элемента. Мы меняем местами элементы в узлах и возвращаем второй элемент.
Реализация класса дерева бинарного поиска
Как обычно, дерево бинарного поиска будет реализовано в виде класса, хотя хотелось бы еще раз предупредить, что его следует использовать только в том случае, если есть уверенность, что вставляемые элементы являются в достаточной степени случайными или их количество достаточно мало, чтобы дерево не выродилось в длинную вытянутую структуру. Основное назначение класса дерева бинарного поиска - попытка сокрытия от пользователя внутренней структуры дерева. Это означает, что пользователь должен иметь возможность использовать класс для поддержания набора элементов в отсортированном порядке и выполнения их обхода без необходимости знания структуры внутренних узлов.
