Класс 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(altem : pointer);
override;
function Find(aKeyItem : pointer) : pointer;
override; procedure Insert (altem : pointer);
override;
end;

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

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

function TtdSplayTree.Find(aKeyltern : pointer) : pointer;
var
Node : PtdBinTreeNode;
ChildType : TtdChildType;
begin
if bstFindl tern (aKeyl tern, Node, ChildType) then begin
Result := NodeA.btData;
stSplay(Node);
end else
Result := nils-end;

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

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

procedure TtdSplayTree. Insert (altem : pointer); var
ChildType : TtdChildType;
begin
stSplay(bstInsertPrim(altem, ChildType));
end;

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

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

procedure TtdSplayTree. Delete (al tem : pointer); var
Node : PtdBinTreeNode;
Dad : PtdBinTreeNode;
begin
Node := bstFindNodeToDelete(altem) ; Dad : = Node A. btParent ; FBinTree.Delete(Node);
dec(FCount);
if (CountoO) 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 := DadA.btParent; {выполнять операции спаренного двустороннего и одностороннего поворота до тех пор, пока это возможно} while (Grandadonil) do begin
{определить вид двойного повышения ранга, которое необходимо выполнить} if ((GrandadA.btChild[ctLeft] = Dad) and (DadA.btChild[ctLeft] = aNode)) or ( (GrandadA.btChild[ctRight] = Dad) and (DadA.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 := aNodeA .btParent ; if (Dad = RootNode) then Grandad : = nil else
Grandad := DadA.btParent;
ends-end;
{достижение этой точки свидетельствует, что узел находится либо в позиции корневого узла, либо на один уровень ниже него; выполнить последнее повышение ранга, если это необходимо) if (Dadonil) then stPromote(aNode);
end;

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

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

Скошенные деревья || Оглавление || Красно-черные деревья


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



Новости за месяц

  • Октябрь
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс