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. Es un árbol etiquetado y enraizado, en el que cada elemento está representado por uno de los nodos hoja , y cada nodo no hoja está etiquetado como P o Q. El 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 forma. Los hijos de un nodo Q se pueden poner en orden inverso, pero no se pueden reordenar de otro modo. Un árbol PQ representa todos los ordenamientos de los nodos hoja que se pueden lograr 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 posibles ordenamientos. Sin embargo, no todos los conjuntos de pedidos pueden representarse de esta manera; por ejemplo, si un orden está representado por un árbol PQ, el reverso del orden también debe estar representado por 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 en el orden se incluyen una a la vez, modificando la estructura del árbol PQ de tal manera que represente solo los pedidos que satisfacen la restricción. Las aplicaciones de los árboles PQ incluyen crear un mapa de contig a partir de fragmentos de ADN [ cita requerida ] , probar una matriz para la propiedad de los consecutivos, reconocer gráficos de intervalo [ cita requerida ] y determinar si un gráfico es plano [ cita requerida ] .
Ejemplos y notación [ editar ]
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 Q raíz, solo se permite un orden y su reverso. 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 hoja conectados directamente a la raíz, entonces se permite cualquier ordenamiento donde a, b, c sean contiguos.
Cuando la presentación gráfica no está disponible, los árboles PQ a menudo se anotan usando listas anidadas entre paréntesis. Cada par coincidente de paréntesis cuadrados representa un nodo Q y cada par coincidente 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 está representada en esta notación por [1 (2 3 4) 5]. Este árbol PQ representa las siguientes doce permutaciones en el conjunto {1, 2, 3, 4, 5}:
- 12345, 12435, 13245, 13425, 14235, 14325, 52341, 52431, 53241, 53421, 54231, 54321.
Árboles de PC [ editar ]
El árbol PC , desarrollado por Wei-Kuan Shih y Wen-Lian Hsu , es una generalización más reciente del árbol PQ. Como el árbol PQ, representa permutaciones por reordenamientos de nodos en un árbol, con elementos representados en las hojas del árbol. A diferencia del árbol de PQ, el árbol de 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 de 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 nLos elementos se pueden simular mediante un árbol de PC en n + 1 elementos, donde el elemento adicional sirve para enraizar el árbol de PC. Las operaciones de estructura de datos necesarias para realizar un algoritmo de prueba de planaridad en árboles de PC son algo más simples que las operaciones correspondientes en árboles de PQ.
Ver también [ editar ]
Referencias [ editar ]
- Booth, Kellogg S. y Lueker, George S. (1976). "Prueba de la propiedad de los consecutivos, gráficos de intervalo y planaridad de gráfico utilizando algoritmos de árbol PQ". Revista de Ciencias de la Computación y Sistemas . 13 (3): 335–379. doi : 10.1016 / S0022-0000 (76) 80045-1 .
- Shih, Wei-Kuan y Hsu, Wen-Lian (1999). "Una nueva prueba de planaridad" (PDF) . Informática Teórica . 223 (1-2): 179-191. doi : 10.1016 / S0304-3975 (98) 00120-0 .
Enlaces externos [ editar ]
