A rotation in a binary tree is a local restructuring that changes the tree into another and preserves the inorder sequence. The rotation distance between two binary trees is the minimum number of rotations needed to transform one into another. However, a polynomial-time algorithm for computing rotation distances between any two binary trees has still not been found. Lucas (The Computer Journal, 47, 259–269, 2004) recently presented an O(n2)-time algorithm for finding the exact rotation distance between two binary trees that are of a restricted form (each node has at most one child in the source tree and there is at most one zig-zag pair in the destination tree), where n is the number of nodes in each binary tree. In this paper, by using the coding technique of left weight sequences, which was proposed by Pallo (The Computer Journal, 9, 171–175, 1986), we find another restricted set of binary trees in which any two of them can be transformed with the exact rotation distance. Our algorithm can be performed in linear time for finding the rotation distance between any two trees in the restricted set. Moreover, the actual sequence of transforming rotations can also be built.
Related posts:
- Resampling Halftone Images Using Interpolation and Error-Diffusion Halftoning schemes are developed for reserving the quality after transforming...
- Dynamic Multipath Allocation in Ad Hoc Networks Ad hoc networks are characterized by fast dynamic changes in...
- A Weighted Voting-Based Associative Classification Algorithm A new associative classification algorithm based on weighted voting (ACWV)...
Related posts brought to you by Yet Another Related Posts Plugin.