В дереве бинарного поиска каждый узел имеет ключ. (В деревьях бинарного поиска, которые будут построены в этой главе, считается, что ключ является частью элемента, вставляемого в дерево. Для сравнения двух элементов, а, следовательно, и их ключей, мы будем использовать подпрограмму TtdConrpare.) Упорядочение применяется ко всем узлам в дереве: для каждого узла ключ левого дочернего узла меньше или равен ключу узла, а этот ключ, в свою очередь, меньше или равен ключу правого дочернего узла. Если описанное упорядочение постоянно применяется во время вставки (как именно - будет показано чуть ниже), это также означает, что для каждого узла все ключи в левом дочернем дереве меньше или равны ключу узла, а все ключи в правом дочернем дереве больше или равны ключу узла.
Какие основные операции претерпевают изменения в случае использования дерева бинарного поиска вместо обычного бинарного дерева? Что ж, все алгоритмы обхода работают так же, как и ранее (фактически, при симметричном обходе все узлы в дереве бинарного поиска посещаются в порядке ключей - отсюда и английское название этого метода "in-order"). Однако операции вставки и удаления должны быть изменены, поскольку они могут нарушить порядок ключей в дереве бинарного поиска. Поиск элемента может быть выполнен значительно быстрее.
Алгоритм поиска в дереве бинарного поиска использует упорядоченность дерева. Поиск элемента выполняется следующим образом. Поиск начинается с корневого узла, и этот узел становится текущим. Затем ключ искомого элемента сравнивается с ключом текущего узла. Если они равны, дело сделано, поскольку мы нашли требуемый элемент в дереве. В противном случае, если ключ элемента меньше ключа текущего узла, мы делаем левый дочерний узел текущим. Если он больше, мы делаем текущим правый дочерний узел и возвращаемся к шагу выполнения сравнения. Со временем мы либо найдем нужный узел, либо встретим нулевой дочерний узел, что свидетельствует об отсутствии искомого элемента в дереве.
Следует отметить одну особенность этого алгоритма в случае наличия в дереве нескольких элементов с равными ключами: не существует никаких гарантий, что мы найдем какой-то конкретный элемент с соответствующим ключом. Им может оказаться первый элемент, последний или любой промежуточный. Фактически, в основном по тем же причинам, что и при использовании списка с пропусками, желательно гарантировать, чтобы все элементы в дереве бинарного поиска имели уникальные, различающиеся между собой ключи. Присутствие дублированных ключей не допускается. На практике это правило не создает особых трудностей: если можно различить два элемента, должно быть не трудно обеспечить их различение и в дереве бинарного поиска. Обычно это достигается за счет использования младших ключей (например, фамилия служит в качестве главного ключа, а имя - в качестве контрольного значения, когда фамилии совпадают). Таким образом, деревья бинарного поиска, рассмотренные в этой главе, будут подчиняться правилу недопустимости дублированных ключей. В результате определение дерева бинарного поиска будет формулироваться следующим образом: это дерево, в котором ключ левого дочернего узла строго меньше ключа данного узла, который, в свою очередь, строго меньше ключа правого дочернего узла.
Алгоритм поиска в дереве бинарного поиска имитирует стандартный бинарный поиск в массиве или в связном списке. В каждом узле мы принимаем решение, какой дочерней связью нужно следовать. При этом можно игнорировать все узлы, находящиеся в другом дочернем дереве. Если дерево сбалансировано, алгоритм поиска является операцией типа 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;