On Rotation Distance of Rank Bounded Trees

• Autorzy: Anoop, S.K.M. , Sarma, Jayalal
• Języki publikacji: EN

Abstrakty

EN

Computing the rotation distance between two binary trees with n internal nodes effi- ciently (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 in [1] in the context of decision trees). We define the rank-bounded rotation distance between two given full binary trees T1 and T2 (with n internal nodes) of rank at most r = max{rank(T1), rank(T2)}, denoted by dR(T1, T2), as the length of the shortest sequence of rotations that transforms T1 to T2 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 (full 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(n2) time algorithm for computing dR(T1, T2). That is, when the given full binary trees are skew trees (we call this variant the 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 dR(T1, T2) ≤ n2. • We show the following upper bound: for any two full binary trees T1 and T2 of rank r1 and r2 respectively, we have that: dR(T1, T2) ≤ n2(1 + (2n + 1)(r1 + r2 − 2)) where r = max{r1, r2}. This bound is asymptotically tight for r = 1. En route to our proof of the above theorems, we associate full binary trees to permutations and relate the rotation operation on trees to transpositions in the corresponding permutations. We give exact combinatorial characterizations of permutations that correspond to full binary trees and full skew binary trees under this association. We also precisely characterize the transpositions that correspond to the set of rotations in full binary trees. We also study bi-variate polynomials associated with binary trees (introduced by [2]), and show characterizations and algorithms for computing rotation distances for the case of full skew trees using them.

Słowa kluczowe

EN

Computer Science; Data Structures and Algorithms

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2024
• Tom: Vol. 191, nr 2
• Strony: 79--104
• Opis fizyczny: Bibliogr. 11 poz., rys.

Twórcy

autor

Anoop, S.K.M.

• Department of Computer Science and Engineering Indian Institute of Technology Madras (IIT Madras) Chennai, India

autor

Sarma, Jayalal

• Department of Computer Science and Engineering Indian Institute of Technology Madras (IIT Madras) Chennai, India,

Bibliografia

• [1] Ehrenfeucht A, Haussler D. Learning decision trees from random examples. Information and Computation, 1989. 82(3):231-246. doi:10.1016/0890-5401(89)90001-1.
• [2] Wiley C, Gray J. Polynomials, Binary Trees, and Positive Braids. Missouri Journal of Mathematical Sciences, 2014. 26(1):1-13. doi:10.35834/mjms/1404997104.
• [3] Culik K, Wood D. A note on some tree similarity measures. Information Processing Letters, 1982.15(1):39-42. doi:10.1016/0020-0190(82)90083-7.
• [4] Dehornoy P. On the rotation distance between binary trees. Advances in Mathematics, 2010. 223(4):1316-1355. doi:10.1016/j.aim.2009.09.016.
• [5] Sleator D, Tarjan R, Thurston W. Rotation Distance, Triangulations, and Hyperbolic Geometry. In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing. 1986 1(3):122-135. doi:10.1145/12130.12143.
• [6] Pournin L. The diameter of associahedra. Advances in Mathematics, 2014. 259:13-42.
• [7] Cleary S, John KS. A Linear-Time Approximation Algorithm for Rotation Distance. J. Graph Algorithms Appl., 2010. 14(2):385-390. doi:10.7155/jgaa.00212.
• [8] Lucas J. Untangling Binary Trees via Rotations. The Computer Journal, 2004. 47(2):259-269. doi:10.1093/comjnl/47.2.259.
• [9] Lucas J. The Rotation Graph of Binary Trees Is Hamiltonian. Journal of Algorithms, 1987. 8(4):503-535. doi:10.1016/0196-6774(87)90048-4.
• [10] Crespelle C, Gambette P. Linear-Time Constant-Ratio Approximation Algorithm and Tight Bounds for the Contiguity of Cographs. In: WALCOM: Algorithms and Computation, 7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings, volume 7748 of Lecture Notes in Computer Science. Springer, 2013 pp. 126-136.
• [11] Bulteau L, Fertin G, Rusu I. Sorting by Transpositions Is Difficult. In: Proceedings of International Conference on Automata, Languages and Programming (ICALP 2011). 2011 pp. 654-665. doi:10.1007/978-3-642-22006-7 55.

Identyfikatory

DOI

10.3233/FI-242173