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

Удаление из сортирующего дерева

Теперь, поскольку мы только что показали, что требуемый элемент расположен в позиции корневого узла, можно приступить к удалению наибольшего узла. Удаление корневого узла и передача этого элемента вызывающей процедуре - не самая лучшая идея. В результате мы получили бы два отдельных дочерних дерева -что было бы полным нарушением атрибута полноты сортирующего дерева. Вместо этого мы заменяем корневой узел последним узлом сортирующего дерева и уменьшаем его размер, тем самым обеспечивая сохранение полноты. Но при этом снова возможно нарушение свойства пирамидальности. Весьма вероятно, что новый корневой узел будет меньше одного или обоих своих дочерних узлов. Поэтому нужно снова исправить сортирующее дерево, чтобы восстановить его свойство пирамидальности. Для этого мы находим больший из двух дочерних узлов и меняем его местами с данным узлом. Как и ранее, эта позиция может нарушать свойство пирамидальности, поэтому мы проверяем, является данный узел меньше одного (или обоих) дочерних узлов и повторяем процесс. Со временем выяснится, что узел погрузился (или "просочился") на уровень, где он больше обоих своих дочерних узлов или является листом, не имеющим дочерних узлов. В любом случае свойство пирамидальное™ восстанавливается. Этот алгоритм называется алгоритмом просачивания вниз (trickle down).

Если реализовать кучу, используя реальное двоичное дерево, подобное описанному в главе 8, выяснится, что при этом расходуется довольно большой объем памяти. Для каждого узла необходимо поддерживать по три указателя: по одному для каждого дочернего узла, чтобы можно было реализовать алгоритм просачивания в нижние уровни дерева, и один для родительского узла, чтобы можно было реализовать алгоритм пузырькового подъема. При каждом обмене узлов местами придется обновлять бесчисленное количество указателей для множества узлов. Обычно в этом случае применяют прием, когда узлы остаются на своих местах, а вместо этого меняют местами элементы внутри узлов.

Однако существует более простой способ. Полное двоичное дерево легко представить массивом. Снова взгляните на рис. 9.1. Выполните просмотр дерева, используя обход по уровням. Обратите внимание, что в полном дереве обход по уровням не затрагивает никаких пробелов, в которых имеется позиция для узла, но какой-либо узел отсутствует (естественно, до тех пор, пока не будут посещены все узлы и не будет достигнут конец дерева). Узлы легко отобразить элементами массива, чтобы последовательное посещение элементов массива было эквивалентно посещению узлов посредством обхода по уровням. При этом элемент 1 массива был бы корневым узлом сортирующего дерева, элемент 2 - левым дочерним узлом корневого узла, элемент 3 - правым дочерним узлом корневого узла и т.д. Фактически, именно так пронумерованы узлы на рис. 9.1.

Теперь обратите внимание на нумерацию дочерних узлов каждого узла. Дочерними узлами корневого узла 1 являются, соответственно, узлы 2 и 3. Дочерними узлами узла 4 являются узлы 8 и 9, а узла 6 - узлы 12 и 13. Заметили ли вы какую-нибудь закономерность? Дочерними узлами узла n являются узлы 2n и 2n + 1, а родительским узлом узла n является узел nil. Теперь уже не обязательно, чтобы узел содержал указатели на родительский и дочерние узлы. Вместо этого можно воспользоваться простым арифметическим отношением. Таким образом, мы изобрели метод реализации сортирующего дерева при помощи массива, и решив более простую задачу, можно было бы снова отдать предпочтение структуре TList.

Проблема заключается в следующем: рассмотренная нами реализация сортирующего дерева в виде массива требует, чтобы отсчет элементов массива начинался единицы, а не с нуля, как имеет место в структуре TList. Этого достаточно легко добиться. Достаточно изменить арифметическую формулу вычисления индекса родительского и дочерних узлов. Дочерние узлы узла n должны располагаться в позициях In + 1 и In + 2, а родительский узел этого узла - в позиции (n -1)11.

Реализация очереди по приоритету при помощи сортирующего дерева

Код интерфейса результирующей очереди по приоритету, в которой используется сортирующее дерево и которая реализована при помощи структуры TList, приведен в листинге 9.3.

Листинг 9.3. Интерфейс класса TtdPriorityQueue

type

TtdPriorityQueue = class private

FCompare : TtdCompareFunc;

FDispose : TtdDisposeProc;

FList : TList;

FName : TtdNameString;

protected

function pqGetCount : integer;

procedure pqError(aErrorCode : integer;

const aMethodName : TtdNameString);

procedure pqBubbleUp(aFromInx : integer);

procedure pqTrickleDown;

