4501
правка
Динамические деревья: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) (Новая страница: «Ключевые слова и синонимы: алгоритм Слейтора-Тарьяна == Постановка задачи == Задача по…») |
Irina (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
== Основные результаты == | == Основные результаты == | ||
Очевидное решение задачи построения динамического дерева заключается в представлении леса явным образом. Однако оно оказывается неэффективным для запросов, относящихся к целым путям или деревьям, поскольку для выполнения таких запросов потребуется их полный обход. Чтобы получить время O (log n) на операцию, необходимо отображение каждого (возможно, несбалансированного) входного дерева на сбалансированное дерево, более подходящее для хранения информации о путях или деревьях неявным образом. Такое отображение можно выполнить при помощи одного из трех основных подходов: декомпозиция пути, стягивание дерева, линеаризация. | Очевидное решение задачи построения динамического дерева заключается в представлении леса явным образом. Однако оно оказывается неэффективным для запросов, относящихся к целым путям или деревьям, поскольку для выполнения таких запросов потребуется их полный обход. Чтобы получить время O (log n) на операцию, необходимо отображение каждого (возможно, несбалансированного) входного дерева на [[сбалансированное дерево]], более подходящее для хранения информации о путях или деревьях неявным образом. Такое отображение можно выполнить при помощи одного из трех основных подходов: [[декомпозиция пути]], [[стягивание дерева]], [[линеаризация]]. | ||
| Строка 60: | Строка 60: | ||
Структуры данных в виде динамических деревьев способны решать задачу динамической связности на ациклических графах, которая заключается в следующем: пусть даны две вершины, v и w; требуется определить, принадлежат ли они к одному и тому же дереву. Патраку и Демен [ ] доказали наличие нижней границы £?(log n) для этой задачи; это значение относится и к представленным структурам данных. | Структуры данных в виде динамических деревьев способны решать задачу динамической связности на ациклических графах, которая заключается в следующем: пусть даны две вершины, v и w; требуется определить, принадлежат ли они к одному и тому же дереву. Патраку и Демен [ ] доказали наличие нижней границы £?(log n) для этой задачи; это значение относится и к представленным структурам данных. | ||
== Применение == | == Применение == | ||
