На этом шаге мы рассмотрим такого типа деревья.
Структура данных "скошенное дерево" была изобретена Д.Д.Слейтором (D.D.Sleator) и Р.Е.Тарьяном (R.E.Tarjan) в 1985 г.
- Определение (по [1, с. 335]).
- Скошенное дерево (от англ. splay tree) - это бинарное дерево поиска, сконструированное так, что любое обращение к узлу приводит к выполнению операции "скос" в сторону корневого узла.
Скошенное дерево является самоорганизующейся структурой данных, т.е. структурой, характеризующейся тенденцией хранить узлы, к которым часто происходит обращение, в окрестности корня дерева, в то время как узлы, к которым обращение происходит редко, перемещаются по направлению к листьям.
В общем случае время обращения к часто (редко) посещаемым узлам будет меньше (больше) среднего времени обращения.
1. Операция "поиск элемента в скошенном дереве"
Вначале выполняется операция поиска заданного узла с помощью классического алгоритма поиска в бинарном дереве поиска.
Обнаружив этот узел, выполняем операцию "скос этого узла к корню". Иначе говоря, мы применяем операции "спаренный двусторонний поворот" либо "спаренный односторонний поворот", перемещая узел вверх по дереву до тех пор, пока он не достигнет позиции корня.
Более подробно:
- (1) если узел, его родительский и прародительский узлы расположены на "одной линии", то выполняется повышение уровня узла за счёт выполнения операции "спаренный односторонний поворот";
- (2) в противном случае применяется повышение уровня за счёт выполнения операции "спаренный двусторонний поворот";
- (3) этот процесс выполняется до тех пор, пока либо уровень узла не совпадёт с уровнем корня, либо родительский узел данного узла не станет корневым; в последнем случае необходимо выполнить ещё одно повышение уровня, т.е. если в результате этих операций узел оказывается на уровне с номером 1 (корень расположен на уровне 0), мы больше не можем применять операцию "спаренный поворот", и поэтому для перемещения в позицию корневого узла применяется операция "ротация" в нужном направлении;
- (4) если поиск был безрезультатным, то мы попадём в лист; в этом случае мы выполняем операцию "скос" для узла, который был родительским узлом, если бы искомый узел существовал (при этом, конечно, необходимо сообщить об отсутствии в дереве искомого элемента).
2. Операция "включение элемента в скошенное дерево"
Вначале необходимо применить классический алгоритм включения элемента в бинарное дерево поиска, а затем выполнить операцию "скос" для узла, добавляемого в дерево.
3. Операция "удаление элемента из скошенного дерева"
Вначале необходимо выполнить классическое удаление из бинарного дерева поиска, а затем выполнить операцию "скос" для родительского узла удалённого узла.
Замечание (важное). Скошенное дерево не обладает явными функциями, реализующими балансировку дерева, но практика свидетельствует, что выполнение операции "скос" способствует успешному поддержанию дерева в сбалансированном состоянии.
В среднем время поиска в скошенном дереве пропорционально O(log2n), где n - количество вершин в скошенном дереве.
(1) Бакнелл Д.М. Фундаментальные алгоритмы и структуры данных в Delphi. - СПб.: ООО "ДиаСофтЮП", 2003. - 560 с.
На следующем шаге мы рассмотрим операцию "объединение бинарных деревьев поиска" .
