一直听说跳表这个数据结构，说要学一下的，懒癌犯了，是该治治了
为什么选择跳表
目前经常使用的平衡数据结构有：B树、红黑树，AVL树，Splay Tree（这个树好像还没有听说过），Treep（也没有听说过）等。
想象一下，给你一张草稿纸，一支笔，一个编辑器，你能立即实现一颗红黑树，或者AVL树出来吗？
不好意思，我tmd连冒泡都实现不了......
很难吧，这需要时间，需要考虑很多细节，需要参考一堆算法与数据结构之类的书，还需要参考网上的代码，比较麻烦
用跳表吧，跳表是一种随机化的数据结构，目前开源软件Redis和LevelDB（这是个啥）都有用到它。
他的效率和红黑树不相上下，但跳表的原理相当简单，只要你能熟练操作链表，就能轻松实现一个SkipList。
有序表的搜索
考虑一个有序表
从该表中搜索元素<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 i的链表中，则它在Level i之下的链表也都会出现
5. 每个节点包含了2个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素
跳表的搜索
图中搜索117的过程用红色线画出来的，从上到下已经很明显了，在此不赘述
具体的搜索算法如下：
/* 如果存在x，返回x所在的节点，否则返回x的后继节点 */
find(x) {
p = top;
while (l) {
while (p->next->key < x)
p = p->next;
if (p->down == NULL)
return p->next;
p = p->down;
}
}
跳表的插入
先确定该元素要占据的层数K（采用丢硬币的方式，这完全是随机的）
然后再Level 1 ...... Level K各个层的链表都插入元素
例如，插入119，K=2
如果K大于链表的层数，则要添加新的层。
例如，插入119，K=4
丢硬币决定K
插入元素的时候，元素所占据的层数完全是随机的，通过以下随机算法：
int random_level() {
K = 1;
while (random(0, 1))
K++;
return K;
}
相当于做了一次丢硬币的实验,如果遇到正面，继续丢，遇到反面则停止，】
用实验中丢硬币的次数K作为元素占有的层数。显然随机变量K满足p=1/2的几何分布，K的期望值是E[K] = 1/p = 2。
也就是说，各个元素的层数，期望值是2层。
跳表的高度
n个元素的跳表，每个元素插入的时候都要做一次实验，用来决定元素占据的层数K，跳表的高度等于这n次实验中产生的最大K。
跳表的空间复杂度分析
根据上面的分析，每个元素的期望高度是2，一个大小为n的跳表，其节点数目的期望是2n。
跳表的删除
在各个层中找到包含x的节点，使用标准的delete from list方法删除。
