Binary Tree Sequence Rotations and t-ary Tree Enumerations

In this book, we consider a transformation on binary trees using new types of rotations. Each of the newly proposed rotations is permitted only at nodes on the left-arm or the right-arm of a tree. Consequently, we develop a linear time algorithm with at most n - 1 rotations for converting weight sequences between any two binary trees. we use right distance sequences (or RD-sequences for short), to describe all t-ary trees with n internal nodes. Using a t-ary recursion tree and its concomitant tables, a systematical way can help us to investigate the structural representation of t-ary trees. Consequently, we develop efficient algorithms for determining the rank of a given t-ary tree in lexicographic order (i.e., the ranking algorithm), and for converting a positive integer to its corresponding RD-sequence (i.e., the unranking algorithm). Both the ranking and unranking algorithms can be run in O(tn) time and without really building any auxiliary table. In addition, we also present a loopless algorithm to enumerate Gray-codes of t-ary trees using RD-sequences.

Mais sobre este produto