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

Перейти к навигации Перейти к поиску
(Новая страница: «Ключевые слова и синонимы: алгоритм Слейтора-Тарьяна == Постановка задачи == Задача по…»)
 
Строка 8: Строка 8:
== Основные результаты ==
== Основные результаты ==


Очевидное решение задачи построения динамического дерева заключается в представлении леса явным образом. Однако оно оказывается неэффективным для запросов, относящихся к целым путям или деревьям, поскольку для выполнения таких запросов потребуется их полный обход. Чтобы получить время O (log n) на операцию, необходимо отображение каждого (возможно, несбалансированного) входного дерева на сбалансированное дерево, более подходящее для хранения информации о путях или деревьях неявным образом. Такое отображение можно выполнить при помощи одного из трех основных подходов: декомпозиция пути, стягивание дерева, линеаризация.
Очевидное решение задачи построения динамического дерева заключается в представлении леса явным образом. Однако оно оказывается неэффективным для запросов, относящихся к целым путям или деревьям, поскольку для выполнения таких запросов потребуется их полный обход. Чтобы получить время O (log n) на операцию, необходимо отображение каждого (возможно, несбалансированного) входного дерева на [[сбалансированное дерево]], более подходящее для хранения информации о путях или деревьях неявным образом. Такое отображение можно выполнить при помощи одного из трех основных подходов: [[декомпозиция пути]], [[стягивание дерева]], [[линеаризация]].




Строка 60: Строка 60:


Структуры данных в виде динамических деревьев способны решать задачу динамической связности на ациклических графах, которая заключается в следующем: пусть даны две вершины, v и w; требуется определить, принадлежат ли они к одному и тому же дереву. Патраку и Демен [ ] доказали наличие нижней границы £?(log n) для этой задачи; это значение относится и к представленным структурам данных.
Структуры данных в виде динамических деревьев способны решать задачу динамической связности на ациклических графах, которая заключается в следующем: пусть даны две вершины, v и w; требуется определить, принадлежат ли они к одному и тому же дереву. Патраку и Демен [ ] доказали наличие нижней границы £?(log n) для этой задачи; это значение относится и к представленным структурам данных.


== Применение ==
== Применение ==
4551

правка

Навигация