WikiDer > Расстояние вращения

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

Расстояние вращения было впервые определено Карлом Чуликом II и Дерик Вуд в 1982 г.^[1] Каждые два п-узловые бинарные деревья имеют максимальное расстояние вращения 2п − 6, и некоторые пары деревьев имеют именно это расстояние. В вычислительная сложность вычисления расстояния вращения неизвестно.^[2]

Определение

Вращение дерева

А двоичное дерево представляет собой структуру, состоящую из набора узлов, один из которых обозначен как корневой узел, в котором каждый оставшийся узел является либо левый ребенок или же правильный ребенок какого-то другого узла, его родитель, и в котором следование родительским ссылкам от любого узла в конечном итоге приводит к корневому узлу. (В некоторых источниках описанные здесь узлы называются «внутренними узлами», существует другой набор узлов, называемых «внешними узлами», каждый внутренний узел является требуется ровно два дочерних элемента, и каждый внешний узел должен иметь ноль дочерних узлов.^[1] Описанную здесь версию можно получить, удалив все внешние узлы из такого дерева.)

Для любого узла Икс в дереве есть поддерево такой же формы, укорененные в Икс и состоящий из всех узлов, которые могут достичь Икс по родительским ссылкам. Каждое двоичное дерево имеет порядок узлов слева направо, его обход по порядку, полученный путем рекурсивного обхода левого поддерева (поддерево в левом дочернем от корня, если такой дочерний элемент существует), затем перечисления самого корня, а затем рекурсивного обхода правого поддерева. двоичное дерево поиска, каждый узел связан с ключом поиска, и требуется, чтобы порядок слева направо соответствовал порядку ключей.^[2]

А вращение деревьев это операция, которая изменяет структуру двоичного дерева без изменения его порядка слева направо. Несколько самобалансирующееся двоичное дерево поиска структуры данных использовать эти вращения как примитивную операцию в своих алгоритмах перебалансировки. Вращение работает на двух узлах Икс и у, куда Икс является родителем у, и реструктурирует дерево, делая у быть родителем Икс и заняв место Икс в дереве. Чтобы освободить одну из дочерних ссылок у и освободить место для связи Икс как ребенок у, для этой операции также может потребоваться переместить одного из дочерних элементов у стать ребенком Икс.Есть два варианта этой операции: правое вращение в котором у начинается как левый ребенок Икс и Икс заканчивается как правильный ребенок у, а левое вращение в котором у начинается как правильный ребенок Икс и Икс заканчивается как левый дочерний элемент у.^[2]

Любые два дерева, которые имеют одинаковую последовательность узлов слева направо, могут быть преобразованы друг в друга с помощью последовательности вращений. Расстояние поворота между двумя деревьями - это количество поворотов в кратчайшей возможной последовательности поворотов, которая выполняет это преобразование. Его также можно описать как кратчайший путь расстояние в график вращения, граф, который имеет вершину для каждого двоичного дерева в заданной последовательности узлов слева направо и ребро для каждого поворота между двумя деревьями.^[2] Этот граф вращения является в точности графом вершин и ребер ассоциэдр.^[3]

Эквивалентность зеркальному расстоянию

Графы переворота пятиугольника и шестиугольника, соответствующие поворотам бинарных деревьев с тремя и четырьмя узлами

Учитывая семью триангуляции некоторого геометрического объекта, кувырок - это операция преобразования одной триангуляции в другую путем удаления ребра между двумя треугольниками и добавления противоположной диагонали к полученному четырехугольнику. Расстояние переворота между двумя триангуляциями - это минимальное количество переворотов, необходимое для преобразования одной триангуляции в другую. Его также можно описать как расстояние кратчайшего пути в перевернуть график, граф, имеющий вершину для каждой триангуляции и ребро для каждого перехода между двумя триангуляциями. Таким образом можно определить расстояния переворота и переворота для нескольких различных видов триангуляции, включая триангуляции наборов точек в Евклидова плоскость, триангуляции полигоны, и триангуляции абстрактных коллекторы.

Существует взаимно однозначное соответствие между триангуляциями данного выпуклый многоугольник, с обозначенным корневым ребром и бинарными деревьями, триангулирующими п-сторонние многоугольники в бинарные деревья с п − 2 узлы. В этом соответствии каждый треугольник триангуляции соответствует узлу в двоичном дереве. Корневой узел - это треугольник, имеющий обозначенное корневое ребро в качестве одной из его сторон, и два узла связаны как родительский и дочерний в дереве, когда соответствующие треугольники имеют общую диагональ в триангуляции. При этом соответствии вращения в двоичных деревьях точно соответствуют переворачивается в соответствующих триангуляциях. Следовательно, расстояние вращения на (п − 2)-узловые деревья точно соответствуют расстоянию переворота на триангуляции п-сторонние выпуклые многоугольники.

