算法合集之《浅谈“跳跃表”的相关操作及其应用》.pptVIP

算法合集之《浅谈“跳跃表”的相关操作及其应用》.ppt

  1. 1、本文档共15页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
让算法的效率“跳起来”! —— 浅谈“跳跃表”的相关操作及其应用 “跳跃表” — 新生的宠儿 跳跃表(Skip List)是1987年才诞生的一种崭新的数据结构,它在进行查找、插入、删除等操作时的时间复杂度均为O(logn),有着近乎替代平衡树的本领。而且最重要的一点,就是它的编程复杂度较同类的AVL树,红黑树等要低得多,这使得其无论是在理解还是在推广性上,都有着十分明显的优势。 “跳跃表”的结构 跳跃表由多条链构成(S0,S1,S2 ……,Sh),且满足如下三个条件: 每条链必须包含两个特殊元素:+∞ 和 -∞ S0包含所有的元素,并且所有链中的元素按照升序排列。 每条链中的元素集合必须包含于序数较小的链的元素集合,即: “跳跃表” 的时空效率 空间复杂度: O(n) (期望) 跳跃表高度: O(logn) (期望) 相关操作的时间复杂度: 查找: O(logn) (期望) 插入: O(logn) (期望) 删除: O(logn) (期望) 基本操作一 查找 目的:在跳跃表中查找一个元素 x 在跳跃表中查找一个元素x,按照如下几个步骤进行: 从最上层的链(Sh)的开头开始 假设当前位置为p,它向右指向的节点为q(p与q不一定相邻),且q的值为y。将y与x作比较 x=y 输出查询成功,输出相关信息 xy 从p向右移动到q的位置 xy 从p向下移动一格 如果当前位置在最底层的链中(S0),且还要往下移动的话,则输出查询失败 基本操作二 插入 目的:在跳跃表中插入一个元素 x 插入操作由两部分组成: 查找插入的位置和插入对应元素。 为了确定插入的“列高”,我们引入一个随机决策模块: 产生一个0到1的随机数r r ← random() 如果r小于一个概率因子P,则执行方案A, if rp then do A 否则,执行方案B else do B 基本操作二 插入 假设我们现在要插入一个元素40到已有的跳跃表中。 基本操作三 删除 目的:从跳跃表中删除一个元素 x 删除操作分为以下三个步骤: 在跳跃表中查找到这个元素的位置,如果未找到,则退出 将该元素所在整列从表中删除 将多余的“空链”删除 概率因子 P 对跳跃表的影响 在插入操作中,我们引入了一个概率因子P,它决定了跳跃表的高度,并影响到了整个数据结构的效率。 让我们来看看在实际评测过程中,不同的P在时空效率上的差异。 跳跃表的应用 高效率的相关操作和较低的编程复杂度使得跳跃表在实际应用中的范围十分广泛。尤其在那些编程时间特别紧张的情况下,高性价比的跳跃表很可能会成为你的得力助手。 跳跃表的应用 NOI2004 Day1 郁闷的出纳员(Cashier) 抽象题意: 跳跃表的应用 NOI2004 Day1 郁闷的出纳员(Cashier) 跳跃表的应用 HNOI2004 Day1 宠物收养所 (Pet) 抽象题意: 维护一个数据结构,使得它支持以下两种操作: 插入一个元素 x (0x231) 给定一个元素y,删除现有与y差值最小的元素x (|x-y|为最小) 所有操作次数不超过80000 总结 跳跃表作为一种新兴的数据结构,以相当高的效率和较低的复杂度散发着其独特的光芒。和同样以编程复杂度低而闻名的“伸展树”相比,跳跃表的效率不但不会比它差,甚至优于前者。 谢谢大家 Thank you * * 华东师范大学第二附属中学 魏冉 53 53 53 45 45 37 30 30 30 29 15 11 11 11 11 -∞ -∞ -∞ -∞ +∞ +∞ +∞ +∞ S0 S1 S2 S3 跳跃表的实例 53 53 53 45 45 37 30 30 30 29 15 11 11 11 11 -∞ -∞ -∞ -∞ +∞ +∞ +∞ +∞ 查询元素53的全过程 S0 S1 S2 S3 查找成功! 列的初始高度为1。插入元素时,不停地执行随机决策模块。如果要求执行的是A操作,则将列的高度加1,并且继续反复执行随机决策模块。直到第i次,模块要求执行的是B操作,我们结束决策,并向跳跃表中插入一个高度为i的列。 37 30 30 30 29 15 -∞ -∞

文档评论(0)

jdy261842 + 关注
实名认证
文档贡献者

分享好文档!

1亿VIP精品文档

相关文档