Ro-Yu Wu, Yue-Li Wang, Jou-Ming Chang

Binary Tree Sequence Rotations and t-ary Tree Enumerations

Binary Trees Rotations, Ranking, Unranking, and Loopless

• Broschiertes Buch

Produktbeschreibung

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.

Produktdetails

• Verlag: VDM Verlag Dr. Müller
• Seitenzahl: 96
• Englisch
• Gewicht: 140g
• ISBN-13: 9783639176346
• ISBN-10: 3639176340
• Artikelnr.: 26605151

Autorenporträt

Ro-Yu Wu, PhD: Studied Information Management at the National
Taiwan University of Science and Technology. Associate professor
at the Department of Industrial Management at Lunghwa University
of Science and Technology., Taiwan.