WikiSort.ru - Программирование

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

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

Статьи

• Booth, Kellogg S. and Lueker, George S. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms (англ.) // Journal of Computer and System Sciences. — 1976. — Vol. 13, no. 3. — P. 335–379. — DOI:10.1016/S0022-0000(76)80045-1.
• Shih, Wei-Kuan and Hsu, Wen-Lian. A new planarity test (англ.) // Theoretical Computer Science (journal). — 1999. — Vol. 223. — P. 179–191. — DOI:10.1016/S0304-3975(98)00120-0.
• Mehta, D.P. and Sahni, S. 32. PQ Trees, PC Trees, and Planar Graphs // Handbook of Data Structures and Applications. — Taylor & Francis, 2004. — ISBN 9781420035179.