Consider the task of performing a sequence of searches in a binary search tree. After each search, we allow an algorithm to arbitrarily restructure the tree. The cost of executing the task is the sum of the time spent searching and the time spent optimizing the searches with restructuring operations. Sleator and Tarjan introduced this notion in 1985, along with an algorithm and a conjecture. The algorithm, Splay, is an elegant procedure for performing adjustments that move 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. We lay a foundation for proving the dynamic optimality conjecture. Central to our method is approximate monotonicity. Approximately monotone algorithms are those whose cost does not increase by more than a fixed multiple after removing searches from the sequence. As we shall see, Splay is dynamically optimal if and only if it is approximately monotone. This result extends to a weaker form of approximate monotonicity as well as insertion, deletion, and related algorithms. We prove that a lower bound on optimal execution cost is approximately monotone and outline how to adapt this proof from the lower bound to Splay, and how to overcome the remaining barriers to establishing dynamic optimality.
翻译:考虑在二进制搜索树中进行一系列搜索的任务 。 每次搜索后, 我们允许任意重组树的算法 。 执行任务的成本是花费的搜索时间和用重组操作优化搜索的时间的总和。 Sleator 和 Tarjan 于1985年引入了这个概念以及一个算法和猜想。 算法Splay 是一种优雅的程序, 用于进行调整, 将搜索的物品移到树顶部。 推测称为动态最佳性, 是播放的成本总是在进行搜索的最佳算法的一个不变因素中。 我们为证明动态最佳预测打下了一个基础。 我们的方法的核心是近似单调。 大约单调算法的算法是那些成本在从序列中去除搜索后不会增加超过固定倍数的算法。 正如我们可以看到, 演算法是一种动态最佳的调整程序, 如果而且只有大约为单一性, 其结果也是一种较弱的形式, 包括插入、 删除和相关的算法。 我们证明, 最优的执行成本是相对较低的, 是如何从最优制的立式障碍, 是如何从最优制到最优制的立式的立式的立式 。