![]() |
Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00611
Restricted rotation distance between k-ary trees
Vol. 27, no. 1, pp. 19-33, 2023. Regular paper.
Abstract We study restricted rotation distance between ternary and higher-valence trees
using approaches based upon generalizations of Thompson's group $F$.
We obtain bounds and a method for computing these distances exactly in linear time,
as well as a linear-time algorithm for computing rotations needed to realize these
distances. Unlike the binary case, the higher-valence notions of rotation distance
do not give Tamari lattices, so there are fewer tools
for analysis in the higher-valence settings. Higher-valence trees arise in a range
of database and filesystem applications where balance is important for
efficient performance.
![]() |
Submitted: June 2022.
Reviewed: July 2022.
Revised: December 2022.
Accepted: February 2023.
Final: February 2023.
Published: February 2023.
Communicated by
Giuseppe Liotta
|
Journal Supporters
|