伸展树的先序和后序

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

摘要：设T是二叉搜索树。我们证明了关于Splay算法行为的两个结果（Sleator和Tarjan 1985）。我们的第一个结果是通过按照T的预订或T的后序的顺序将密钥插入到空的二进制搜索树中需要线性时间。我们的证据使用了这样一个事实，即预订和预订是模式避免的：即它们不包含分别与（2,3,1）和（3,1,2）顺序同构的子序列。模式避免意味着对项目插入方式的某些限制。我们利用这个结构利用一个简单的潜在函数来计算位于未插入节点的访问路径上的插入节点。我们的方法可以扩展到避免更一般模式的排列。其次，如果T是具有相同键的任何其他二元搜索树，如T 和 T'是权重平衡（Nievergelt和Reingold 1973），然后splaying 的T的预订序列或T的后序列从T'开始线性时间。为了证明这一点，我们证明了平衡搜索树的预订和出版物不会以对称的顺序包含许多大的“跳跃”，并利用动态手指定理来利用这一事实（Cole et al.2000）。我们的两个结果都提供了有利于难以捉摸的“动态最优猜想”的进一步证据。

原文标题：Splaying Preorders and Postorders 原文摘要：Let T be a binary search tree. We prove two results about the behavior of the Splay algorithm (Sleator and Tarjan 1985). Our first result is that inserting keys into an empty binary search tree via splaying in the order of eitherT's preorder orT's postorder takes linear time. Our proof uses the fact that preorders and postorders are pattern-avoiding: i.e. they contain no subsequences that are order-isomorphic to(2,3,1)and(3,1,2), respectively. Pattern-avoidance implies certain constraints on the manner in which items are inserted. We exploit this structure with a simple potential function that counts inserted nodes lying on access paths to uninserted nodes. Our methods can likely be extended to permutations that avoid more general patterns. Second, if T′is any other binary search tree with the same keys asT and T is weight-balanced (Nievergelt and Reingold 1973), then splayingT's preorder sequence orT's postorder sequence starting fromT′takes linear time. To prove this, we demonstrate that preorders and postorders of balanced search trees do not contain many large "jumps" in symmetric order, and exploit this fact by using the dynamic finger theorem (Cole et al. 2000). Both of our results provide further evidence in favor of the elusive "dynamic optimality conjecture."

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