Введение

PQ-дерево — это древовидная структура данных, представляющая семейство перестановок на множестве элементов, разработанная и названная Келлоггом С. Бутом и Джорджем С. Луекером в 1976 году. Это корневое, маркированное дерево, в котором каждый элемент представлен одним из листовых узлов, а каждый нелистовой узел маркирован P или Q. Узел P имеет как минимум два дочерних узла, а узел Q — как минимум три. PQ-дерево представляет свои перестановки посредством допустимых упорядочиваний дочерних узлов своих узлов. Дочерние узлы узла P могут быть переупорядочены любым способом. Дочерние узлы узла Q могут быть расположены в обратном порядке, но не могут быть переупорядочены иным образом. PQ-дерево представляет все возможные упорядочения листовых узлов, которые могут быть достигнуты любой последовательностью этих двух операций. PQ-дерево с большим количеством узлов P и Q может представлять сложные подмножества множества всех возможных упорядочений. Однако не любое множество упорядочений может быть представлено таким образом; например, если перестановка представлена PQ-деревом, то и обратная перестановка также должна быть представлена тем же деревом. PQ-деревья используются для решения задач, в которых необходимо найти упорядочение, удовлетворяющее различным ограничениям. В этих задачах ограничения на упорядочение вводятся по одному, путем модификации структуры PQ-дерева таким образом, чтобы оно представляло только упорядочения, удовлетворяющие данному ограничению. Области применения PQ-деревьев включают создание контиг-карты из фрагментов ДНК, проверку матрицы на свойство последовательных единиц, распознавание интервальных графов и определение, является ли граф планарным.

Примеры и обозначение

Если все листья дерева PQ соединены непосредственно с корневым узлом P, то допускаются все возможные порядки. Если все листья соединены непосредственно с корневым узлом Q, то допускается только один порядок и порядок, обратный ему. Если узлы a, b, c соединены с узлом P, который соединен с корневым узлом P, а все остальные листья соединены непосредственно с корнем, то допускается любой порядок, при котором a, b, c идут подряд. Когда графическое представление недоступно, деревья PQ часто записываются с использованием вложенных списков в скобках. Каждая совпадающая пара квадратных скобок представляет узел Q, а каждая совпадающая пара круглых скобок – узел P. Листья – это элементы списков, не заключенные в скобки. Изображение слева представлено в этой нотации как [1 (2 3 4) 5]. Это дерево PQ представляет следующие двенадцать перестановок множества {1, 2, 3, 4, 5}: 12345, 12435, 13245, 13425, 14235, 14325, 52341, 52431, 53241, 53421, 54231, 54321.

ПЦ деревья

Древо ПК, разработанное Вэй Куан Ши и Вэнь Лян Хсу, является более поздней обобщенной версией дерева PQ. Как и дерево PQ, оно представляет перестановки посредством переупорядочивания узлов в дереве, при этом элементы располагаются на листьях дерева. В отличие от дерева PQ, дерево ПК не имеет корня. Узлы, смежные с любым нелистовым узлом, помеченным буквой P, могут быть переупорядочены произвольно, как и в дереве PQ, тогда как узлы, смежные с любым нелистовым узлом, помеченным буквой C, имеют фиксированный циклический порядок и могут быть переупорядочены только путем обращения этого порядка. Таким образом, дерево ПК может представлять только множества упорядочений, в которых любая циклическая перестановка или обращение упорядочения из этого множества также содержится в нем. Однако дерево PQ на n элементах может быть смоделировано деревом ПК на n + 1 элементах, где дополнительный элемент служит для создания корня дерева ПК. Операции над структурой данных, необходимые для выполнения алгоритма проверки планарности на деревьях ПК, несколько проще, чем соответствующие операции на деревьях PQ.