Binary Tree Sequence Rotations and t-ary Tree Enumerations
Binary Trees Rotations, Ranking, Unranking, and Loopless
Versandkostenfrei!
Versandfertig in 6-10 Tagen
32,99 €
inkl. MwSt.
PAYBACK Punkte
16 °P sammeln!
In this book, we consider a transformation on binarytrees using new types of rotations. Each of the newlyproposed rotations is permitted only at nodes on theleft-arm or the right-arm of a tree. Consequently, wedevelop a linear time algorithm with at most n 1rotations for converting weight sequences between anytwo binary trees.we use right distance sequences (or RD-sequences forshort), to describe all t-ary trees with n internalnodes. Using a t-ary recursion tree and itsconcomitant tables, a systematical way can help us toinvestigate the structural representation of t-arytrees. Consequently, we...
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.
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.
Andere Kunden interessierten sich für
