Binary search trees (BSTs) are one of the most basic and widely used data structures. The best static tree for serving a sequence of queries (searches) can be computed by dynamic programming. In contrast, when the BSTs are allowed to be dynamic (i.e. change by rotations between searches), we still do not know how to compute the optimal algorithm (OPT) for a given sequence. One of the candidate algorithms whose serving cost is suspected to be optimal up-to a (multiplicative) constant factor is known by the name Greedy Future (GF). In an equivalent geometric way of representing queries on BSTs, GF is in fact equivalent to another algorithm called Geometric Greedy (GG). Most of the results on GF are obtained using the geometric model and the study of GG. Despite this intensive recent fruitful research, the best lower bound we have on the competitive ratio of GF is $\frac{4}{3}$. Furthermore, it has been conjectured that the additive gap between the cost of GF and OPT is only linear in the number of queries. In this paper we prove a lower bound of $2$ on the competitive ratio of GF, and we prove that the additive gap between the cost of GF and OPT can be $\Omega(m \cdot \log\log n)$ where $n$ is the number of items in the tree and $m$ is the number of queries.
翻译:Binary 搜索树( BST) 是最基本和广泛使用的数据结构之一。 用于一系列查询( 搜索) 的最佳静态树( 搜索) 可以通过动态编程来计算。 相反, 当允许 BST 动态化时( 由搜索之间轮换改变), 我们仍不知道如何计算特定序列的最佳算法( OPT ) 。 其中一种候选算法, 其服务成本被怀疑是最佳的上至( 倍增) 美元不变因素之一 。 在代表 BST 查询的同等几何方法中, GF 等同于另一个称为 Geology 的算法( GG ) 。 大部分 GF 的结果是使用几何模型和 GG 研究获得的。 尽管最近进行了深入细致的研究,但我们对GF 竞争比率的最大低约束是 $forc { {4} n3美元。 此外, 人们还推测GFF 和 AL 之间的加 差值差距在 $ $ 美元 的查询次数中是线性 。</s>