PQ-träd
Ett PQ-träd är en trädbaserad datastruktur som representerar en familj av permutationer på en uppsättning element, upptäckt och namngiven av Kellogg S. Booth och George S. Lueker 1976. Det är ett rotat, märkt träd, där varje element representeras av en av lövnoderna , och varje icke-bladsnod är märkt P eller Q. AP-nod har minst två barn och en Q-nod har minst tre barn.
Ett PQ-träd representerar dess permutationer via tillåtna omordningar av barnen till dess noder. Barnen till en P-nod kan ordnas om på vilket sätt som helst. Underordnade av en Q-nod kan placeras i omvänd ordning, men får inte på annat sätt omordnas. Ett PQ-träd representerar alla bladnodsordningar som kan uppnås genom vilken sekvens som helst av dessa två operationer. Ett PQ-träd med många P- och Q-noder kan representera komplicerade delmängder av uppsättningen av alla möjliga beställningar. Det är dock inte säkert att varje uppsättning beställningar kan representeras på detta sätt; till exempel, om en beställning representeras av ett PQ-träd, måste den omvända ordningen också representeras av samma träd.
PQ-träd används för att lösa problem där målet är att hitta en beställning som uppfyller olika begränsningar. I dessa problem ingår restriktioner för beställningen en i taget, genom att modifiera PQ-trädstrukturen på ett sådant sätt att den endast representerar beställningar som uppfyller begränsningen. Tillämpningar av PQ-träd inkluderar att skapa en contig-karta från DNA- fragment, testa en matris för de konsekutiva egenskaperna, känna igen intervallgrafer och bestämma om en graf är plan .
Exempel och notation
Om alla blad i ett PQ-träd är anslutna direkt till en rot P-nod är alla möjliga ordningar tillåtna. Om alla blad är anslutna direkt till en rot Q-nod är endast en ordning och dess omvända ordning tillåten. Om noderna a,b,c ansluter till en P-nod, som ansluter till en rot P-nod, med alla andra bladnoder anslutna direkt till roten, så är all ordning där a,b,c är angränsande tillåten.
Där grafisk presentation inte är tillgänglig noteras ofta PQ-träd med hjälp av kapslade listor med parenteser. Varje matchat par av fyrkantiga parenteser representerar en Q-nod och varje matchat par av rundade parenteser representerar en P-nod. Blad är icke-parenteselement i listorna. Bilden till vänster representeras i denna notation av [1 (2 3 4) 5]. Detta PQ-träd representerar följande tolv permutationer på uppsättningen {1, 2, 3, 4, 5}:
- 12345, 12435, 13245, 13425, 14235, 14325, 52341, 52431, 53241, 53421, 54231, 54321.
PC-träd
PC -trädet , utvecklat av Wei-Kuan Shih och Wen-Lian Hsu, är en nyare generalisering av PQ-trädet. Liksom PQ-trädet representerar det permutationer genom omordning av noder i ett träd, med element representerade vid trädets löv. Till skillnad från PQ-trädet är PC-trädet unrooted. Noderna som gränsar till valfri icke-bladsnod märkt P kan ordnas om godtyckligt som i PQ-trädet, medan noderna som gränsar till valfri icke-bladsnod märkt C har en fast cyklisk ordning och endast kan ordnas om genom att vända denna ordning. Således kan ett PC-träd endast representera uppsättningar av beställningar där varje cirkulär permutation eller omkastning av en ordning i uppsättningen också finns i uppsättningen. Ett PQ-träd på n element kan emellertid simuleras av ett PC-träd på n + 1 element, där det extra elementet tjänar till att rota PC-trädet. De datastrukturoperationer som krävs för att utföra en planaritetstestalgoritm på PC-träd är något enklare än motsvarande operationer på PQ-träd.