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

Алгоритм поиска в дереве бинарного поиска имитирует стандартный бинарный поиск в массиве или в связном списке. В каждом узле мы принимаем решение, какой дочерней связью нужно следовать. При этом можно игнорировать все узлы, находящиеся в другом дочернем дереве. Если дерево сбалансировано, алгоритм поиска является операцией типа O(log(n)). Другими словами, среднее время, затрачиваемое на поиск любого элемента, пропорционально log(_2_) от числа элементов в дереве. Под сбалансированным мы будем понимать дерево, в котором длина пути от любого листа до корневого узла приблизительно одинакова, причем дерево имеет минимальное количество уровней, необходимое для данного количества присутствующих узлов.

Листинг 8.13. Поиск в дереве бинарного поиска

function TtdBinarySearchTree.bstFindItem(aItem : pointer;

var aNode : PtdBinTreeNode;

var aChild : TtdChildType): boolean;

var

Walker : PtdBinTreeNode;

CmpResult : integer;

begin

Result := false;

{если дерево пусто, вернуть нулевой и левый узел для указания того, что новый узел, в случае его вставки, должен быть корневым}

if (FCount = 0) then begin

aNode := nil;

aChild := ctLeft;

Exit;

end;

{в противном случае перемещаться по дереву}

Walker := FBinTree.Root;

CmpResult := FCompare(aItem, Walker^.btData);

while (CmpResult <> 0) do

begin

if (CmpResult < 0) then begin

if (Walker^.btChild[ctLeft] = nil) then begin

aNode := Walker;

aChild := ctLeft;

Exit;

end;

Walker := Walker^.btChild[ctLeft];

end

else begin

if (Walker^.btChild[ctRight] =nil) then begin

aNode := Walker;

aChild := ctRight;

Exit;

end;

Walker := Walker^.btChild[ctRight];

end;

CmpResult := FCompare(aItem, Walker^.btData);

end;

Result := true;

aNode := Walker;

end;

function TtdBinarySearchTree.Find(aKeyItem : pointer): pointer;

var

Node : PtdBinTreeNode;

ChildType : TtdChildType;

begin

if bstFindItem(aKeyItem, Node, ChildType) then

Result := Node^.btData else

Result := nil;

end;

В коде, представленном в листинге 8.13, не используются отдельные ключи для каждого элемента. Вместо этого предполагается, что свойство упорядочения дерева бинарного поиска определяется функцией сравнения, подобно тому, как это делалось в отсортированных связных списках, списках с пропусками и т.п. Функция сравнения дерева бинарного поиска объявляется конструктором Create.

Метод Find использует внутренний метод bstFindItem. Этот метод должен вызываться для достижения двух различных целей. Во-первых, самим методом Find, и, во-вторых, методом, который вставляет новые узлы в дерево (этот метод мы рассмотрим несколько позже). Соответственно, если элемент не был найден, метод будет возвращать место, в которое он должен быть вставлен. Естественно, эта функция не требуется для простого поиска: нам нужно только знать, существует ли элемент, и если существует, то получить элемент целиком обратно.

В представленном коде следует также отметить, что класс используется внутренний экземпляр TtdBinaryTree, названный FBinTree, для хранения фактического бинарного дерева. Как будет показано, класс дерева бинарного поиска делегирует все операции бинарного дерева этому внутреннему бинарному дереву. Легко заметить, что от этого внутреннего объекта требуется получить только корневой узел. С этого момента остается только перемещаться по узлам.

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

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

Тем не менее, алгоритм вставки сопряжен с одной проблемой. Хотя метод гарантирует создание допустимого дерева бинарного поиска после выполнения операции, созданное дерево может быть неоптимальным или неэффективным. Чтобы понять, о чем идет речь, вставьте элементы a, b, c, d, e и f в пустое дерево бинарного поиска. С элементом а все просто - он становится корневым узлом. Элемент b добавляется в качестве правого дочернего узла элемента a. Элемент c добавляется в качестве правого дочернего узла элемента b и т.д. Результат показан слева на рис. 8.2: он представляет собой длинное вытянутое дерево, которое можно трактовать как связного списка. В идеале желательно, чтобы дерево было более сбалансированным. Для только что созданного вырожденного дерева время поиска пропорционально числу элементов в дереве (О(n)), а не log(_2_) числа элементов (O(log(n))). Возможны также другие случаи вырождения. Например, попытайтесь выполнить следующую последовательность вставок: a, f, b, e, c и d, в результате которой создается явно вырожденное дерево, показанное справа на рис. 8.2.

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

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

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

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

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

Возвращаясь к простому алгоритму вставки, мы видим, что для вставки n элементов в дерево бинарного поиска в среднем требуется время, пропорциональное O(n log(n)) (другими словами, для каждой вставки используется алгоритм O(log(n)) для выяснения места, в которое должен быть помещен новый элемент, а количество вставляемых элементов равно n). В случае вырождения вставка n элементов превращается в операцию типа O(n(^2^)).