Динамические деревья: различия между версиями

ST-дерево (согласно алгоритму из [   ]). В левой части представлено исходное дерево с корнем в вершине a, уже разбитое на пути; в правой части – текущая структура данных. Дуги, изображенные сплошными линиями, соединяют вершины одного и того же пути; изображенные пунктиром – соединяют разные пути

При использовании стандартных сбалансированных бинарных деревьев поиска (например, красно-черных деревьев) ST-деревья поддерживают операции динамического дерева с амортизированным временем исполнения O(log2 n). Это значение может быть улучшено до амортизированного времени O(log n) при помощи локально смещенных бинарных деревьев поиска, и до O(log n) в наихудшем случае – при помощи глобально смещенных бинарных деревьев поиска. Однако смещенные деревья поиска [5] сами по себе достаточно сложны. Более практичная реализация ST-деревьев использует косые деревья – самонастраивающиеся бинарные деревья поиска, поддерживающие все операции динамического дерева с амортизированным временем исполнения O(log n) [14].

В отличие от ST-деревьев, которые представляют входные деревья непосредственно, топологические деревья Фредериксона [6, 7, 8] представляют стягивание каждого дерева. Исходные вершины представляют собой 0 уровень стягивания. Уровень 1 представляет разбиение этих вершин на кластеры: вершина первой степени может комбинироваться только с ее соседом; вершины второй степени, смежные друг с другом, могут быть объединены в кластер; другие вершины остаются одиночными. Конечный результат представляет собой дерево меньшего размера, разбиение которого на кластеры дает уровень 2. Процесс продолжается до тех пор, пока не останется один кластер. Стягивание представлено в виде топологического дерева, в котором каждый кластер имеет потомков – кластеры, из которых он состоит на предыдущем уровне.

Топологическое дерево (согласно алгоритму из [   ]). В левой части представлено исходное дерево и его многоуровневое разбиение; в правой части – соответствующее топологическое дерево.

Понятие стягивания дерева было независимо разработано Миллером и Рейфом [ ] в контексте параллельных алгоритмов. Они предложили две базовые операции: обрезку (rake), которая удаляет вершины первой степени, и сжатие (compress), удаляющее вершины второй степени. Авторы показали, что O(log n) повторений этих операций достаточно для стягивания любого дерева в единственный кластер. Акар и коллеги преобразовали вариацию своего алгоритма в структуру данных в виде динамического дерева – RC-дерево [1], которое также можно рассматривать как рандомизированную и упрощенную версию топологического дерева.

Недостаток топологических деревьев и RC-деревьев заключается в том, что лес, на основе которого они строятся, должен иметь вершины с ограниченными (константными) степенями, чтобы гарантировать время O(log n) на исполнение операции. И хотя ST-деревья не имеют подобного ограничения при сборе информации по путям, им необходимы ограниченные степени для сбора информации по деревьям. Ограничения по степени могут быть обойдены при помощи «растроения» исходного леса (замены вершины с высокой степенью серией вершин с низкими степенями [ ]), но при таком подходе возникают несколько специальных случаев.

«Верхушки деревьев», введенные Алструпом и коллегами [3, 4], не имеют подобных ограничений, в силу чего они позволяют охватить более общие случаи, чем все рассмотренные ранее структуры данных. Их кластеры также создаются при помощи процедуры стягивания дерева, однако они ведут себя скорее как дуги, чем как вершины. Кластер типа «сжатие» объединяет две дуги, имеющие общую вершину второй степени; кластер типа «обрезка» объединяет дугу, содержащую конечную точку первой степени, с дугой, дугой, смежной с ее второй конечной точкой.

Операции обрезки и сжатия в алгоритме, использующем верхушки деревьев [16]