Проблема предка уровня

В теории графов и теоретической информатике проблема предка уровня — это проблема предварительной обработки данного корневого дерева T в структуру данных , которая может определить предка данного узла на заданном расстоянии от корня дерева.

Точнее, пусть T — корневое дерево с n узлами, и пусть v — произвольный узел T . Запрос предка уровня LA( v , d ) запрашивает предка узла v на глубине d , где глубина узла v в дереве — это количество ребер на кратчайшем пути от корня дерева до узла v .Эту проблему можно решить за постоянное время для каждого запроса после алгоритма предварительной обработки, который принимает O( n ) и создает структуру данных, использующую O( n ) пространство для хранения. ^[1]^[2]

Наивные методы

Предок уровня ( v ,2) и путь от корня r до узла v .

Самый простой способ найти предка узла — подняться вверх по дереву к его корню. На пути к корню дерева можно посетить каждого предка узла и, следовательно, сообщить о нем. В этом случае дерево не нуждается в предварительной обработке, а время ответа на запрос равно O( h ), где «h» — высота дерева. Этот подход невозможен в ситуациях, когда дерево может иметь большую высоту и требуется обработка большого количества запросов.

Альтернативно, все возможные решения могут быть предварительно вычислены и сохранены в таблице. В этом случае на запросы можно ответить за O(1), но пространство и время предварительной обработки составляют O( n ²).

Простейшими запросами, на которые можно ответить за постоянное время без какой-либо предварительной обработки, являются LA( v , 0) и LA( v , глубина ( v )). В первом случае ответом всегда является корень дерева, а во втором случае ответом является сам узел v . Каждый из этих результатов занимает O(1).

Сохранение путей через дерево в косом двоичном списке произвольного доступа позволяет расширять дерево вниз на один шаг O(1) за раз, но теперь позволяет продолжить поиск за O(log( p )), где "p " — расстояние от v до требуемой глубины. Этот подход возможен, когда дерево особенно широкое или будет расширяться онлайн и поэтому не может быть эффективно предварительно обработано, поскольку время хранения и доступа определяется исключительно длиной пути. ^[3]

Алгоритм указателя перехода

Алгоритм указателя перехода ^[1] предварительно обрабатывает дерево за время O( n log n ) и отвечает на запросы предков уровня за время O(log n ). Алгоритм указателя перехода связывает до log n указателей с каждой вершиной дерева. Эти указатели называются указателями перехода, поскольку они перескакивают вверх по дереву к его корню. Для данного узла v дерева алгоритм сохраняет массив длины $l$ перемычки где $\ell =\lfloor \log _{2}(\operatorname {depth} (v))\rfloor$ . Я ^й элемент этого массива указывает на 2 ^яй предок v . Использование такой структуры данных помогает нам прыгнуть на полпути вверх по дереву от любого заданного узла. Когда алгоритму предлагается обработать запрос, мы неоднократно переходим вверх по дереву, используя эти указатели. Число переходов будет не более log n , поэтому на запросы можно будет ответить за log n времени.

Лестничный алгоритм

Лестничный алгоритм ^[1] основан на идее упрощения дерева до набора путей . Причиной этого является тот факт, что пути легче запрашивать, когда дело доходит до запросов к предкам уровня. Рассмотрим путь P, состоящий из n узлов с корнем в узле r. Мы можем сохранить путь в массиве размера n под названием Ladder и быстро ответить на запрос предка уровня LA(v, d), вернув Ladder[d], если глубина(v)≤d. Это займет O( 1 ). Однако это будет работать только в том случае, если данное дерево является путем. В противном случае нам нужно разложить его на пути. Это делается в два этапа: декомпозиция длинных путей и расширение длинных путей в лестницы.

Этап 1: разложение по длинному пути

