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

Реализация класса скошенного дерева

Класс TtdSplayTree представляет собой простой производный класс класса TtdBinarySearchTree, в котором перекрыты методы Delete, Find и Insert и объявлены новые внутренние методы скоса и повышения ранга узла. Код интерфейса этого класса приведен в листинге 8.18.

Листинг 8.18. Интерфейс класса TtdSplayTree

type

TtdSplayTree = class (TtdBinarySearchTree) private protected

function stPromote(aNode : PtdBinTreeNode): PtdBinTreeNode;

procedure stSplay(aNode : PtdBinTreeNode);

public

procedure Delete(aItem : pointer); override;

function Find(aKeyItem : pointer): pointer; override;

procedure Insert(aItem : pointer); override;

end;

Перекрытый метод Find (см. листинг 8.19) реализует обычную операцию поиска в дереве бинарного поиска и, если узел найден, выполняет его скос к корневому узлу.

Листинг 8.19. Метод TtdSplayTree.Find

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

var

Node : PtdBinTreeNode;

ChildType : TtdChildType;

begin

if bstFindItem (aKeyItem, Node, ChildType) then begin

Result := Node^.btData;

stSplay(Node);

end else

Result := nil;

end;

Перекрытый метод Insert(см. листинг 8.20) реализует обычную операцию вставки в дерево бинарного поиска и выполняет скос нового узла к корневому узлу.

Листинг 8.20. Метод TtdSplayTree.Insert

procedure TtdSplayTree.Insert(aItem : pointer);

var

ChildType : TtdChildType;

begin

stSplay(bstInsertPrim(aItem, ChildType));

end;

Перекрытый метод Delete (см. листинг 8.21) реализует обычную операцию удаления из дерева бинарного поиска и выполняет скос родительского узла удаленного узла к корневому узлу.

Листинг 8.21. Метод TtdSplayTree.Delete

procedure TtdSplayTree.Delete(aItem : pointer);

var

Node : PtdBinTreeNode;

Dad : PtdBinTreeNode;

begin

Node := bstFindNodeToDelete(aItem);

Dad := Node^.btParent;

FBinTree.Delete(Node);

dec(FCount);

if (Count <> 0) then

stSplay(Dad);

end;

Эти три перекрытых метода достаточно просты для понимания, поскольку реальная обработка передается методу stSplay. Код реализации этого метода приведен в листинге 8.22.

Листинг 8.22. Метод TtdSplayTree.stSplay

procedure TtdSplayTree.stSplay(aNode : PtdBinTreeNode);

var

Dad : PtdBinTreeNode;

Grandad : PtdBinTreeNode;

RootNode : PtdBinTreeNode;

begin

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

RootNode := FBinTree.Root;

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

if (aNode = RootNode) then

Exit;

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

Dad := aNode^.btParent;

if (Dad = RootNode) then

Grandad := nil else

Grandad := Dad^.btParent;

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

while (Grandad <> nil) do

begin

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

if ((Grandad^.btChild[ctLeft] = Dad) and (Dad^.btChild[ctLeft] = aNode)) or ( (Grandad^.btChild[ctRight] = Dad) and (Dad^.btChild[ctRight] ? aNode)) then begin

{выполнить повышение ранга посредством спаренного одностороннего поворота}

stPromote(Dad);

stPromote(aNode);

end

else begin

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

stPromote(stPromote(aNode));

end;

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

RootNode := FBinTree.Root;

if (aNode = RootNode) then begin

Dad := nil;

Grandad := nil;

end

else begin

Dad := aNode^.btParent;

if (Dad = RootNode) then

Grandad := nil else

Grandad := Dad^.btParent;

end;

end;

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

if (Dad <> nil) then

stPromote(aNode);

end;

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

Код реорганизации при помощи повышения ранга представлен в методе stPromote, который показан в листинге 8.17.

Красно-черные деревья

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