PC Trees
The PC tree, developed by Wei-Kuan Shih and Wen-Lian Hsu, is a more recent generalization of the PQ tree. Like the PQ tree, it represents permutations by reorderings of nodes in a tree, with elements represented at the leaves of the tree. Unlike the PQ tree, the PC tree is unrooted. The nodes adjacent to any non-leaf node labeled P may be reordered arbitrarily as in the PQ tree, while the nodes adjacent to any non-leaf node labeled C have a fixed cyclic order and may only be reordered by reversing this order. Thus, a PC tree can only represent sets of orderings in which any circular permutation or reversal of an ordering in the set is also in the set. However, a PQ tree on n elements may be simulated by a PC tree on n + 1 elements, where the extra element serves to root the PC tree. The data structure operations required to perform a planarity testing algorithm on PC trees are somewhat simpler than the corresponding operations on PQ trees.
Read more about this topic: PQ Tree
Famous quotes containing the word trees:
“Out of the woods my Master came,
Content with death and shame.
When Death and Shame would woo Him last,
From under the trees they drew Him last:
‘Twas on a tree they slew Him—last
When out of the woods He came.”
—Sidney Lanier (1842–1881)