Шаг 150.
Основы языка Haskell.
Рекурсивные типы данных. BST-деревья. Скошенные деревья

    На этом шаге мы рассмотрим такого типа деревья.

    Структура данных "скошенное дерево" была изобретена Д.Д.Слейтором (D.D.Sleator) и Р.Е.Тарьяном (R.E.Tarjan) в 1985 г.

Определение (по [1, с. 335]).
Скошенное дерево (от англ. splay tree) - это бинарное дерево поиска, сконструированное так, что любое обращение к узлу приводит к выполнению операции "скос" в сторону корневого узла.

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

    В общем случае время обращения к часто (редко) посещаемым узлам будет меньше (больше) среднего времени обращения.

1. Операция "поиск элемента в скошенном дереве"

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

    Обнаружив этот узел, выполняем операцию "скос этого узла к корню". Иначе говоря, мы применяем операции "спаренный двусторонний поворот" либо "спаренный односторонний поворот", перемещая узел вверх по дереву до тех пор, пока он не достигнет позиции корня.

    Более подробно:

2. Операция "включение элемента в скошенное дерево"

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

3. Операция "удаление элемента из скошенного дерева"

    Вначале необходимо выполнить классическое удаление из бинарного дерева поиска, а затем выполнить операцию "скос" для родительского узла удалённого узла.


    Замечание (важное). Скошенное дерево не обладает явными функциями, реализующими балансировку дерева, но практика свидетельствует, что выполнение операции "скос" способствует успешному поддержанию дерева в сбалансированном состоянии.

    В среднем время поиска в скошенном дереве пропорционально O(log2n), где n - количество вершин в скошенном дереве.


(1) Бакнелл Д.М. Фундаментальные алгоритмы и структуры данных в Delphi. - СПб.: ООО "ДиаСофтЮП", 2003. - 560 с.

    На следующем шаге мы рассмотрим операцию "объединение бинарных деревьев поиска" .




Предыдущий шаг Содержание