4551
правка
Динамические деревья: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 47: | Строка 47: | ||
Верхушки деревьев сконструированы таким образом, чтобы полностью скрывать от пользователя внутренние операции над структурой данных. Пользователь задает только то, какой фрагмент информации в каком кластере хранится, а также – при помощи косвенно вызываемых функций – как обновлять информацию после создания или разрушения кластера в ходе изменения дерева. Если операции определены должным образом, то приложения, использующие верхушки деревьев, совершенно независимы от того, как в действительности реализована структура данных – иначе говоря, от порядка, в котором выполняются операции обрезки и сжатия. | Верхушки деревьев сконструированы таким образом, чтобы полностью скрывать от пользователя внутренние операции над структурой данных. Пользователь задает только то, какой фрагмент информации в каком кластере хранится, а также – при помощи косвенно вызываемых функций – как обновлять информацию после создания или разрушения кластера в ходе изменения дерева. Если операции определены должным образом, то приложения, использующие верхушки деревьев, совершенно независимы от того, как в действительности реализована структура данных – иначе говоря, от порядка, в котором выполняются операции обрезки и сжатия. | ||
Фактически верхушки деревьев были изначально предложены не как самостоятельные структуры данных, но как интерфейс над топологическими деревьями. Однако по соображениям эффективности хотелось бы иметь более прямую реализацию. Холм, Тарьян, Торуп и Вернек предложили концептуально простой автономный алгоритм обновления верхушки дерева после выполнения операции связывания или отрезания за время O(log n) в наихудшем случае [17]. Кроме того, Тарьян и Вернек предложили самонастраивающиеся верхушки деревьев [16] – более эффективную реализацию верхушек деревьев, основанную на декомпозиции путей: она разбивает исходный лес на пути с непересекающимися дугами, представляет эти пути в виде косых деревьев, | Фактически верхушки деревьев были изначально предложены не как самостоятельные структуры данных, но как интерфейс над топологическими деревьями. Однако по соображениям эффективности хотелось бы иметь более прямую реализацию. Холм, Тарьян, Торуп и Вернек предложили концептуально простой автономный алгоритм обновления верхушки дерева после выполнения операции связывания или отрезания за время O(log n) в наихудшем случае [17]. Кроме того, Тарьян и Вернек предложили самонастраивающиеся верхушки деревьев [16] – более эффективную реализацию верхушек деревьев, основанную на декомпозиции путей: она разбивает исходный лес на пути с непересекающимися дугами, представляет эти пути в виде косых деревьев, а затем соответствующим образом соединяет эти деревья. Внутренняя структура данных очень похожа на ST-дерево, однако пути в ней имеют непересекающиеся дуги, а не вершины, а шаг «растроения» встроен в саму структуру данных. Однако пользователю видны только операции обрезки и сжатия, характеризующие стягивание дерева. | ||
а затем соответствующим образом соединяет эти деревья. Внутренняя структура данных очень похожа на ST-дерево, однако пути в ней имеют непересекающиеся дуги, а не вершины, а шаг «растроения» встроен в саму структуру данных. Однако пользователю видны только операции обрезки и сжатия, характеризующие стягивание дерева. | |||
''Линеаризация'' | ''Линеаризация'' | ||
ET-деревья, предложенные Хензингером и Кингом [10] и впоследствии несколько упрощенные Тарьяном [ ], используют иной подход к представлению динамических деревьев – линеаризацию. Она поддерживает эйлеров путь по каждому входному дереву: замкнутый путь, который проходит через каждую дугу дважды – по одному разу в обоих направлениях. Путь порождает линейный порядок на вершинах и ребрах и, следовательно, может быть представлен в виде сбалансированного бинарного дерева поиска. Связывание и отрезание дуг от леса соответствует присоединению и отщеплению затрагиваемых этими операциями бинарных деревьев и может быть выполнено за время O(log n). Линеаризация является, пожалуй, самым простым из трех подходов, однако у нее есть серьезный недостаток: поскольку каждая дуга встречается дважды, эта структура данных может собирать информацию только по деревьям, а не по путям. | ET-деревья, предложенные Хензингером и Кингом [10] и впоследствии несколько упрощенные Тарьяном [15], используют иной подход к представлению динамических деревьев – линеаризацию. Она поддерживает [[эйлеров путь]] по каждому входному дереву: замкнутый путь, который проходит через каждую дугу дважды – по одному разу в обоих направлениях. Путь порождает линейный порядок на вершинах и ребрах и, следовательно, может быть представлен в виде сбалансированного бинарного дерева поиска. Связывание и отрезание дуг от леса соответствует присоединению и отщеплению затрагиваемых этими операциями бинарных деревьев и может быть выполнено за время O(log n). Линеаризация является, пожалуй, самым простым из трех подходов, однако у нее есть серьезный недостаток: поскольку каждая дуга встречается дважды, эта структура данных может собирать информацию только по деревьям, а не по путям. | ||
Нижние границы | Нижние границы | ||
Структуры данных в виде динамических деревьев способны решать задачу динамической связности на ациклических графах, которая заключается в следующем: пусть даны две вершины, v и w; требуется определить, принадлежат ли они к одному и тому же дереву. Патраку и Демен [ ] доказали наличие нижней границы | Структуры данных в виде динамических деревьев способны решать задачу динамической связности на ациклических графах, которая заключается в следующем: пусть даны две вершины, v и w; требуется определить, принадлежат ли они к одному и тому же дереву. Патраку и Демен [12] доказали наличие нижней границы <math>\Omega (log n)</math> для этой задачи; это значение относится и к представленным структурам данных. | ||
== Применение == | == Применение == | ||
