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:
“Usually the scenery about them is drear and savage enough; and the logger’s camp is as completely in the woods as a fungus at the foot of a pine in a swamp; no outlook but to the sky overhead; no more clearing than is made by cutting down the trees of which it is built, and those which are necessary for fuel.”
—Henry David Thoreau (1817–1862)