Максимальное значение

Чулик и Вуд (1982) Определите «правый стержень» двоичного дерева как путь, полученный, начиная с корня и следуя правым дочерним ссылкам до достижения узла, у которого нет правого дочернего элемента. Если у дерева есть свойство, что не все узлы принадлежат правому стержню, всегда существует правое вращение, которое увеличивает длину правого стержня. Ведь в этом случае существует хотя бы один узел Икс на правом позвоночнике, у которого есть левый ребенок у это не на правом позвоночнике. Выполнение правого вращения на Икс и у добавляет у к правому позвоночнику, не удаляя из него другие узлы. За счет многократного увеличения длины правого позвоночника любой п-нодерево может быть преобразовано в уникальное дерево с тем же порядком узлов, в котором все узлы принадлежат правому корешку, максимум в п − 1 шаги. Для любых двух деревьев с одинаковым порядком узлов можно преобразовать одно в другое, преобразовав первое дерево в дерево со всеми узлами на правом стержне, а затем изменив то же преобразование второго дерева в сумме не более 2п − 2 шаги. Следовательно, как Чулик и Вуд (1982) доказано, расстояние вращения между любыми двумя деревьями не превосходит 2п − 2.^[1]

Рассматривая проблему в терминах переворотов выпуклых многоугольников вместо поворотов деревьев, Слейтор, Тарджан и Терстон (1988) смогли показать, что расстояние вращения не превышает 2п − 6. В терминах триангуляции выпуклых многоугольников правый спайн - это последовательность треугольников, инцидентных правому концу корневого ребра, а дерево, в котором все вершины лежат на спине, соответствует веерная триангуляция для этой вершины. Основная идея их улучшения состоит в том, чтобы попытаться перевернуть обе заданные триангуляции в веерную триангуляцию для любой вершины, а не только для правой конечной точки корневого ребра. Невозможно, чтобы все эти варианты одновременно давали наихудшее расстояние. п − 1 от каждой начальной триангуляции, что дает улучшение.^[2]

Слейтор, Тарджан и Терстон (1988) также использовал геометрический аргумент, чтобы показать, что для бесконечного числа значений п, максимальное расстояние поворота точно 2п − 6. Они снова используют интерпретацию проблемы в терминах переворотов триангуляций выпуклых многоугольников, и они интерпретируют начальную и конечную триангуляцию как верхнюю и нижнюю грани треугольника. выпуклый многогранник причем сам выпуклый многоугольник интерпретируется как Гамильтонова схема в этом многограннике. Согласно этой интерпретации, последовательность переворотов от одной триангуляции к другой может быть преобразована в набор тетраэдры которые триангулируют данный трехмерный многогранник. Они находят семейство многогранников со свойством, что (в трехмерном гиперболическая геометрия) многогранники имеют большой объем, но все тетраэдры внутри них имеют гораздо меньший объем, что означает, что для любой триангуляции требуется много тетраэдров. Бинарные деревья, полученные переводом верхних и нижних наборов граней этих многогранников обратно в деревья, имеют большое расстояние вращения, по крайней мере 2п − 6.^[2]

Впоследствии Пурнин (2014) предоставил доказательство того, что для всех п ≥ 11, максимальное расстояние поворота точно 2п − 6. Доказательство Пурнина комбинаторно и избегает использования гиперболической геометрии.^[3]

Вычислительная сложность

Нерешенная проблема в математике: Какова сложность вычисления расстояния вращения между двумя деревьями? (больше нерешенных задач по математике)

Помимо определения расстояния вращения, Чулик и Вуд (1982) попросил вычислительная сложность вычисления расстояния вращения между двумя заданными деревьями. Существование коротких последовательностей вращения между любыми двумя деревьями означает, что проверка того, не превышает ли расстояние поворота k принадлежит к класс сложности НП, но это не известно НП-полный, и не разрешима в полиномиальное время.

Расстояние поворота между любыми двумя деревьями может быть ограничено снизу, в эквивалентном представлении триангуляции многоугольников, числом диагоналей, которые необходимо удалить из одной триангуляции и заменить другими диагоналями для создания другой триангуляции. Ее также можно ограничить сверху вдвое большим числом, разбив задачу на подзадачи по любым диагоналям, общим для обеих триангуляций, а затем применив метод Чулик и Вуд (1982) к каждой подзадаче. Этот метод обеспечивает алгоритм аппроксимации для проблемы с коэффициент аппроксимации из двух.^[4] Подобный подход разбиения на подзадачи по общим диагоналям приводит к управляемый с фиксированными параметрами алгоритм для точного вычисления расстояния вращения.^[5][6]

Определение сложности точного вычисления расстояния вращения без параметризации остается нерешенным, и лучшие алгоритмы, известные в настоящее время для решения этой проблемы, работают в экспоненциальное время.^[7]

Рекомендации