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 no 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 a través de reordenamientos permisibles de los hijos de sus nodos. Los hijos de un nodo P pueden reordenarse de cualquier manera. Los hijos de un nodo Q pueden colocarse en orden inverso, pero no pueden reordenarse de otra manera. Un árbol PQ representa todos los ordenamientos de nodos hoja que pueden lograrse mediante cualquier secuencia de estas dos operaciones. Un árbol PQ con muchos nodos P y Q puede representar subconjuntos complicados 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 se representa mediante un árbol PQ, el orden inverso también debe representarse mediante el mismo árbol.
Los árboles PQ se utilizan para resolver problemas en los que el objetivo es encontrar un orden que satisfaga varias restricciones. En estos problemas, las restricciones sobre el orden se incluyen de a una por vez, 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 contig a partir de fragmentos de ADN , [2] la prueba de una matriz para la propiedad de unos consecutivos, el reconocimiento de gráficos de intervalos y la determinación de si un gráfico es planar . [1]
Si todas las hojas de un árbol PQ están conectadas directamente a un nodo raíz P, entonces se permiten todos los ordenamientos posibles. Si todas las hojas están conectadas directamente a un nodo raíz Q, entonces solo se permite un orden y su inverso. Si los nodos a, b, c se conectan a un nodo P, que se conecta a un nodo raíz P, con todos los demás nodos de hoja conectados directamente a la raíz, entonces se permite cualquier ordenamiento donde a, b, c sean contiguos.
Cuando no se dispone de una representación gráfica, los árboles PQ se suelen representar 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 elementos de las listas que no están entre 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 en el conjunto {1, 2, 3, 4, 5}:
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 elementos representados en las hojas del árbol. A diferencia del árbol PQ, el árbol PC no tiene raíz. Los nodos adyacentes a cualquier nodo no hoja etiquetado P pueden reordenarse arbitrariamente como en el árbol PQ, mientras que los nodos adyacentes a cualquier nodo no hoja etiquetado C tienen un orden cíclico fijo y solo pueden reordenarse invirtiendo este 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 esté en el conjunto. Sin embargo, un árbol PQ en n elementos puede ser simulado por un árbol PC en 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]