Rotation distance for rank bounded trees

DOI10.1007/978-3-031-22105-7_47arXiv2304.03985MaRDI QIDQ6168976FDOQ6168976

Authors: S. K. M. Anoop, Jayalal Sarma M. N. 

Publication date: 10 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Computing the rotation distance between two binary trees with $n$ internal nodes efficiently (in $poly(n)$ time) is a long standing open question in the study of height balancing in tree data structures. In this paper, we initiate the study of this problem bounding the rank of the trees given at the input (defined by Ehrenfeucht and Haussler (1989) in the context of decision trees). We define the rank-bounded rotation distance between two given binary trees $T_1$ and $T_2$ (with $n$ internal nodes) of rank at most $r$, denoted by $d_r(T_1,T_2)$, as the length of the shortest sequence of rotations that transforms $T_1$ to $T_2$ with the restriction that the intermediate trees must be of rank at most $r$. We show that the rotation distance problem reduces in polynomial time to the rank bounded rotation distance problem. This motivates the study of the problem in the combinatorial and algorithmic frontiers. Observing that trees with rank $1$ coincide exactly with skew trees (binary trees where every internal node has at least one leaf as a child), we show the following results in this frontier : We present an $O(n^2)$ time algorithm for computing $d_1(T_1,T_2)$. That is, when the given trees are skew trees (we call this variant as skew rotation distance problem) - where the intermediate trees are restricted to be skew as well. In particular, our techniques imply that for any two skew trees $d(T_1,T_2)le{n}^2$. We show the following upper bound : for any two trees $T_1$ and $T_2$ of rank at most $r_1$ and $r_2$ respectively, we have that: $d_r(T_1,T_2)le{n}^2(1+(2n+1)(r_1+r_2-2))$ where $r=max{r}_1,r_2$. This bound is asymptotically tight for $r=1$. En route our proof of the above theorems, we associate binary trees to permutations and bivariate polynomials, and prove several characterizations in the case of skew trees.

Full work available at URL: https://arxiv.org/abs/2304.03985

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Linear-time constant-ratio approximation algorithm and tight bounds for the contiguity of cographs
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• The rotation graph of binary trees is Hamiltonian
• Learning decision trees from random examples
• A note on some tree similarity measures
• On the rotation distance between binary trees
• Rotation distance is fixed-parameter tractable
• The diameter of associahedra
• A linear-time approximation algorithm for rotation distance

Cited In (1)

• Distributions of restricted rotation distances

This page was built for publication: Rotation distance for rank bounded trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6168976)