Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
Часто эти два вида поворота объединяются попарно и используются в формах так называемых спаренных двухсторонних поворотов (zig-zag) и спаренных односторонних поворотов (zig-zig). Существуют две операции спаренного двустороннего поворота и две операции спаренного одностороннего поворота. Операция спаренного двустороннего поворота состоит либо из поворота вправо, за которым следует поворот влево, либо из поворота влево, за которым следует поворот вправо, причем конечным результатом обеих операций является повышение ранга узла на два уровня. И напротив, операции спаренного одностороннего поворота состоят из двух выполняемых последовательно поворотов вправо или влево. Цель выполнения всех этих спаренных операций состоит в повышении ранга узла на два уровня.
На рис. 8.4 показана операция спаренного двустороннего поворота, которая начинается с поворота влево вокруг узла P. В результате ранг узла R повышается, а ранг узла P понижается. На следующем шаге выполняется вращение вправо вокруг узла G, в результате которого ранг узла R снова повышается, а ранг узла G понижается. Общим результатом операции спаренного двустороннего поворота будет локальная балансировка дерева.
Рисунок 8.4. Операция спаренного двустороннего поворота
На рис. 8.5 изображены обе операции спаренного одностороннего поворота, поскольку они дополняют друг друга. Обратите взимание, что операция спаренного одностороннего поворота всегда начинается с поворота вокруг верхнего узла.
Рисунок 8.5. Операция спаренного одностороннего поворота
Скошенные деревья
Как бы то ни было, ознакомившись с этими операциями простых и спаренных двухсторонних и односторонних поворотов, мы может их использовать в структуре данных, называемой скошенным деревом. Скошенное дерево (splay tree) - это дерево бинарного поиска, сконструированное таким образом, что любое обращение к узлу приводит к его скосу в сторону корневого узла. Скос заключается в применении операций спаренного двустороннего или одностороннего поворота до тех пор, пока скашиваемый узел не окажется в позиции корневого узла дерева или на один уровень ниже него. В последнем случае его ранг можно повысить до корневого узла, выполнив одиночный поворот. Концепция скошенного дерева была изобретена Д. Д. Слеатором (D. D. Sleator) и Р. Е. Таръяном (R. E. Tarjan) в 1985 году [22].
Вначале рассмотрим операцию поиска, т.е. нахождение конкретного узла. Мы начнем с применения стандартного алгоритма поиска в дереве бинарного поиска. Обнаружив искомый узел, мы выполняем его скос к корневому узлу.
Иначе говоря, мы применяем операции спаренного двустороннего либо одностороннего поворота, перемещая узел вверх по дереву до тех пор, пока он не достигнет позиции корневого узла. Если в результате этих операций узел оказывается на втором уровне, мы больше не можем применять операции спаренного поворота, и поэтому для перемещения в позицию корневого узла применяем поворот влево или вправо.
Если поиск был безрезультатным, в ходе него мы должны натолкнуться на нулевой узел. В этом случае мы выполняем скос узла, который был бы родительским узлом, если бы искомый узел существовал. Естественно, при этом следовало бы сообщить о невозможности как-либо найти элемент.
Вставку также легко описать: необходимо применить обычный алгоритм вставки в дерево бинарного поиска, а затем выполнить скос добавленного узла.
Чтобы выполнить удаление, мы выполняем обычное удаление из дерева бинарного поиска, а затем выполняем скос родительского узла того узла, который был удален.
Обобщая, можно сказать, что скошенное дерево предоставляет нам самоизменяющуюся структуру — структуру, характеризующуюся тенденцией хранить узлы, к которым часто происходит обращение, вблизи верхушки дерева, в то время как узлы, к которым обращение происходит редко, перемещаются по направлению к листьям. В общем случае время обращения к часто посещаемым узлам будет меньше, а время обращения к редко посещаемым узлам — больше среднего. Важно отметить, что скошенное дерево не обладает никакими явными функциями балансировки, но практика свидетельствует, что скос способствует достаточно успешному поддержанию дерева в сбалансированном состоянии. В среднем время поиска в скошенном дереве пропорционально 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.
Красно-черные деревья
Рассмотрев простые и спаренные двусторонние и односторонние повороты и ознакомившись с реорганизацией деревьев бинарного поиска за счет использования скошенных деревьев, пора приступить к исследованию соответствующего алгоритма балансировки.
