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

На рис. 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) реализует обычную операцию поиска в дереве бинарного поиска и, если узел найден, выполняет его скос к корневому узлу.