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

• Название: Фундаментальные алгоритмы и структуры данных в Delphi
• Автор: Джулиан Бакнелл
• Издательство: ДиаСофтЮП
• Жанр: Программирование
• Год: 2003
• ISBN: ISBN 5-93772-087-3

Книга "Фундаментальные алгоритмы и структуры данных в Delphi" представляет собой уникальное учебное и справочное пособие по наиболее распространенным алгоритмам манипулирования данными, которые зарекомендовали себя как надежные и проверенные многими поколениями программистов. По данным журнала "Delphi Informant" за 2002 год, эта книга была признана сообществом разработчиков прикладных приложений на Delphi как «самая лучшая книга по практическому применению всех версий Delphi».

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

Несмотря на то что книга рассчитана в первую очередь на профессиональных разработчиков приложений на Delphi, она окажет несомненную пользу и начинающим программистам, демонстрируя им приемы и трюки, которые столь популярны у истинных «профи». Все коды примеров, упомянутые в книге, доступны для выгрузки на Web-сайте издательства.

---

Рисунок 8.15. Балансировка после удаления: заключительный случай

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

братский узел был черным, а дальний узел-племянник красным (цвет родительского узла и ближайшего узла-племянника "не имели значения");

и, наконец, случай, когда братский узел был черным, дальний узел-племянник черным, а ближайший узел-племянник красным. Если вы еще раз взглянете на рисунки 8.12, 8.13, 8.14 и 8.15, то убедитесь, что мы рассмотрели все варианты.

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

Операция удаления узла из красно-черного дерева реализуется с помощью кода, представленного в листинге 8.25.

Листинг 8.25. Удаление из красно-черного дерева

procedure TtdRedBlackTree.Delete(aItem : pointer);

var

Node : PtdBinTreeNode;

Dad : PtdBinTreeNode;

Child : PtdBinTreeNode;

Brother : PtdBinTreeNode;

FarNephew : PtdBinTreeNode;

NearNephew : PtdBinTreeNode;

IsBalanced : boolean;

ChildType : TtdChildType;

begin

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

Node := bstFindNodeToDelete(aItem);

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

if (Node^.btColor = rbRed) or (Node = FBinTree.Root) then begin

FBinTree.Delete(Node);

dec(FCount);

Exit;

end;

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

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

Child := Node^.btChild[ctRight] else

Child :=Node^.btChild[ctLeft];

if IsRed(Child) then begin

Child^.btColor :=rbBlack;

FBinTree.Delete(Node);

dec(FCount);

Exit;

end;

{на этом этапе узел, который нужно удалить, - узел Node; он является черным и известно, что дочерний узел Child, который его заменит, является черным (а также может быть нулевым!) и что существует родительский узел узла Node (который вскоре станет родительским узлом узла Child); братский узел узла Node также существует в соответствии с правилом, сформулированным для черных узлов}

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

if (Child = nil) then begin

Dad := Node^.btParent;

if (Node = Dad^.btChild[ctLeft]) then begin

ChildType :=ctLeft;

Brother := Dad^.btChild[ctRight];

end

else begin

ChildType :=ctRight;

Brother := Dad^.btChild[ctLeft];

end;

end

else begin

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

Dad := nil;

Brother := nil;

ChildType :=ctLeft;

end;

{удалить узел — он больше не нужен}

FBinTree.Delete(Node);

dec(FCount);

Node := Child;

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

repeat

{предположим, что дерево сбалансировано}

IsBalanced := true;

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

if (Node <> FBinTree.Root) then begin

{получить родительский и братский узлы}

if (Node <> nil) then begin

Dad := Node^.btParent;

if (Node = Dad^.btChild[ctLeft]) then begin

ChildType := ctLeft;

Brother := Dad^.btChild[ctRight];

end

else begin

ChildType := ctRight;

Brother := Dad^.btChild[ctLeft];

end;

end;

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

if (Brother^.btColor = rbRed) then begin

Dad^.btColor := rbRed;

Brother^.btColor :=rbBlack;

rbtPromote(Brother);

IsBalanced := false;

end

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

else begin

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

if (ChildType = ctLeft) then begin

FarNephew := Brother^.btChild[ctRight];

NearNephew := Brother^.btChild[ctLeft];

end

else begin

FarNephew := Brother^.btChild[ctLeft];

NearNephew := Brother^.btChild[ctRight];

end;

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

if IsRed( FarNephew) then begin

FarNephew^.btColor :=rbBlack;

Brother^.btColor := Dad^.btColor;

Dad^.btColor :=rbBlack;

rbtPromote(Brother);

end

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

else begin

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

if isRed(NearNephew) then begin

NearNephew^.btColor := Dad^.btColor;

Dad^.btColor :=rbBlack;

rbtPromote(rbtPromote(NearNephew));

end

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

else begin

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

if (Dad^.btColor = rbRed) then begin

Dad^.btColor :=rbBlack;

Brother^.btColor := rbRed;

end

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

else begin

Brother^.btColor := rbRed;

Node := Dad;

IsBalanced := false;

end;

end;

end;

end;

end;

until IsBalanced;

end;

За исключением перекрытых методов Insert и Delete, класс TtdRedBlackTree не представляет особого интереса. Код интерфейса и дополнительного внутреннего метода, выполняющего повышение ранга узла, приведен в листинге 8.26.

Листинг 8.26. Класс TtdRedBlack и метод повышения ранга узла

type

TtdRedBlackTree = class(TtdBinarySearchTree) private protected

function rbtPromote(aNode : PtdBinTreeNode): PtdBinTreeNode;

public

procedure Delete(aItem : pointer); override;

procedure Insert(aItem : pointer); override;

end;

function TtdRedBlackTree.rbtPromote(aNode : PtdBinTreeNode): PtdBinTreeNode;

var

Parent : PtdBinTreeNode;

begin

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

Parent := aNode^.btParent;

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

{повысить ранг левого дочернего узла, т.е. выполнить поворот родительского узла вправо}

if (Parent^.btChild[ctLeft] = aNode) then begin

Parent^.btChild[ctLeft] := aNode^.btChild[ctRight];

if (Parent^.btChild[ctLeft]<> nil) then

Parent^.btChild[ctLeft]^.btParent := Parent;

aNode^.btParent := Parent^.btParent;

if (aNode^.btParent^.btChild[ctLeft] = Parent) then

aNode^.btParent^.btChild[ctLeft] := anode

else

aNode^.btParent^.btChild[ctRight J := aNode;

aNode^.btChild[ctRight] := Parent;

Parent^.btParent := aNode;

end

{повысить ранг правого дочернего узла, т.е. выполнить поворот родительского узла влево}

else begin

Parent^.btChild[ctRight] := aNode^.btChild[ctLeft];

if (Parent^.btChild[ctRight]<> nil) then

Parent^.btChild[ctRight]^.btParent := Parent;

aNode^.btParent := Parent^.btParent;

if (aNode^.btParent^.btChild[ctLeft] = Parent) then

aNode^.btParent^.btChild[ctLeft] := anode else

aNode^.btParent^.btChild[ctRight] := aNode;

aNode^.btChild[ctLeft] := Parent;

Parent^.btParent := aNode;

end;

{вернуть узел, ранг которого был повышен}

Result := aNode;

end;

Исходный код класса TtdRedBlackTree можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDBinTre.pas.

Резюме

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

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

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

Глава 9. Очереди по приоритету и пирамидальная сортировка.

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