分类导航

数据结构与算法(c++)——跳跃表(skip list)

发布时间：2017年05月08日作者： IT网络文摘 (该文来自笔记，点击查看原文)

今天要介绍一个这样的数据结构：

——跳跃表 Skip List

一、普通链表

移动开发培训,Android培训,安卓培训,手机开发培训,手机维修培训,手机软件培训

对于普通链接来说，越靠前的节点检索的时间花费越低，反之则越高。而且，即使我们引入复杂算法，其检索的时间花费依然为O(n)。为了解决长链表结构的检索问题，一位名叫William Pugh的人于1990年提出了跳跃表结构。基本思想是——以空间换时间。

二、简单跳跃表（Integer结构）

跳跃表的结构是多层的，通过从最高维度的表进行检索再逐渐降低维度从而达到对任何元素的检索接近线性时间的目的O(logn)。