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:
“But, where the road runs near the stream,
Oft through the trees they catch a glance
Of passing troops in the sun’s beam—
Pennon, and plume, and flashing lance!
Forth to the world those soldiers fare,
To life, to cities, and to war!”
—Matthew Arnold (1822–1888)