4551
правка
Динамические деревья: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 25: | Строка 25: | ||
''Стягивание дерева'' | ''Стягивание дерева'' | ||
В отличие от ST-деревьев, которые представляют входные деревья непосредственно, топологические деревья Фредериксона [6, 7, 8] представляют стягивание каждого дерева. Исходные вершины представляют собой 0 уровень стягивания. Уровень 1 представляет разбиение этих вершин на кластеры: вершина первой степени может комбинироваться только с ее соседом; вершины второй степени, смежные друг с другом, могут быть объединены в кластер; другие вершины остаются одиночными. Конечный результат представляет собой дерево меньшего размера, разбиение которого на кластеры дает уровень 2. Процесс продолжается до тех пор, пока не останется один кластер. Стягивание представлено в виде топологического дерева, в котором каждый кластер имеет потомков – кластеры, из которых он состоит на предыдущем уровне. | В отличие от ST-деревьев, которые представляют входные деревья непосредственно, топологические деревья Фредериксона [6, 7, 8] представляют стягивание каждого дерева. Исходные вершины представляют собой 0 уровень стягивания. Уровень 1 представляет разбиение этих вершин на кластеры: вершина первой степени может комбинироваться только с ее соседом; вершины второй степени, смежные друг с другом, могут быть объединены в кластер; другие вершины остаются одиночными. Конечный результат представляет собой дерево меньшего размера, разбиение которого на кластеры дает уровень 2. Процесс продолжается до тех пор, пока не останется один кластер. Стягивание представлено в виде топологического дерева, в котором каждый кластер имеет потомков – кластеры, из которых он состоит на предыдущем уровне. | ||
[[Файл:DynamicTrees_2.jpg]] | |||
Топологическое дерево (согласно алгоритму из [ ]). В левой части представлено исходное дерево и его многоуровневое разбиение; в правой части – соответствующее топологическое дерево. | Топологическое дерево (согласно алгоритму из [ ]). В левой части представлено исходное дерево и его многоуровневое разбиение; в правой части – соответствующее топологическое дерево. | ||
| Строка 37: | Строка 38: | ||
Недостаток топологических деревьев и RC-деревьев заключается в том, что лес, на основе которого они строятся, должен иметь вершины с ограниченными (константными) степенями, чтобы гарантировать время O(log n) на исполнение операции. И хотя ST-деревья не имеют подобного ограничения при сборе информации по путям, им необходимы ограниченные степени для сбора информации по деревьям. Ограничения по степени могут быть обойдены при помощи «растроения» исходного леса (замены вершины с высокой степенью серией вершин с низкими степенями [ ]), но при таком подходе возникают несколько специальных случаев. | Недостаток топологических деревьев и RC-деревьев заключается в том, что лес, на основе которого они строятся, должен иметь вершины с ограниченными (константными) степенями, чтобы гарантировать время O(log n) на исполнение операции. И хотя ST-деревья не имеют подобного ограничения при сборе информации по путям, им необходимы ограниченные степени для сбора информации по деревьям. Ограничения по степени могут быть обойдены при помощи «растроения» исходного леса (замены вершины с высокой степенью серией вершин с низкими степенями [ ]), но при таком подходе возникают несколько специальных случаев. | ||
«Верхушки деревьев», введенные Алструпом и коллегами [3, 4], не имеют подобных ограничений, в силу чего они позволяют охватить более общие случаи, чем все рассмотренные ранее структуры данных. Их кластеры также создаются при помощи процедуры стягивания дерева, однако они ведут себя скорее как дуги, чем как вершины. Кластер типа «сжатие» объединяет две дуги, имеющие общую вершину второй степени; кластер типа «обрезка» объединяет дугу, содержащую конечную точку первой степени, с дугой, дугой, смежной с ее второй конечной точкой. | «Верхушки деревьев», введенные Алструпом и коллегами [3, 4], не имеют подобных ограничений, в силу чего они позволяют охватить более общие случаи, чем все рассмотренные ранее структуры данных. Их кластеры также создаются при помощи процедуры стягивания дерева, однако они ведут себя скорее как дуги, чем как вершины. Кластер типа «сжатие» объединяет две дуги, имеющие общую вершину второй степени; кластер типа «обрезка» объединяет дугу, содержащую конечную точку первой степени, с дугой, дугой, смежной с ее второй конечной точкой. | ||
[[Файл:DynamicTrees_3.jpg]] | |||
Операции обрезки и сжатия в алгоритме, использующем верхушки деревьев [16] | Операции обрезки и сжатия в алгоритме, использующем верхушки деревьев [16] | ||