从Splay到动态优化的新路径

作者：Caleb C. Levy,Robert E. Tarjan

摘要：考虑在二叉搜索树中执行搜索序列的任务。 在每次搜索之后，允许算法以与执行的重构量成比例的成本任意地重构树。 执行的成本是搜索所花费的时间和使用重组操作优化这些搜索所花费的时间的总和。 这个概念是由Sleator和Tarjan通过计算和猜想在（JACM，1985）中引入的。 算法Splay是一个严苛的过程，用于在将搜索到的项目移动到树顶部时执行调整。 这种被称为“动态最优性”的猜想是，展开的成本总是在用于执行搜索的最佳算法的恒定因子内。 这个猜想一直持续到今天。 在这项工作中，我们试图为动态最优性猜想的证明奠定基础。

原文标题：New Paths from Splay to Dynamic Optimality

原文摘要：Consider the task of performing a sequence of searches in a binary search tree. After each search, an algorithm is allowed to arbitrarily restructure the tree, at a cost proportional to the amount of restructuring performed. The cost of an execution is the sum of the time spent searching and the time spent optimizing those searches with restructuring operations. This notion was introduced by Sleator and Tarjan in (JACM, 1985), along with an algorithm and a conjecture. The algorithm, Splay, is an elegant procedure for performing adjustments while moving searched items to the top of the tree. The conjecture, called "dynamic optimality," is that the cost of splaying is always within a constant factor of the optimal algorithm for performing searches. The conjecture stands to this day. In this work, we attempt to lay the foundations for a proof of the dynamic optimality conjecture.

地址：https://arxiv.org/abs/1907.06310