An efficient algorithm for estimating rotation distance between two binary trees

DOI10.1080/00207160500069870zbMath1101.68016OpenAlexW2025994050MaRDI QIDQ5312707

Jou-Ming Chang, Yen-Ju Chen, Yue-Li Wang

Publication date: 25 August 2005

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207160500069870

zbMATH Keywords

algorithmsbinary treesAVL treesrotation distance

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Related Items (5)

A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations ⋮ Efficient lower and upper bounds of the diagonal-flip distance between triangulations ⋮ Lower bounds on the rotation distance of binary trees ⋮ Effective splaying with restricted rotations ⋮ An improved kernel size for rotation distance in binary trees

Cites Work

• Unnamed Item
• On the loopless generation of binary tree sequences
• Generating binary trees by Glivenko classes on Tamari lattices
• Right-arm rotation distance between binary trees
• Bounding restricted rotation distance
• A note on some tree similarity measures
• On the deque conjecture for the splay algorithm
• An efficient upper bound of the rotation distance of binary trees
• Flipping edges in triangulations
• On the upper bound on the rotation distance of binary trees
• Restricted rotation distance between binary trees.
• Graph of triangulations of a convex polygon and tree of triangulations
• A direct algorithm for restricted rotation distance
• Symmetric binary B-trees: Data structure and maintenance algorithms
• The number of coverings in four catalan lattices
• Enumerating, Ranking and Unranking Binary Trees
• Self-adjusting binary search trees
• The rotation graph of binary trees is Hamiltonian
• Short notes: Some Properties of the Rotation Lattice of Binary Trees
• General Balanced Trees
• On Rotations and the Generation of Binary Trees

This page was built for publication: An efficient algorithm for estimating rotation distance between two binary trees