4501
правка
Динамические деревья: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
== Основные результаты == | == Основные результаты == | ||
Очевидное решение задачи построения динамического дерева заключается в представлении леса явным образом. Однако оно оказывается неэффективным для запросов, относящихся к целым путям или деревьям, поскольку для выполнения таких запросов потребуется их полный обход. Чтобы получить время O (log n) на операцию, необходимо отображение каждого (возможно, несбалансированного) входного дерева на [[сбалансированное дерево]], более подходящее для хранения информации о путях или деревьях неявным образом. Такое отображение можно выполнить при помощи одного из трех основных подходов: [[декомпозиция пути]], [[стягивание дерева]], [[линеаризация]]. | Очевидное решение задачи построения динамического дерева заключается в представлении леса явным образом. Однако оно оказывается неэффективным для запросов, относящихся к целым путям или деревьям, поскольку для выполнения таких запросов потребуется их полный обход. Чтобы получить время O(log n) на операцию, необходимо отображение каждого (возможно, несбалансированного) входного дерева на [[сбалансированное дерево]], более подходящее для хранения информации о путях или деревьях неявным образом. Такое отображение можно выполнить при помощи одного из трех основных подходов: [[декомпозиция пути]], [[стягивание дерева]], [[линеаризация]]. | ||
Декомпозиция пути | ''Декомпозиция пути'' | ||
Первая эффективная структура данных для динамического дерева была разработана Слейтором и Тарьяном; она известна как ST-дерево [13, 14], дерево со связыванием и отрезанием или просто динамическое дерево. Она была предназначена для представления корневых деревьев, однако пользователь может изменить корень дерева при помощи операции выворачивания (evert). Эта структура данных разбивает каждое входное дерево на пути с непересекающимися вершинами; каждый путь представляется в виде бинарного дерева поиска, в котором вершины появляются в симметричном порядке. Затем бинарные деревья соединяются в соответствии с тем, как пути соотносятся друг с другом в структуре леса. Точнее говоря, корень бинарного дерева становится средним потомком (в рамках структуры данных) родительского дерева (в лесу) самой верхней вершины соответствующего пути. В собственном бинарном дереве вершина может иметь не более двух потомков (левого и правого), однако при этом у нее может быть произвольное число средних потомков. Путь, включающий вершину (qlifcba на рисунке), должен быть открытым; он представлен в виде самого верхнего бинарного дерева. Все запросы, касающиеся путей, будут относиться к этому пути. Операция открытия (expose) может использоваться для того, чтобы сделать любую вершину частью открытого пути. | Первая эффективная структура данных для динамического дерева была разработана Слейтором и Тарьяном; она известна как ST-дерево [13, 14], дерево со связыванием и отрезанием или просто динамическое дерево. Она была предназначена для представления корневых деревьев, однако пользователь может изменить корень дерева при помощи операции выворачивания (evert). Эта структура данных разбивает каждое входное дерево на пути с непересекающимися вершинами; каждый путь представляется в виде бинарного дерева поиска, в котором вершины появляются в симметричном порядке. Затем бинарные деревья соединяются в соответствии с тем, как пути соотносятся друг с другом в структуре леса. Точнее говоря, корень бинарного дерева становится средним потомком (в рамках структуры данных) родительского дерева (в лесу) самой верхней вершины соответствующего пути. В собственном бинарном дереве вершина может иметь не более двух потомков (левого и правого), однако при этом у нее может быть произвольное число средних потомков. Путь, включающий вершину (qlifcba на рисунке), должен быть открытым; он представлен в виде самого верхнего бинарного дерева. Все запросы, касающиеся путей, будут относиться к этому пути. Операция открытия (expose) может использоваться для того, чтобы сделать любую вершину частью открытого пути. | ||
| Строка 22: | Строка 22: | ||
Стягивание дерева | ''Стягивание дерева'' | ||
В отличие от ST-деревьев, которые представляют входные деревья непосредственно, топологические деревья Фредериксона [6, 7, 8] представляют стягивание каждого дерева. Исходные вершины представляют собой 0 уровень стягивания. Уровень 1 представляет разбиение этих вершин на кластеры: вершина первой степени может комбинироваться только с ее соседом; вершины второй степени, смежные друг с другом, могут быть объединены в кластер; другие вершины остаются одиночными. Конечный результат представляет собой дерево меньшего размера, разбиение которого на кластеры дает уровень 2. Процесс продолжается до тех пор, пока не останется один кластер. Стягивание представлено в виде топологического дерева, в котором каждый кластер имеет потомков – кластеры, из которых он состоит на предыдущем уровне. См. рис. 2. | В отличие от ST-деревьев, которые представляют входные деревья непосредственно, топологические деревья Фредериксона [6, 7, 8] представляют стягивание каждого дерева. Исходные вершины представляют собой 0 уровень стягивания. Уровень 1 представляет разбиение этих вершин на кластеры: вершина первой степени может комбинироваться только с ее соседом; вершины второй степени, смежные друг с другом, могут быть объединены в кластер; другие вершины остаются одиночными. Конечный результат представляет собой дерево меньшего размера, разбиение которого на кластеры дает уровень 2. Процесс продолжается до тех пор, пока не останется один кластер. Стягивание представлено в виде топологического дерева, в котором каждый кластер имеет потомков – кластеры, из которых он состоит на предыдущем уровне. См. рис. 2. | ||
| Строка 52: | Строка 52: | ||
Линеаризация | ''Линеаризация'' | ||
ET-деревья, предложенные Хензингером и Кингом [10] и впоследствии несколько упрощенные Тарьяном [ ], используют иной подход к представлению динамических деревьев – линеаризацию. Она поддерживает эйлеров путь по каждому входному дереву: замкнутый путь, который проходит через каждую дугу дважды – по одному разу в обоих направлениях. Путь порождает линейный порядок на вершинах и ребрах и, следовательно, может быть представлен в виде сбалансированного бинарного дерева поиска. Связывание и отрезание дуг от леса соответствует присоединению и отщеплению затрагиваемых этими операциями бинарных деревьев и может быть выполнено за время O(log n). Линеаризация является, пожалуй, самым простым из трех подходов, однако у нее есть серьезный недостаток: поскольку каждая дуга встречается дважды, эта структура данных может собирать информацию только по деревьям, а не по путям. | ET-деревья, предложенные Хензингером и Кингом [10] и впоследствии несколько упрощенные Тарьяном [ ], используют иной подход к представлению динамических деревьев – линеаризацию. Она поддерживает эйлеров путь по каждому входному дереву: замкнутый путь, который проходит через каждую дугу дважды – по одному разу в обоих направлениях. Путь порождает линейный порядок на вершинах и ребрах и, следовательно, может быть представлен в виде сбалансированного бинарного дерева поиска. Связывание и отрезание дуг от леса соответствует присоединению и отщеплению затрагиваемых этими операциями бинарных деревьев и может быть выполнено за время O(log n). Линеаризация является, пожалуй, самым простым из трех подходов, однако у нее есть серьезный недостаток: поскольку каждая дуга встречается дважды, эта структура данных может собирать информацию только по деревьям, а не по путям. | ||