Right-arm rotation distance between binary trees

DOI10.1016/S0020-0190(03)00283-7zbMath1161.68692MaRDI QIDQ1014416

Jean-Marcel Pallo

Publication date: 28 April 2009

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

latticealgorithmsrotationdistancebinary trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (21)

Restricted rotation distance between k-ary trees ⋮ A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations ⋮ BOUNDING RIGHT-ARM ROTATION DISTANCES ⋮ The pruning-grafting lattice of binary trees ⋮ Efficient lower and upper bounds of the diagonal-flip distance between triangulations ⋮ A direct algorithm for restricted rotation distance ⋮ An efficient algorithm for estimating rotation distance between two binary trees ⋮ The phagocyte lattice of Dyck words ⋮ Catalan intervals and uniquely sorted permutations ⋮ Refined upper bounds for right-arm rotation distances ⋮ Effective splaying with restricted rotations ⋮ Recursive constructions for the higher Stasheff-Tamari orders in dimension three using the outer Tamari and Tamari block posets ⋮ Root-restricted Kleenean rotations ⋮ Uniquely sorted permutations ⋮ The combinatorics of a tree-like functional equation for connected chord diagrams ⋮ On a subposet of the Tamari lattice ⋮ Some properties of a new partial order on Dyck paths ⋮ Computing spin networks ⋮ Unnamed Item ⋮ Weak associativity and restricted rotation ⋮ Motzkin subposets and Motzkin geodesics in Tamari lattices.

Cites Work

• Unnamed Item
• On the use of ordered sets in problems of comparison and consensus of classifications
• Metrics on partially ordered sets - a survey
• On the deque conjecture for the splay algorithm
• An efficient upper bound of the rotation distance of binary trees
• Restricted rotation distance between binary trees.
• Enumerating, Ranking and Unranking Binary Trees
• Lower Bounds for Accessing Binary Search Trees with Rotations
• The rotation \(\chi\)-lattice of ternary trees
• Relaxed balance using standard rotations

This page was built for publication: Right-arm rotation distance between binary trees