procedure pqTrickleDownStd;

public

constructor Create(aCompare : TtdCompareFunc;

aDispose : TtdDisposeProc );

destructor Destroy; override;

procedure Clear;

function Dequeue : pointer;

procedure Enqueue(aItem : pointer);

function Examine : pointer;

function IsEmpty : boolean;

property Count : integer read pqGetCount;

property Name : TtdNameString read FName write FName;

end;

Реализация и конструктора Create, и деструктора Destroy достаточно проста: первый должен создавать экземпляр TList, а второй должен всего лишь освобождать внутренний объект TList. Подобно стандартной очереди, конструктор Create нуждается в процедуре удаления элемента, позволяющей при необходимости освобождать элементы. Но, в отличие от стандартной очереди, теперь нам требуется процедура сравнения, позволяющая определить больший из двух элементов.

Листинг 9.4. Конструктор и деструктор очереди по приоритету

constructor TtdPriorityQueue.Create(aCompare : TtdCompareFunc;

aDispose : TtdDisposeProc);

begin

inherited Create;

if not Assigned(aCompare) then

pqError(tdePriQueueNoCompare, 'Create');

FCompare := aCompare;

FDispose :=aDispose;

FList := TList.Create;

end;

destructor TtdPriorityQueue.Destroy;

begin

Clear;

FList.Free;

inherited Destroy;

end;

Код реализации алгоритма вставки и процедуры, выполняющей реальную операцию пузырькового подъема, показан в листинге 9.5. Операция вставки реализована так, чтобы гарантировать размещение наибольшего элемента в корневом узле. Этот тип очереди по приоритету обычно называют пирамидальной сортировкой выбором максимального элемента (max-heap). Если изменить процедуру сравнения так, чтобы она возвращала отрицательное число, если первый элемент больше второго, в корневом узле очереди по приоритету будет располагаться наименьший элемент. Такая сортировка называется пирамидальной сортировкой выбором наименьшего элемента (min-heap).

Листинг 9.5. Вставка в TtdPriorityQueue: постановка в очередь

procedure TtdPriorityQueue.pqBubbleUp(aFromInx : integer);

var

ParentInx : integer;

Item : pointer;

begin

Item := FList.List^ [aFromInx];

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

{Примечание: родительский узел узла, имеющего индекс n, располагается в позиции (n-1)/2}

ParentInx := (aFromInx - 1) div 2;

{если данный элемент имеет родительский узел и больше родительского элемента...}

while (aFromInx > 0) and (FCompare(Item, FList.List^[ParentInx]) > 0) do

begin

{необходимо переместить родительский элемент вниз по дереву}

FList.List^[aFromInx] := FList.List^[ParentInx];

aFromInx := ParentInx;

ParentInx := (aFromInx - 1) div 2;

end;

{сохранить элемент в правильной позиции}

FList.List^[aFromInx] := Item;

end;

procedure TtdPriorityQueue.Enqueue(aItem : pointer);

begin

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

FList.Add(aItem);

pqBubbleup(pred(FList.Count));

end;

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

Листинг 9.6. Удаление из TtdPriorityQueue: исключение из очереди

procedure TtdPriorityQueue.pqTrickleDownStd;

var

FromInx : integer;

ChildInx : integer;

MaxInx : integer;

Item : pointer;

begin

FromInx := 0;

Item := FList.List^[0];

MaxInx := FList.Count - 1;

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

{Примечание: дочерние узлы родительского узла n располагаются в позициях 2n+1 и 2n+2}

ChildInx := (FromInx * 2) + 1;

{если существует по меньшей мере левый дочерний узел...}

while (ChildInx <= MaxInx) do

begin

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

if (succ(ChildInx) <= MaxInx) and

(FCompare(FList.List^[ChildInx], FList.List^[succ(ChildInx) ]) < 0) then

inc(ChildInx);

{если данный элемент больше или равен большему дочернему элементу, задача выполнена}

if (FCompare(Item, FList.List^[ChildInx]) >= 0) then

Break;

{в противном случае больший дочерний элемент нужно переместить верх по дереву, а сам элемент - вниз по дереву, а затем повторить процесс}

FList.List^[FromInx] := FList.List^[ChildInx];

FromInx := ChildInx;

ChildInx := (FromInx * 2) + 1;

end;

{сохранить элемент в правильной позиции}

FList.List^[FromInx] := Item;

end;

function TtdPriorityQueue.Dequeue : pointer;

begin

{проверить наличие элемента для его исключения из очереди}

if (FList.Count = 0) then

pqError(tdeQueueIsEmpty, 'Dequeue');

{вернуть элемент, расположенный в корневом узле}