论文标题
树木上的树木
Splay trees on trees
论文作者
论文摘要
树上的搜索树（Stts）是对二进制搜索树（BST）的深远概括，从而有效地探索了树的结构域。 （BST是基础域是一条路径的特殊情况。）树木上的树木在计算机科学和离散数学中的各种姿势上进行了广泛的研究。 最近，Bose，Cardinal，Iacono，Koumoutsos和Langerman（Soda 2020）考虑了自适应性STT，并观察到，除了值得注意的例外，过去几十年来为BST开发的机械并不容易转移到STT中。特别是，他们询问是否可以有效地计算或近似最佳的STT（类似于Knuth的算法以获得最佳的BST），以及是否可以将自然自我调整的BST（例如Splay Trees（Sleator，Tarjan，1983））扩展到此更一般的环境。 我们肯定地回答两个问题。首先，我们表明$（1 + \ frac {1} {t}）$ - 可以在所有整数$ o（n^{2t + 1}）$中计算出最佳尺寸 - $ n $ stt的最佳尺寸 - $ n $ stt。其次，我们确定了具有线性旋转距离的广泛的STT家族，从而使张开树的概括为STT设置。我们表明，我们的广义散布满足静态最优性定理，渐近地以在线方式匹配最佳STT的成本，即在不了解搜索分布的情况下。我们的结果表明，将树木的动态最佳猜想扩展到树木上更广泛的树木环境。
Search trees on trees (STTs) are a far-reaching generalization of binary search trees (BSTs), allowing the efficient exploration of tree-structured domains. (BSTs are the special case in which the underlying domain is a path.) Trees on trees have been extensively studied under various guises in computer science and discrete mathematics. Recently Bose, Cardinal, Iacono, Koumoutsos, and Langerman (SODA 2020) considered adaptive STTs and observed that, apart from notable exceptions, the machinery developed for BSTs in the past decades does not readily transfer to STTs. In particular, they asked whether the optimal STT can be efficiently computed or approximated (by analogy to Knuth's algorithm for optimal BSTs), and whether natural self-adjusting BSTs such as Splay trees (Sleator, Tarjan, 1983) can be extended to this more general setting. We answer both questions affirmatively. First, we show that a $(1 + \frac{1}{t})$-approximation of an optimal size-$n$ STT for a given search distribution can be computed in time $O(n^{2t + 1})$ for all integers $t \geq 1$. Second, we identify a broad family of STTs with linear rotation-distance, allowing the generalization of Splay trees to the STT setting. We show that our generalized Splay satisfies a static optimality theorem, asymptotically matching the cost of the optimal STT in an online fashion, i.e. without knowledge of the search distribution. Our results suggest an extension of the dynamic optimality conjecture for Splay trees to the broader setting of trees on trees.
