PQ-дерево — структура данных для представления группы перестановок. Это корневое планарное дерево. Висячие вершины в нем представляют переставляемые элементы. Остальные вершины имеют пометку либо , либо . Вершины с пометкой имеют по крайней мере 3 потомка, а вершины с пометкой имеют по крайней мере 2 потомка. В PQ-дереве разрешается как угодно переставлять потомков вершины с пометкой и обращать порядок потомков вершины с пометкой .
Использование
PQ-деревья используются для поиска перестановок, ограничения на которые становятся известны постепенно, одно за другим. Такие задачи возникают при воссоздании ДНК и проверке планарности графа.
А именно, на каждом шаге добавляется ограничение, что все элементы из задаваемого подмножества должны следовать в перестановке последовательно. Соответствующая перестройка PQ-дерева выполняется за .
Пример Рассмотрим универсальное множество: . Изначально любая перестановка допустима, этому соответствует PQ-дерево: (A B C).
Добавим ограничение чтобы элементы из шли в перестановке последовательно. Допустимые перестановки: , , и . PQ-дерево имеет вид: ( (A B) C ).
Добавим следующее ограничение на последовательность элементов из \{ B, C \}. Останутся допустимые перестановки: , . PQ-дерево станет: [A B C].
Статьи
Approximate search for known gene clusters in new genomes using PQ-trees
Примечания
Категория:Деревья (структуры данных) Категория:Алгоритмы на графах