Árbol PQ

Un árbol PQ es una estructura de datos basada en árboles que representa una familia de permutaciones en un conjunto de elementos, descubierto y nombrado por Kellogg S. Booth y George S. Lueker en 1976. ^{[ 1 ]} Es un árbol enraizado y etiquetado, en el que cada elemento está representado por uno de los nodos hoja , y cada nodo que no es hoja está etiquetado como P o Q. Un nodo AP tiene al menos dos hijos, y un nodo Q tiene al menos tres hijos.

Un árbol PQ representa sus permutaciones mediante reordenamientos permitidos de los hijos de sus nodos. Los hijos de un nodo P pueden reordenarse de cualquier forma. Los hijos de un nodo Q pueden colocarse en orden inverso, pero no pueden reordenarse de ninguna otra manera. Un árbol PQ representa todos los ordenamientos de nodos hoja que se pueden obtener mediante cualquier secuencia de estas dos operaciones. Un árbol PQ con muchos nodos P y Q puede representar subconjuntos complejos del conjunto de todos los ordenamientos posibles. Sin embargo, no todos los conjuntos de ordenamientos pueden representarse de esta manera; por ejemplo, si un ordenamiento está representado por un árbol PQ, el ordenamiento inverso también debe estar representado por el mismo árbol.

Los árboles PQ se utilizan para resolver problemas cuyo objetivo es encontrar un ordenamiento que satisfaga diversas restricciones. En estos problemas, las restricciones sobre el ordenamiento se incluyen una a una, modificando la estructura del árbol PQ de tal manera que represente solo los ordenamientos que satisfacen la restricción. Las aplicaciones de los árboles PQ incluyen la creación de un mapa de contigs a partir de fragmentos de ADN , ^{[ 2 ]} la comprobación de una matriz para la propiedad de unos consecutivos, el reconocimiento de grafos de intervalos y la determinación de si un grafo es planar . ^{[ 1 ]}

Si todas las hojas de un árbol PQ están conectadas directamente a un nodo raíz P, se permiten todos los ordenamientos posibles. Si todas las hojas están conectadas directamente a un nodo raíz Q, solo se permite un ordenamiento y su inverso. Si los nodos a, b y c se conectan a un nodo Q, que a su vez se conecta a un nodo raíz P, y todos los demás nodos hoja están conectados directamente a la raíz, se permite cualquier ordenamiento en el que a, b y c sean contiguos.

Cuando no se dispone de una representación gráfica, los árboles PQ suelen representarse mediante listas anidadas entre paréntesis. Cada par de paréntesis cuadrados representa un nodo Q, y cada par de paréntesis redondeados representa un nodo P. Las hojas son los elementos de las listas que no son paréntesis. La imagen de la izquierda se representa en esta notación mediante [1 (2 3 4) 5]. Este árbol PQ representa las siguientes doce permutaciones del conjunto {1, 2, 3, 4, 5}:

12345, 12435, 13245, 13425, 14235, 14325, 52341, 52431, 53241, 53421, 54231, 54321.

El árbol PC , desarrollado por Wei-Kuan Shih y Wen-Lian Hsu , es una generalización más reciente del árbol PQ. Al igual que el árbol PQ, representa permutaciones mediante reordenamientos de nodos en un árbol, con los elementos representados en las hojas del mismo. A diferencia del árbol PQ, el árbol PC no tiene raíz. Los nodos adyacentes a cualquier nodo no hoja etiquetado como P pueden reordenarse arbitrariamente, como en el árbol PQ, mientras que los nodos adyacentes a cualquier nodo no hoja etiquetado como C tienen un orden cíclico fijo y solo pueden reordenarse invirtiendo dicho orden. Por lo tanto, un árbol PC solo puede representar conjuntos de ordenamientos en los que cualquier permutación circular o inversión de un ordenamiento en el conjunto también se encuentre en el conjunto. Sin embargo, un árbol PQ con n elementos puede simularse mediante un árbol PC con n + 1 elementos, donde el elemento adicional sirve para enraizar el árbol PC. Las operaciones de estructura de datos necesarias para realizar un algoritmo de prueba de planaridad en árboles PC son algo más simples que las operaciones correspondientes en árboles PQ. ^{[ 3 ]}

• Orden parcial serie-paralelo

• Algoritmo de árbol PQ y problema de los unos consecutivos
• Demostración en Javascript de PQ Trees