A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations

摘要

In this paper, 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. In particular, from an analysis of aggregate method for a sequence of rotations, each rotation of the proposed algorithm can be performed in a constant amortized time. Next, we show that a specific directed rooted tree called rotation tree can be constructed using one of the new type rotations. As a by-product, a naive algorithm for enumerating weight sequences of binary trees in lexicographic order can be implemented by traversing the rotation tree.