Дерево качества обслуживания
Дерево PQ — это древовидная структура данных , представляющая семейство перестановок набора элементов, обнаруженная и названная Келлоггом С. Бутом и Джорджем С. Люкером в 1976 году. [1] Это корневое помеченное дерево, в котором каждый элемент представлен одним из листовых узлов , а каждый нелистовой узел помечен P или Q. Узел AP имеет как минимум два дочерних узла, а узел Q имеет как минимум три дочерних узла. .
Дерево PQ представляет свои перестановки посредством допустимого переупорядочения дочерних элементов его узлов. Дочерние узлы P-узла могут быть переупорядочены любым способом. Дочерние узлы Q-узла могут быть расположены в обратном порядке, но не могут быть переупорядочены иным образом. Дерево PQ представляет собой все упорядочения конечных узлов, которые могут быть достигнуты с помощью любой последовательности этих двух операций. Дерево PQ со многими узлами P и Q может представлять сложные подмножества множества всех возможных упорядочений. Однако не каждый набор упорядочений можно представить таким образом; например, если порядок представлен деревом PQ, обратный порядок также должен быть представлен тем же деревом.
Деревья PQ используются для решения задач, цель которых — найти порядок, удовлетворяющий различным ограничениям. В этих задачах ограничения на упорядочение включаются по одному путем изменения древовидной структуры PQ таким образом, чтобы она представляла только упорядочения, удовлетворяющие ограничению. Приложения деревьев PQ включают создание карты контигов из ДНК , фрагментов [2] проверка матрицы на свойство последовательных единиц, распознавание интервальных графиков и определение того, является ли график плоским . [1]
Примеры и обозначения [ править ]
[1 (2 3 4) 5]
Если все листья дерева 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.
Деревья ПК [ править ]
Дерево PC , разработанное Вэй-Куаном Ши и Вэнь-Лянь Сюем , является более поздним обобщением дерева PQ. Как и дерево PQ, оно представляет собой перестановки путем изменения порядка узлов в дереве, при этом элементы представлены на листьях дерева. В отличие от дерева PQ, дерево ПК не имеет корней. Узлы, соседние с любым нелистовым узлом, помеченным P, могут быть переупорядочены произвольно, как в дереве PQ, в то время как узлы, смежные с любым нелистовым узлом, помеченным C, имеют фиксированный циклический порядок и могут быть переупорядочены только путем изменения этого порядка. Таким образом, дерево ПК может представлять только наборы упорядочений, в которых любая циклическая перестановка или изменение порядка в наборе также находится в наборе. Однако дерево PQ на n элементах может быть смоделировано деревом PC на n + 1 элементе, где дополнительный элемент служит корнем дерева PC. Операции со структурой данных, необходимые для выполнения алгоритма проверки планарности на деревьях PC, несколько проще, чем соответствующие операции на деревьях PQ. [3]
См. также [ править ]
Ссылки [ править ]
- ^ Перейти обратно: а б Бут, Келлог С.; Люкер, Джордж С. (1976). «Проверка свойства последовательных единиц, интервальных графов и планарности графов с использованием алгоритмов PQ-дерева» . Журнал компьютерных и системных наук . 13 (3): 335–379. дои : 10.1016/S0022-0000(76)80045-1 .
- ^ Карп, Ричард М. (1993). «Картирование генома: некоторые комбинаторные проблемы, возникающие в молекулярной биологии». В Косараджу, С. Рао ; Джонсон, Дэвид С .; Аггарвал, Алок (ред.). Материалы двадцать пятого ежегодного симпозиума ACM по теории вычислений, 16–18 мая 1993 г., Сан-Диего, Калифорния, США . Ассоциация вычислительной техники. стр. 278–285. дои : 10.1145/167088.167170 .
- ^ Ши, Вэй-Куан; Сюй, Вэнь-Лянь (1999). «Новый тест на планарность» (PDF) . Теоретическая информатика . 223 (1–2): 179–191. дои : 10.1016/S0304-3975(98)00120-0 .