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

让算法的效率“跳起来”！ —— 浅谈“跳跃表”的相关操作及其应用 “跳跃表” — 新生的宠儿 跳跃表（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 -∞ -∞