Дерево PQ
-
Дерево PQ
- Древовидная структура данных, представляющая перестановки для набора элементов
- Разработано Келлоггом С. Бутом и Джорджем С. Люкером в 1976 году
- Корневое дерево с маркировкой, где каждый элемент представлен конечным узлом
- Узел P имеет по крайней мере двух дочерних элементов, узел Q — по крайней мере трех
-
Представление перестановок
- Дочерние элементы узла P могут быть переупорядочены произвольно
- Дочерние элементы узла Q могут быть расположены в обратном порядке, но не переупорядочены иначе
- Дерево PQ представляет все упорядочения конечных узлов, достижимые с помощью этих операций
-
Применение деревьев PQ
- Решение задач, требующих найти порядок, удовлетворяющий ограничениям
- Ограничения включаются путем изменения древовидной структуры PQ
- Примеры применения: создание непрерывной карты из фрагментов ДНК, тестирование матрицы, распознавание интервальных графов, определение планарности графа
-
Примеры и обозначения
- Если все листья подключены к корневому узлу P, разрешены все возможные упорядочения
- Если все листья подключены к корневому узлу Q, допускается только один порядок и его обратное расположение
- Если узлы a, b, c соединены с P-узлом, допускается любое упорядочение, в котором a, b, c смежны
- Деревья PQ часто отмечаются вложенными списками в круглых скобках
-
Дерево PC
- Обобщение дерева PQ, разработанное Вэй-Куан Ши и Вэнь-Лянь Су
- Не имеет корней, узлы с меткой P могут быть переупорядочены произвольно, узлы с меткой C имеют фиксированный циклический порядок
- Дерево PC может представлять только наборы упорядочений, в которых любая циклическая перестановка также присутствует
- Дерево PQ на n элементах может быть смоделировано деревом PC на n + 1 элементе
- Операции с деревьями PC проще, чем с деревьями PQ для проверки планарности