- PQ-дерево
-
PQ дерево — структура данных для представления группы перестановок. Это корневое планарное дерево. Висячие вершины в нем представляют переставляемые элементы. Остальные вершины имеют пометку либо , либо . Вершины с пометкой имеют по крайней мере 3 потомка, а вершины с пометкой имеют по крайней мере 2 потомка. В PQ дереве разрешается как угодно переставлять потомков вершины с пометкой и обращать порядок потомков вершины с пометкой .
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.
Дерево (структура данных) Двоичное дерево поиска · Дерево (теория графов) · Древовидная структура Двоичные деревья Двоичное дерево · T-дерево Самобалансирующиеся двоичные деревья АА-дерево · АВЛ-дерево · Красно-чёрное дерево · Расширяющееся дерево · Дерево со штрафами · Декартово дерево · Дерево Фибоначчи B-деревья B-дерево · 2-3-дерево · B+ дерево · B*-дерево · UB-дерево · 2-3-4 дерево · (a,b)-дерево · Танцующее дерево Префиксные деревья Суффиксное дерево · Radix tree · Ternary search tree Двоичное разбиение пространства k-мерное дерево · VP-дерево Недвоичные деревья Дерево квадрантов · Октодерево · Sparse Voxel Octree · Экспоненциальное дерево · PQ-дерево Разбиение пространства R-дерево · R+-дерево · R*-дерево · X-дерево · M-дерево · Дерево Фенвика · Дерево отрезков Другие деревья Куча · TTH · Finger tree · Metric tree · Cover tree · BK-tree · Doubly-chained tree · iDistance · Link-cut tree Алгоритмы Поиск в ширину · Поиск в глубину · DSW-алгоритм · Алгоритм связующего дерева Категории:- Деревья (структуры данных)
- Алгоритмы на графах
Wikimedia Foundation. 2010.