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

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

Класс 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.

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

Что должен делать алгоритм балансировки? В идеале он должен обеспечивать, чтобы длина пути от любого из листьев до корневого узла была одинаковой с точностью до единицы. На практике удовлетворить это строгое требование несколько затруднительно (AVL-деревья соответствуют этому определению, и их алгоритм балансировки удовлетворяет данному правилу). Поэтому мы определим какой-то алгоритм, который обеспечивает удовлетворение "менее строгого" требования, но не до такой степени "менее строгого", чтобы мы вернулись к тому, с чего начали.

В 1978 году Гюиба (Guibas) и Седжвик (Sedgewick) изобрели концепцию красно-черного дерева, удовлетворяющего такому умеренно нестрогому требованию. Красно-черные деревья (RB-деревья) - это структуры данных, используемые для реализации карт преобразования данных в библиотеке стандартных шаблонов С++ (С++ Standard Template Library). Красно-черный алгоритм предоставляет быстрый и эффективный метод балансировки дерева бинарного поиска, требующий для каждого узла не слишком много дополнительного объема памяти для хранения информации, необходимой для балансировки (в действительности для этого достаточно единственного дополнительного разряда).

Так что же собой представляют красно-черные деревья? Прежде всего, это дерево бинарного поиска, обладающее обычным простым алгоритмом поиска. Однако в красно-черном дереве каждый узел содержит определенную дополнительную информацию: каждый из них помечается как находящийся в одном из двух состояний. Эти два состояния называются красным (red) и черным (black).