PQ strom

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 17. září 2015; kontroly vyžadují 4 úpravy .

PQ strom je datová struktura pro reprezentaci permutační skupiny . Toto je zakořeněný planární strom . Visící vrcholy v něm představují permutovatelné prvky. Zbytek vrcholů je označen buď , nebo . Označené vrcholy mají alespoň 3 potomky a označené vrcholy mají alespoň 2 potomky. V PQ-stromu je povoleno libovolně přeskupit potomky vrcholu označeného a obrátit pořadí potomků vrcholu označeného . $P$ $Q$ $Q$ $P$ $P$ $Q$

PQ-stromy se používají k nalezení permutací, jejichž omezení jsou známa postupně, jedna po druhé. Takové problémy vznikají při obnově DNA a kontrole rovinnosti grafu.

Články

Booth, Kellogg S. a Lueker, George S. Testování vlastností po sobě jdoucích, intervalových grafů a rovinnosti grafu pomocí algoritmů PQ-tree // Journal of Computer and System Sciences. - 1976. - Sv. 13 , č. 3 . — S. 335–379 . - doi : 10.1016/S0022-0000(76)80045-1 .
Shih, Wei-Kuan a Hsu, Wen-Lian. Nový test rovinnosti (anglicky) // Theoretical Computer Science (žurnál). - 1999. - Sv. 223 . - S. 179-191 . - doi : 10.1016/S0304-3975(98)00120-0 . Archivováno z originálu 12. září 2006.
Mehta, DP a Sahni, S. 32. PQ stromy, PC stromy a rovinné grafy // Příručka datových struktur a aplikací. — Taylor & Francis, 2004. — ISBN 9781420035179 .
3.2. Testování rovinnosti // Planar Graphs: Theory and Algorithms / ed. T. Nishizeki a N. Chiba. - North-Holland, 1988. - ISBN 0-444-702121 .

Strom (datová struktura)
Binární vyhledávací strom Strom (teorie grafů) stromová struktura
Binární stromy	binární strom T-strom
Samovyrovnávací binární stromy	AA strom strom AVL Červeno-černý strom Rozvětvený strom strom s pokutami karteziánský strom Fibonacciho strom B-strom T-strom
B-stromy	2-3-strom B⁺-strom B*-strom B x -strom UB strom 2-3-4 strom (a,b)-strom tančící strom
předponové stromy	příponový strom Komprimovaný strom předpon Ternární vyhledávací strom
Binární dělení prostoru	k-rozměrný strom VP strom
Nebinární stromy	Čtyřstrom oktree Řídký Voxel Octree exponenciální strom PQ strom
Rozbití prostoru	R-strom Hilbertův R-strom R+-strom R*-strom X-strom M-strom Fenwickův strom Segmentový strom
Jiné stromy	halda hash tree prstový strom metrický strom Potahový strom BK-strom Dvouřetězový strom iVzdálenost Link-cut strom LSM strom
Algoritmy	Šířka první hledání Hloubka první hledání Algoritmus DSW protokol spanning tree