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

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

1、华东师范大学第二附属中学魏冉让算法的效率“跳起来”！——浅谈“跳跃表”的相关操作及其应用上海市华东师范大学第二附属中学魏冉【目录】◆关键字························································································【2】◆摘要························································································【2】◆概述及结构················

2、··································································【2】◆基本操作·························································································【3】◇查找··················································································【3】◇插入···················

3、·······························································【3】◇删除··················································································【4】◇“记忆化”查找·····································································【5】第16页华东师范大学第二附属中学魏冉◆复杂度分析··················

4、································································【6】◇空间复杂度分析······································································【7】◇跳跃表高度分析······································································【7】◇查找的时间复杂度分析····································

5、·····················【7】◇插入与删除的时间复杂度分析··················································【8】◇实际测试效果·····································································【8】◆跳跃表的应用············································································【9】◆总结·················

6、········································································【10】◆附录·························································································【11】第16页华东师范大学第二附属中学魏冉【关键字】跳跃表高效概率随机化【摘要】本文分为三大部分。首先是概述部分。它会从功能、效率等方面对跳跃表作一个初步的介绍，并给出其图形结构，以便读者对跳跃表有个形象的认识。第

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

8、gn),有着近乎替代平衡树的本领。而且最重要的一点，就是它的编程复杂度较同类的AVL树，红黑树等要低得多，这使得其无论是在理解还是在推广