浅谈“跳跃表”的相关操作及其应用

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

1、社篇该的致車“馳起来”/——嵌後“馳跃素”的相矣絲作及曳疹用上海市华东师范人学第二附属中学魏冉【目录】♦关键字[2]♦摘要[2]♦概述及结构【2】♦基本操作[3]O查找[3]◊插入【3】◊删除[4]◊“记忆化”查找【5】♦复杂度分析[6]O空间复杂度分析[7]O跳跃表高度分析【7】O查找的时间复杂度分析【7】O插入与删除的时间复杂度分析[8]O实际测试效果[8]♦跳跃表的应用[91♦总结【10】♦附录[11]【关键字】跳跃表高效概率随机化【摘要】本文分为三大部分。首先是概述部分。它会从功能、效率等方面对跳跃表作一个初步的介绍，并给出英图形结构，以便读者对跳跃表冇个形象的认

2、识。第二部分将介绍跳跃表的三种基本操作一一查找，插入和删除，并对它们的时空复杂度进行分析。笫三部分是对跳跃表应川的介绍，并通过实际测试效果來对跳跃表以及其它一些相关数据结构进行対比，体现其各口的优缺点。最后一部分是对跳跃表数据结构的总结。【概述及结构】二叉树是我们都非常熟悉的一种数据结构。它支持包括查找、插入、删除等一系列的操作。但它有一个致命的弱点，就是当数据的随机性不够时，会导致其树型结构的不平衡，从而直接影响到算法的效率。跳跃表(SkipList)是1987年才诞生的一种崭新的数据结构,它在进行查找、插入、删除等操作时的期望时间复杂度均为O(logn),有着近乎替代

3、平衡树的木领。而且最重要的一点，就是它的编程复杂度较同类的AVL树，红黑树等要低得多，这使得其无论是在理解述是在推广性上，都有着十分明显的优势。首先，我们來看一下跳跃表的结构(如图1)跳跃表由多条链构成（S。，ShS2……，Sh）,且满足如下三个条件：（1）每条链必须包含两个特殊元素：+00和-00（2）So包含所有的元素，并且所有链中的元素按照升序排列。（3）每条链中的元素集合必须包含于序数较小的链的元素集合，即:【基本操作】在对跳跃表有一个初步的认识以后，我们來看一下基于它的几个最基本的操作。查找目的：在跳跃表中查找一个元素X在跳跃表中查找一个元素X,按照如下几个步骤

4、进行：i）从最上层的链（SQ的开头开始ii）假设当前位置为P，它向右指向的节点为q（P与q不一定相邻），且q的值为y。将y与X作比较（1）X=y输'\'查询成功及相关信息（2）x>y从p向右移动到q的位置（3）x

5、跃表的查找功能，找到比x小的最大的数y。根据跳跃衣中所有链均是递增序列的原则，x必然就插在y的后面。而插入列的“高度”较前者来说显得更加重要，也更加难以确定。由于它的不确定性,使得不同的决策可能会导致截然不同的算法效率。为了使插入数据Z片，保持该数据结构进行各种操作均为0(logn)复杂度的性质，我们引入随机化算法(RandomizedAlgorithms).,我们定义一个随机决策模块，它的大致内容如下：r—random()ifr

6、地执行随机决策模块。如果耍求执行的是A操作，则将列的高度加1，并且继续反复执行随机决策模块。直到第i次，模块要求执行的是B操作，我们结束决策，并向跳跃表中插入一个髙度为i的列。性质1：根据上述决策方法，该列的高度大于等于k的概率为pi。此处有一个地方需耍注意，如果得到的i比当前跳跃表的高度h还耍大的话，则需耍增加新的链，使得跳跃衣仍满足先前所提到的条件。我们来看一个例子：假设当前我们要插入元素“40”，H在执行了随机决策模块后得到高度为4•步骤-：找到表中比40小的最大的数，确定插入位置•步骤二：插入高度为4的列，并维护跳跃表的结构三、删除目的：从跳跃表中删除一个元素x删

7、除操作分为以下三个步骤：（1）在跳跃表屮查找到这个元素的位置，如果未找到，则退出*（2）将该元素所在整列从表中删除*（3）将多余的“空链”删除*SiSo1111II535330304553图4.1删除元•素11的全过程+oo四.“记忆化”查找（Searchwithfingers）所谓“记忆化”查找，就是在前一次查找的基础上进行进一步的查找。它可以利用前一次查找所得到的信息，取其中可以被当前查找所利用的部分。利用“记忆化”查找可以将一次查找的复杂度变为O（logk）,其中k为此次与前一次两个被査找元素在跳跃表中位置的距离。下面來