Это рекурсивный метод, который разбивает заданное дерево на пути. Этот этап начинается с поиска самого длинного пути от корня к листу в дереве. Затем он удаляет этот путь, разрывая его связи с деревом, что разбивает оставшуюся часть дерева на поддеревья , а затем рекурсивно обрабатывает каждое поддерево. Каждый раз при декомпозиции пути создается массив , связанный с путем, который содержит элементы пути от корня до листа. Базовый случай этой рекурсии — когда дерево представляет собой путь, и в этом случае его удаление оставляет пустой граф. Каждая вершина v имеет уникальную лестницу, которая является лестницей, содержащей ее, и мы называем ее «лестницей v». Однако после этого этапа предварительной обработки на запросы невозможно ответить быстро. Фактически, чтобы ответить на запрос предка уровня, алгоритму необходимо переходить от одного пути к другому, пока он не достигнет корня, и может быть Θ( √ n на пути от листа к корню ) таких путей. Это приводит нас к алгоритму, который может предварительно обработать дерево за O( n ) времени и отвечает на запросы за O( √ n ). Чтобы достичь оптимального времени запроса, нам необходимо обработать результаты на втором этапе, описанном ниже.

Этап 2: расширение длинных дорожек до лестниц

На первом этапе алгоритма дерево разбивается на несколько непересекающихся путей. На втором этапе алгоритма каждый путь расширяется, поэтому полученные пути не будут взаимоисключающими. На первом этапе алгоритма каждому пути сопоставлен массив размером h' . Мы расширяем этот путь, добавляя непосредственных предков h вверху пути в том же массиве. Это увеличит каждый массив не более чем в два раза по сравнению с исходным размером, что приведет к 2n общему количеству узлов во всех лестницах . Обратите внимание, что количество цепочек не меняется и лестница каждого узла остается прежней. Хотя узел v теперь может быть указан в нескольких путях, его лестница — это та, которая была связана с v на первом этапе алгоритма. Эти два этапа могут быть обработаны за время O( n ), но время запроса еще не является постоянным. Рассмотрим запрос предка уровня на узле u высоты h. Поднявшись на вершину своей лестницы, вершины высотой не менее 2h вы достигнете . Обратите внимание, что все узлы имеют высоту не менее 1, и, следовательно, проделав это i раз, мы достигаем узла высотой не менее 2. ^я и поэтому нам нужно сделать это не более 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 . Таким образом, построив тур Эйлера и связанный с ниминформации о глубине задача сводится к запросу по массивам с именем find less (FS).Для массива A и допустимого индекса i FS( i , x ) возвращаетпервый индекс j > i такой, что A [ i ]< x (здесь мы используем x = d +1). Эффективное решение проблемы FS в целом сложно, но проще в частном случае, возникающем при использовании циклов Эйлера; в этом случае соседние элементы отличаются на ±1. Эта идея дает время запроса O(1) с алгоритмом предварительной обработки сложности O( n log n ). Время предварительной обработки сокращается до O( n ) за счет применения метода четырех русских .

См. также

Ссылки

^ Jump up to: ^а ^б ^с Бендер, Майкл А .; Фарах-Колтон, Мартин (2004). «Упрощенная проблема предков уровня» . Теор. Вычислить. Наука . 321 : 5–12. дои : 10.1016/j.tcs.2003.05.002 .
^ Jump up to: ^а ^б Беркман, Омер; Вишкин, Узи (апрель 1994 г.). «Нахождение уровней-предков в деревьях» . Дж. Компьютер. Сист. Наука . 2. 48 (2): 214–230. дои : 10.1016/S0022-0000(05)80002-9 .
^ Кметт, Эдвард. «O(log n) постоянный онлайн-вычисление наименьшего общего предка без предварительной обработки» . Проверено 8 мая 2013 г.
^ Бен-Амрам, Амир М. (2009). «Путь Эйлера к предкам статического уровня». arXiv : 0909.1030v1 [ cs.DS ].

[simplified-1] Jump up to: ^а ^б ^с Бендер, Майкл А .; Фарах-Колтон, Мартин (2004). «Упрощенная проблема предков уровня» . Теор. Вычислить. Наука . 321 : 5–12. дои : 10.1016/j.tcs.2003.05.002 .

[BV94-2] Jump up to: ^а ^б Беркман, Омер; Вишкин, Узи (апрель 1994 г.). «Нахождение уровней-предков в деревьях» . Дж. Компьютер. Сист. Наука . 2. 48 (2): 214–230. дои : 10.1016/S0022-0000(05)80002-9 .

[3] Кметт, Эдвард. «O(log n) постоянный онлайн-вычисление наименьшего общего предка без предварительной обработки» . Проверено 8 мая 2013 г.

[4] Бен-Амрам, Амир М. (2009). «Путь Эйлера к предкам статического уровня». arXiv : 0909.1030v1 [ cs.DS ].

[1]

[2]

[3]

[4]