Árbol PQ

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 17 de septiembre de 2015; las comprobaciones requieren 4 ediciones .

Un árbol PQ es una estructura de datos para representar un grupo de permutaciones . Este es un árbol plano enraizado . Los vértices colgantes en él representan elementos permutables. El resto de los vértices están etiquetados como , o . Los vértices marcados tienen al menos 3 hijos y los vértices marcados tienen al menos 2 hijos. En un árbol PQ, se permite reorganizar los descendientes de un vértice marcado arbitrariamente e invertir el orden de los descendientes de un vértice marcado como . $PAGS$ $q$ $q$ $PAGS$ $PAGS$ $q$

Los árboles PQ se utilizan para encontrar permutaciones, cuyas restricciones se conocen gradualmente, una por una. Tales problemas surgen cuando se recrea el ADN y se verifica la planitud de un gráfico.

Artículos

Booth, Kellogg S. y Lueker, George S. Pruebas de la propiedad de los consecutivos, gráficos de intervalos y planaridad de gráficos mediante algoritmos de árbol PQ // Journal of Computer and System Sciences. - 1976. - vol. 13 , núm. 3 . — págs. 335–379 . - doi : 10.1016/S0022-0000(76)80045-1 .
Shih, Wei-Kuan y Hsu, Wen-Lian. Una nueva prueba de planaridad (inglés) // Ciencias de la Computación Teórica (revista). - 1999. - vol. 223 . - pág. 179-191 . - doi : 10.1016/S0304-3975(98)00120-0 . Archivado desde el original el 12 de septiembre de 2006.
Mehta, DP y Sahni, S. 32. PQ Trees, PC Trees, and Planar Graphs // Handbook of Data Structures and Applications. — Taylor & Francis, 2004. — ISBN 9781420035179 .
3.2. Pruebas de planaridad // Gráficos planares: teoría y algoritmos / ed. por T. Nishizeki y N. Chiba. - Holanda Septentrional, 1988. - ISBN 0-444-702121 .

Árbol (estructura de datos)
Árbol de búsqueda binario Árbol (teoría de grafos) estructura de árbol
Árboles binarios	árbol binario árbol en T
Árboles binarios autoequilibrados	árbol AA árbol AVL árbol rojo-negro árbol de juego árbol con multas árbol cartesiano árbol de fibonacci árbol B árbol en T
árboles B	2-3-árbol árbol B⁺ árbol B* B x -árbol árbol de la UB 2-3-4 árbol (a,b)-árbol arbol bailando
árboles de prefijo	árbol de sufijos Árbol de prefijos comprimido Árbol de búsqueda ternario
Partición binaria del espacio	árbol k-dimensional árbol de vicepresidentes
Árboles no binarios	Árbol cuádruple octárbol Octree voxel disperso árbol exponencial árbol PQ
Rompiendo el espacio	R-árbol Árbol R de Hilbert R+-árbol R*-árbol árbol X M-árbol árbol de fenwick Árbol de segmentos
Otros árboles	montón árbol de hachís árbol de los dedos árbol métrico árbol de revestimiento árbol BK Árbol de doble cadena iDistancia Árbol de corte de enlace árbol LSM
Algoritmos	Primera búsqueda en amplitud Primera búsqueda en profundidad algoritmo DSW protocolo de árbol de expansión