Проблема предка уровня - Level ancestor problem

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Первый этап алгоритма разбивает дерево на несколько непересекающихся путей. На втором этапе алгоритма каждый путь расширяется, и поэтому результирующие пути не будут взаимоисключающими. На первом этапе алгоритма каждый путь связывается с массивом размера час' . Мы продлим этот путь, добавив час' непосредственные предки в верхней части пути в том же массиве. Это расширит каждый массив в два раза больше исходного размера, что приведет к 2n общее количество узлов во всех лестницах. Обратите внимание, что количество лестничных диаграмм не меняется, и лестничная диаграмма каждого узла остается прежней. Хотя узел v теперь может быть указан в нескольких путях, его лестница - это та, которая была связана с v на первом этапе алгоритма. Эти две стадии могут быть процессами за O (п), но время запроса еще не постоянное. Рассмотрим запрос предка уровня на узле u высоты h. Поднявшись к вершине лестницы u, вершина высотой не менее 2ч будет достигнуто. Заметьте, что все узлы имеют высоту не менее 1, и поэтому, сделав это i раз, мы достигаем узла высотой не менее 2^я и поэтому нам нужно сделать это самое большее logп раз. Это дает нам время запроса O (log п).

Этап 3: совмещение двух подходов

Оказывается, лестничный алгоритм сам по себе не справляется. Фактически алгоритм указателя перехода и лестничный алгоритм дополняют друг друга. Эти два алгоритма работают в противоположных направлениях: алгоритм указателя перехода выполняет экспоненциально убывающие переходы, а алгоритм лестничной диаграммы - экспоненциально возрастающие переходы. Комбинация двух алгоритмов может отвечать на запросы за O (1) время. Одиночный указатель перехода принимает любой запрос хотя бы на полпути вверх по дереву, после чего подъем только по одной лестнице ответит на запрос. Это приводит к O (п бревноп) время предварительной обработки и O (1) время запроса. Предварительная обработка может быть сокращена до O (п) время по приложению Метод четырех русских, в котором дерево сокращается до меньшего дерева с линейной предварительной обработкой и набором очень маленьких деревьев, которые достаточно малы, чтобы исчерпывающее перечисление всех деревьев и предварительная обработка этих деревьев по-прежнему составляли O (п) время. Деревья размером (бревно п) / 4 достаточно.

Решение Беркмана и Вишкина

Другое решение принадлежит Беркману и Вишкину.^[2]^[4] Это решение основано наЭйлер тур техника обработки деревьев. Главное наблюдение состоит в том, что LA (v,d) - первый узел глубиныd который появляется в туре Эйлера после последнего появления v. Таким образом, путем построения обхода Эйлера и связанной с ним информации по глубине проблема сводится к запросу массивов с именем найти меньше (ФС) .Для массива А, и действительный индекс я, FS (я,Икс) возвращает первый индекс j>я такой, что А[я]<Икс (здесь мы используем Икс=d+1). Эффективное решение проблемы ФС в целом сложно, но проще для частного случая, возникающего из туров Эйлера; в этом случае соседние элементы отличаются на ± 1. Эта идея дает время запроса O (1) с алгоритмом предварительной обработки сложности O (п бревноп). Время предварительной обработки увеличено до O (п) по заявлению Метод четырех русских.