Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

Рисунок 8.2. Вырожденные деревья бинарного поиска

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

-----------------

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

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

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

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

Второй тип узла - узел только с одним дочерним узлом. В случае стандартного бинарного дерева мы просто перемещаем дочерний узел на один уровень вверх, чтобы заменить удаляемый узел. Можно ли это же сделать в данном случае? Рассмотрим родительский узел узла, который должен быть удален. Удаленный узел является либо левым дочерним узлом (в этом случае его ключ меньше ключа родительского узла), либо правым дочерним узлом (в этом случае его ключ больше ключа родительского узла). Не только этот узел, но и все дочерние, "внучатые" и так далее узлы удаленного узла обладают тем же свойством. Все они будут либо меньше родительского узла, либо больше. Таким образом, до тех пор, пока речь идет о родительском узле, при замене узла одним из его дочерних узлов свойство упорядочения будет сохраняться. Если дочерний узел имеет свои дочерние узлы, это перемещение не сказывается на них или на их порядке. Следовательно, в случае дерева бинарного поиска мы по-прежнему можем выполнить эту простую операцию.