国家集训队2005论文集 魏冉

《国家集训队2005论文集 魏冉》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、让算法的效率“跳起来”！——浅谈“跳跃表”的相关操作及其应用华东师范大学第二附属中学魏冉“跳跃表”—新生的宠儿跳跃表（SkipList）是1987年才诞生的一种崭新的数据结构，它在进行查找、插入、删除等操作时的时间复杂度均为O(logn),有着近乎替代平衡树的本领。而且最重要的一点，就是它的编程复杂度较同类的AVL树，红黑树等要低得多，这使得其无论是在理解还是在推广性上，都有着十分明显的优势。“跳跃表”的结构跳跃表由多条链构成（S0，S1，S2……，Sh），且满足如下三个条件：每条链必须包含两个特殊元素：+∞

2、和-∞S0包含所有的元素，并且所有链中的元素按照升序排列。每条链中的元素集合必须包含于序数较小的链的元素集合，即：535353454537303030291511111111-∞-∞-∞-∞+∞+∞+∞+∞S0S1S2S3跳跃表的实例“跳跃表”的时空效率空间复杂度：O(n)（期望）跳跃表高度：O(logn)（期望）相关操作的时间复杂度：查找：O(logn)（期望）插入：O(logn)（期望）删除：O(logn)（期望）基本操作一查找目的：在跳跃表中查找一个元素x在跳跃表中查找一个元素x，按照如下几个步骤进行：

3、从最上层的链（Sh）的开头开始假设当前位置为p，它向右指向的节点为q（p与q不一定相邻），且q的值为y。将y与x作比较x=y输出查询成功，输出相关信息x>y从p向右移动到q的位置x

4、入的“列高”，我们引入一个随机决策模块：产生一个0到1的随机数rr←random()如果r小于一个概率因子P，则执行方案A，ifr

5、置5353534545+∞+∞+∞+∞40404040高度+1随机化模块运行状况：高度=4高度+1高度+1结束53-∞-∞-∞-∞S0S1S2S3基本操作三删除目的：从跳跃表中删除一个元素x删除操作分为以下三个步骤：在跳跃表中查找到这个元素的位置，如果未找到，则退出将该元素所在整列从表中删除将多余的“空链”删除111111115353534545373030302915+∞+∞+∞+∞5353534545373030302915-∞-∞-∞+∞+∞+∞S0S1S2概率因子P对跳跃表的影响在插入操作中，我们引入

6、了一个概率因子P，它决定了跳跃表的高度，并影响到了整个数据结构的效率。让我们来看看在实际评测过程中，不同的P在时空效率上的差异。P平均操作时间平均列高总结点数每次查找跳跃次数（平均值）每次插入跳跃次数（平均值）每次删除跳跃次数（平均值）2/30.0024690ms3.0049123339.87841.60441.5661/20.0020180ms1.9956068327.80729.94729.0721/e0.0019870ms1.5844757027.33228.23828.4521/40.0021720m

7、s1.3304047828.72629.47229.6641/80.0026880ms1.1443442035.14735.82136.007跳跃表的应用高效率的相关操作和较低的编程复杂度使得跳跃表在实际应用中的范围十分广泛。尤其在那些编程时间特别紧张的情况下，高性价比的跳跃表很可能会成为你的得力助手。您正为找不到合适的数据结构而感到烦恼吗？您正为自己编写程序的效率高低而感到担忧吗？您正为陷入R-Btree的深渊又无法自拔而感到苦闷吗？朋友！试试跳跃表吧！它将给您的编程带来超高的效率与无尽的快乐！机不可失，时

8、不再来！详情请致电：1381xxxxxxx跳跃表的应用NOI2004Day1郁闷的出纳员（Cashier）抽象题意：要求维护这样一个数据结构，使得它支持以下四种操作：I(x)插入一个值为x元素A(x)现有全体元素加上一个值xS(x)现有全体元素减去一个值xF(i)查找现有元素中第i大的元素值（x为105级别）同时还要保持这样一个性质：现有的元素必须都大于一个特定的值min，小于min的要删去。我们利