跳表是一种随机化的数据结构，目前开源软件Redis和LevelDB都有用到它，它的效率和红黑树以及AVL树不相上下：
考虑一个有序表：
从该有序表中搜索元素< 23, 43, 59 >，需要比较的次数分别为< 2, 4, 6 >，总共比较的次数为2 + 4 + 6 = 12次。有没有优化的算法吗?链表是有序的，但不能使用二分查找。类似二叉搜索树，我们把一些节点提取出来，作为索引。得到如下结构：
这里我们把< 14, 34, 50, 72 >提取出来作为一级索引，这样搜索的时候就可以减少比较次数了。
我们还可以再从一级索引提取一些元素出来，作为二级索引，变成如下结构：
跳表结构：
-1表示INT_MIN,链表的最小值
1表示INT_MAX,链表的最大值。
跳表具有如下性质：
(1)由很多层结构组成
(2)每一层都是一个有序的链表
(3)最底层(Level 1)的链表包含所有元素
(4)如果一个元素出现在Level(x)的链表中，则它在Level(x-n)的链表中也都会出现。
(5)每个节点包含两个指针，一个指向下一个元素，一个指向下面一层的元素
跳表的搜索
例子：查找元素117
(1)比较21，比21大，往后面找
(2)比较37,比37大，比链表最大值小，从37的下面一层开始找
(3)比较71,比71大，比链表最大值小，从71的下面一层开始找
(4)比较85，比85大，从后面找
(5)比较117，等于117，找到了节点。
跳表的插入
先确定该元素要占据的层数K（采用丢硬币的方式，这完全是随机的）
然后在Level 1 ...
Level K各个层的链表都插入元素。
例子：插入119，K = 2
如果K大于链表的层数，则要添加新的层。
例子：插入119，K = 4
丢硬币决定K
插入元素的时候，元素所占有的层数完全是随机的，通过一下随机算法产生：
相当与做一次丢硬币的实验，如果遇到正面，继续丢，遇到反面，则停止，
用实验中丢硬币的次数K作为元素占有的层数。显然随机变量K满足参数为p = 1/2的几何分布，
K的期望值E[K] = 1/p = 2.就是说，各个元素的层数，期望值是2层。
跳表的删除
在各个层中找到包含x的节点，使用标准的delete from list方法删除该节点。
例子：删除71
java实现:
网友评论