Книга: Фундаментальные алгоритмы и структуры данных в Delphi

Деревья бинарного поиска

Деревья бинарного поиска

Хотя бинарные деревья являются структурами данных, которые представляют интерес и сами по себе, на практике в основном используют бинарные деревья, содержащие элементы в сортированном виде. Такие бинарные деревья называют деревьями бинарного поиска (binary search tree).

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

ChildType : TtdChildType;

begin

if bstFindItem(aKeyItem, Node, ChildType) then

Result := Node^.btData else

Result := nil;

end;

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

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

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

Оглавление книги