专栏首页算法和应用伸展树的先序和后序
原创

伸展树的先序和后序

作者: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

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 论婚姻问题的泛化概括

    摘要:我们将Hall著名的婚姻定理的婚姻问题概括为我们称之为对称婚姻问题,这个问题可以被认为是最大加权二元匹配的一个特例。 我们证明了对称婚姻问题的解决方案,当...

    罗大琦
  • 蛋糕切割图:离散和有界比例协议

    作者:Xiaohui Bei,Xiaoming Sun,Hao Wu,Jialin Zhang,Zhijie Zhang,Wei Zi

    罗大琦
  • 关于无意识匹配问题

    作者:Zhihao Gavin Tang,Xiaowei Wu,Yuhao Zhang

    罗大琦
  • Social networks and health: Communicable but not infectious

    Harvard Men’s Health Watch Poet and pastor John Donne famously proclaimed “No ma...

    互联网金融打杂
  • 霍克斯模型的电信模式揭示了人际关系的动态和个性特征(社会和信息网络)

    我们的手机包含了大量关于我们的私人信息,这不是新闻,这也是为什么我们要尽量保证手机的安全。但即使是我们通信方式的痕迹,也能看出不少关于我们的信息。在这项工作中,...

    Jillchen996
  • 枪声:枪声样本数字取证与人工智能(CS LG)

    根据炮口冲击波对武器进行分类是一项具有挑战性的任务,在各种安全和军事领域有着重要的应用。 现有的大多数工程依赖于特别部署的空间多样性麦克风传感器,以捕捉同一枪击...

    用户7095611
  • 【论文推荐】最新7篇视觉问答(VQA)相关论文—解释、读写记忆网络、逆视觉问答、视觉推理、可解释性、注意力机制、计数

    【导读】专知内容组整理了最近七篇视觉问答(Visual Question Answering)相关文章,为大家进行介绍,欢迎查看! 1.VQA-E: Expla...

    WZEARW
  • 【论文推荐】最新5篇深度强化学习相关论文推荐—经验驱动的网络、自动数据库管理、双光技术推荐系统、UAVs、多代理竞争对手

    【导读】专知内容组整理了最近强化学习相关文章,为大家进行介绍,欢迎查看! 1. Experience-driven Networking: A Deep Rei...

    WZEARW
  • 花边土地投资5.25亿美元,收入增长300%

    随着这一流行病在2020年开始流行,企业加快了向云服务的转移。云安全初创公司Lacework在正确的时间出现在正确的地点,因为客户正在寻找保护其云本地工作负载的...

    用户8054111
  • 【CCF-CV特别活动】“CCF-腾讯犀牛鸟沙龙”走进腾讯优图

    中国计算机学会计算机视觉专委会走进企业系列交流会 CCF-CV@Industry 腾讯优图·上海 主题:图像识别和多媒体分析技术前沿 时间:2016年5月13日...

    腾讯高校合作

扫码关注云+社区

领取腾讯云代金券