《论文_算法合集之《浅谈“跳跃表”的相关操作及其应用》(定稿)》

《《论文_算法合集之《浅谈“跳跃表”的相关操作及其应用》(定稿)》》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、让篇號的数率“魏超東”/嵌谡“眺块彖”的相关操作及其盜用上海市华东师范大学第二附属中学魏冉【目录】♦关键字[2]♦摘要[2]♦概述及结构【2】♦基本操作【3】O查找【3】O插入【3】O删除【4】◊“记忆化”查找【5】♦复杂度分析【6】◊空间复杂度分析【7】O跳跃表高度分析【7】O查找的时间复杂度分析【7】O插入与删除的时间复杂度分析【8】O实际测试效果【8】♦跳跃表的应用【9】♦总结【10】♦P付录[11]【关键字】跳跃表高效概率随机化【摘要】本文分为三大部分。首先是概述部分。它会从功能、效率等方而对跳跃表作一个

2、初步的介绍，并给出其图形结构，以便读者对跳跃表冇个形象的认识。第二部分将介绍跳跃表的三种基本操作一一查找，插入和删除，并对它们的时空复杂度进行分析。第三部分是对跳跃表应用的介绍，并通过实际测试效果来对跳跃表以及其它一些相关数据结构进行対比，体现其各白的优缺点。最后一部分是对跳跃表数据结构的总结。【概述及结构】二义树是我们都非常熟悉的一种数据结构。它支持包括查找、插入、删除等一系列的操作。但它有一个致命的弱点，就是当数据的随机性不够时，会导致其树型结构的不平衡，从而直接影响到算法的效率。跳跃表（SkipList）是

3、1987年才诞生的一种崭新的数据结构，它在进行查找、插入、删除筹操作时的期望时间复杂度均为O（logn）,有着近乎替代平衡树的本领。而且最重要的一点，就是它的编程复杂度较同类的AVL树，红黑树等要低得多，这使得其无论是在理解还是在推广性上，都有着十分明显的优势。首先，我们来看一下跳跃表的结构（如图1）S2SoS3V序排列图1仃7个元索的跳跃表（2）So包含所有的元素，'（3）每条链中的元素集合必狈巴曰丁疗釵叔勺、1丹墟li、J元素集合，即:【基本操作】在对跳跃表冇一个初步的认识以后，我们来看一下基于它的几个最基本

4、的操作。―、查找目的：在跳跃表中查找一个元素X在跳跃表中查找一个元素X,按照如下儿个步骤进行：i)从最上层的链(SQ的开头开始ii)假设当前位置为P，它向右指向的节点为q(P与q不一定和邻)，Rq的值为y。将y与x作比较(1)x二y输出查询成功及相关信息(2)x>y从p向右移动到q的位置(3)x

5、IIR确、业hill3045+853中帚一Q1皆出好右137Ek、I"亠3、:及它的“高度”。图2查询元素53的全过程关于插入的位置，我们先利用叽叭衣口、j旦代七川匕，x小的最大的数y°根据跳跃-002930上的连续一段元素。冇两个参痂*"亠+oo53表中所有链均是递增序列的原则，X必然就插在y的厉而。而插入列的“高度”较前者来说显得更加垂要，也更加难以确定。由于它的不确定性,使得不同的决策可能会导致截然不同的算法效率。为了使插入数据Z后，保持该数据结构进行各种操作均为0(logn)复杂度的性质，我们引入随机化算

6、法(RandomizedAlgorithms)□我们定义一个随机决策模块，它的大致内容如卞:r—random()ifr

7、，如果得到的i比当前跳跃表的高度h还要大的话，则需要增加新的链，使得跳跃表仍满足先前所提到的条件。我们来看一个例了：假设当前我们要插入元索“40”，且在执行了随机决策模块后得到高度为4•步骤-：找到表中比40小的最大的数，确定插入位置插入的位置S2■8So-cc153(-：插入高度为4的列,3(293374553+0053+0045S2SiSo■co口口k301529(2)30从跳跃表中删除一个元系A[I——爲苗i算如艇4040JM30将该元玄所在黑图3.2插入汩j丿殳为4的列，并纟隹护跳跃表+84553+004

8、5J11J53+00贝53+004040将多余的“空链”删除-00152937+00图4.2删除以后的结构四、“记忆化"查找（Searchwithfingers）所谓“记忆化”查找，就是在询一次查找的基础上进行进一步的查找。它可以利用前一次查找所得到的信息，取其中可以被当前查找所利用的部分。利用'‘记忆化”査找可以将一次查找的复杂度变为O（logk）,其中k为此次与前一次