Restricted rotation distance between k-ary trees

被引：0

作者：

Cleary S. ^{[1
,2
]}

机构：

[1] The City College of New York, United States

[2] The CUNY Graduate Center, United States

来源：

Journal of Graph Algorithms and Applications | 2023年 / 27卷 / 01期

关键词：

Clustering algorithms - Trees (mathematics);

D O I：

10.7155/jgaa.00611

中图分类号：

学科分类号：

摘要：

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 dis-tances. 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. © 2023, Brown University. All rights reserved.

引用

页码：19 / 33

页数：14