В теории графов и теоретической информатике , то проблема уровня предка является проблемой предварительной обработки данного корневого дерева T в структуру данных , которые могут определить предок данного узла на заданное расстоянии от корня дерева.
Точнее, пусть Т быть корневым деревом с п узлами, и пусть v произвольный узел Т . Запрос уровня предка LA ( v , d ) запрашивает предка узла v на глубине d , где глубина узла v в дереве - это количество ребер на кратчайшем пути от корня дерева до узла v . Эту проблему можно решить за постоянное время на запрос после алгоритма предварительной обработки, который занимает O ( n ) и строит структуру данных, которая использует O ( n ) дискового пространства. [1] [2]
Наивные методы
Самый простой способ найти предка узла по уровню - это подняться по дереву к корню дерева. На пути к корню дерева можно посетить каждого предка узла и, следовательно, сообщить о нем. В этом случае дерево не требует предварительной обработки, и время ответа на запрос составляет O ( h ), где «h» - высота дерева. Этот подход невозможен в ситуациях, когда дерево может иметь большую высоту и требуется обрабатывать большое количество запросов.
В качестве альтернативы все возможные решения можно предварительно вычислить и сохранить в таблице. В этом случае на запросы можно ответить за O (1), но пространство и время предварительной обработки равны O ( n 2 ).
Простейшие запросы, на которые можно ответить за постоянное время без какой-либо предварительной обработки, - это LA ( v , 0) и LA ( v , depth ( v )). В первом случае ответом всегда является корень дерева, а во втором - сам узел v . Каждый из этих результатов занимает O (1).
Сохранение путей через дерево в скошенном двоичном списке произвольного доступа позволяет расширять дерево вниз на один шаг O (1) за раз, но теперь позволяет продолжить поиск за O (log ( p )), где "p "- это расстояние от v до требуемой глубины. Этот подход возможен, когда дерево особенно велико или будет расширяться в интерактивном режиме и поэтому не может быть эффективно предварительно обработано, поскольку время хранения и доступа определяется исключительно длиной пути. [3]
Алгоритм указателя перехода
Алгоритм указателя перехода [1] предварительно обрабатывает дерево за время O ( n log n ) и отвечает на запросы предка уровня за время O (log n ). Алгоритм указателя перехода связывает до log n указателей с каждой вершиной дерева. Эти указатели называются указателями перехода, потому что они прыгают вверх по дереву к корню дерева. Для данного узла v дерева алгоритм хранит массив длины перемычки, где . Я й элемент этого массива указывает на 2 я й предок V . Использование такой структуры данных помогает нам перепрыгнуть на полпути вверх по дереву от любого заданного узла. Когда алгоритму предлагается обработать запрос, мы многократно прыгаем вверх по дереву, используя эти указатели. Количество переходов будет не более log n, поэтому на запросы можно будет ответить за log n времени.
Лестничный алгоритм
Релейный алгоритм [1] основан на идее упрощения дерева до набора путей . Причина этого заключается в том, что пути легче запрашивать, когда дело доходит до запросов предков уровня. Рассмотрим путь P, состоящий из n узлов с корнем в узле r. Мы можем сохранить путь в массиве размера n под названием Ladder, и мы можем быстро ответить на запрос предка уровня LA (v, d), вернув Ladder [d], если depth (v) ≤d. Это займет O ( 1 ). Однако это будет работать только в том случае, если данное дерево является путем. В противном случае нам нужно разложить его на пути. Это делается в два этапа: разложение длинных путей и преобразование длинных путей в лестницы.
Этап 1: разложение по длинному пути
Это рекурсивный метод, который разбивает заданное дерево на пути. Этот этап начинается с поиска самого длинного пути от корня к листу в дереве. Затем он удаляет этот путь, разрывая его связи с деревом, что разбивает оставшуюся часть дерева на поддеревья, а затем рекурсивно обрабатывает каждое поддерево. Каждый раз при декомпозиции пути создается массив , связанный с путем, который содержит элементы на пути от корня к листу. Базовый случай этой рекурсии - это когда дерево является путем, и в этом случае при его удалении остается пустой граф. Каждая вершина v имеет уникальную лестницу, которая представляет собой лестницу, содержащую ее, и мы называем ее «лестницей v». Однако после этого этапа предварительной обработки на запросы нельзя быстро ответить. Фактически, чтобы ответить на запрос предка уровня, алгоритм должен перейти с одного пути на другой, пока не достигнет корня, и на пути от листа к корню может быть ( √ n ) таких путей. Это приводит нас к алгоритму, который может предварительно обработать дерево за O ( n ) раз и ответить на запросы за O ( √ n ). Чтобы достичь оптимального времени запроса, нам необходимо обработать результаты на втором этапе, описанном ниже.
Этап 2: продолжение длинных дорожек в лестницы
Первый этап алгоритма разбивает дерево на несколько непересекающихся путей. На втором этапе алгоритма каждый путь расширяется, и поэтому результирующие пути не будут взаимоисключающими. На первом этапе алгоритма каждый путь связывается с массивом размера h ' . Мы расширяем этот путь, добавляя непосредственных предков h ' вверху пути в том же массиве. Это расширит каждый массив в два раза больше исходного размера, что приведет к общему количеству узлов во всех лестничных диаграммах 2n . Обратите внимание, что количество лестничных диаграмм не изменяется, и лестничная диаграмма каждого узла остается прежней. Хотя узел v теперь может быть указан в нескольких путях, его лестница - это та, которая была связана с v на первом этапе алгоритма. Эти два этапа могут быть обработаны за O ( n ), но время запроса еще не является постоянным. Рассмотрим запрос предка уровня на узле u высоты h. Поднявшись на вершину лестницы u, будет достигнута вершина высотой не менее 2h . Обратите внимание, что все узлы имеют высоту не менее 1, и поэтому после выполнения этого i раз мы достигаем узла высотой не менее 2 i, и поэтому нам нужно сделать это не более log n раз. Это дает нам время запроса O (log n ).
Этап 3: совмещение двух подходов
Оказывается, лестничный алгоритм сам по себе не помогает. Фактически алгоритм указателя перехода и лестничный алгоритм дополняют друг друга. Два алгоритма работают в противоположных направлениях: алгоритм указателя перехода выполняет экспоненциально уменьшающиеся переходы, а алгоритм лестничной диаграммы - экспоненциально возрастающие переходы. Комбинация двух алгоритмов может отвечать на запросы за время O ( 1 ). Одиночный указатель перехода берет любой запрос, по крайней мере, на полпути вверх по дереву, после чего подъем только по одной лестнице ответит на запрос. Это приводит к времени предварительной обработки O ( n log n ) и времени запроса O ( 1 ). Предварительная обработка может быть дополнительно сокращена до времени O ( n ) с помощью применения метода четырех русских , в котором дерево сокращается до меньшего дерева с линейной предварительной обработкой и набором очень маленьких деревьев, которые достаточно малы. что для исчерпывающего перебора всех деревьев и предварительной обработки этих деревьев требуется время O ( n ). Деревья размером (log n ) / 4 достаточно.
Решение Беркмана и Вишкина
Другое решение принадлежит Беркману и Вишкину. [2] [4] Это решение основано на технике тура Эйлера для обработки деревьев. Главное наблюдение состоит в том, что LA ( v , d ) - это первый узел глубины d, который появляется в эйлеровом туре после последнего появления v . Таким образом, путем построения обхода Эйлера и связанной с ним информации о глубине проблема сводится к запросу по массивам, называемому поиск меньшего размера (FS). Для массива A и допустимого индекса i функция FS ( i , x ) возвращает первый индекс j > i, такой что A [ i ] < x (здесь мы используем x = d +1). Эффективное решение проблемы ФС в общем случае сложно, но проще для частного случая, возникающего из туров Эйлера; в этом случае соседние элементы отличаются на ± 1. Эта идея дает время запроса O (1) с алгоритмом предварительной обработки со сложностью O ( n log n ). Время предварительной обработки увеличено до O ( n ) за счет применения метода четырех русских .
Смотрите также
Рекомендации
- ^ a b c Бендер, Майкл А .; Фарач-Колтон, Мартин (2004). «Упрощенная проблема предков уровня». Теор. Comput. Sci . 321 : 5–12. DOI : 10.1016 / j.tcs.2003.05.002 .
- ^ а б Беркман, Омер; Вишкин, Узи (апрель 1994 г.). «Поиск предков уровней в деревьях». J. Comput. Syst. Sci . 2. 48 (2): 214–230. DOI : 10.1016 / S0022-0000 (05) 80002-9 .
- ^ Кметт, Эдвард. «O (log n) постоянное онлайн-вычисление наименьшего общего предка без предварительной обработки» . Проверено 8 мая 2013 года .
- ^ Бен-Амрам, Амир М. (2009). «Путь Эйлера к статическим предкам уровня». arXiv : 0909.1030v1 [ cs.DS ].