PQ-дерево

PQ дерево — структура данных для представления группы перестановок. Это корневое планарное дерево. Висячие вершины в нем представляют переставляемые элементы. Остальные вершины имеют пометку либо $P$, либо $Q$. Вершины с пометкой $Q$ имеют по крайней мере 3 потомка, а вершины с пометкой $P$ имеют по крайней мере 2 потомка. В PQ дереве разрешается как угодно переставлять потомков вершины с пометкой $P$ и обращать порядок потомков вершины с пометкой $Q$.

PQ-дерево, описывающее вложенный список
[1 (2 3 4) 5]

PQ деревья используются для поиска перестановок, ограничения на которые становятся известны постепенно, одно за другим. Такие задачи возникают при воссоздании ДНК и проверке планарности графа.

Статьи

• Booth, Kellogg S. and Lueker, George S. (1976). «Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms». Journal of Computer and System Sciences 13: 335–379.

• Shih, Wei-Kuan and Hsu, Wen-Lian (1999). «A new planarity test». Theoretical Computer Science 223: 179–191. DOI:10.1016/S0304-3975(98)00120-0.