Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
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;
Перекрытый
Листинг 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).
Понятно, что этот подход применяется не просто для раскрашивания узлов, и в действительности необходимо выполнить еще три правила: