跳跃表总结 第1篇
随机函数以概率 1/2^{j} 产生一个新的有j个链接的节点。搜索到正确位置后将对应的链接连上。在到第0层时返回。
随机产生层数：
用i控制层数，j控制概率，每一层的概率减半
插入：
性质：
1.平均情况下，在参数为t的随机化跳跃链表中进行搜素和插入操作需要大约 (tlog_{t}N)/2 次比较。
跳跃表有 log_{t}N 层，每层平均跳过t/2个节点。
2.跳跃表中平均有(t/(t-1))N个链接。
依次计算每层节点个数可得，这引出了时空权衡的问题，由性质1可以计算出当t=e时，期望的搜索次数达到最小。
跳跃表总结 第2篇
随机决策过程：
，否则，执行方案B else do B
由于跳表数据结构整体上是有序的，所以在插入时，需要首先查找到合适的位置，然后就是修改指针（和链表中操作类似），然后更新跳表的level变量。 跳表的插入总结起来需要三步:
比如插入key为25的节点，如下图
实现代码如下:
删除节点操作和插入差不多，找到每层需要删除的位置，删除时和操作普通链表完全一样。不过需要注意的是，如果该节点的level是最大的，则需要更新跳表的level。
删除操作分为以下三个步骤：
删除节点操作和插入差不多，找到每层需要删除的位置，删除时和操作普通链表完全一样。不过需要注意的是，如果该节点的level是最大的，则需要更新跳表的level。
上面分别介绍了跳表的创建、节点插入、节点删除，其中涉及了内存的动态分配，在使用完跳表后别忘了释放所申请的内存，不然会内存泄露的。
1、_ustc/article/details/20218489 2、;q=%E8%B7%B3%E8%A1%A8 3、 4、
跳跃表总结 第3篇
解决了插入之后，我们来看看删除，删除就比较简单了，例如我们要删除4，那我们直接把4及其所跨越的层数删除就行了。
跳跃表的插入与删除至此都讲完了，总结下跳跃表的有关性质：
(1). 跳跃表的每一层都是一条有序的链表.
(2). 跳跃表的查找次数近似于层数，时间复杂度为O(logn)，插入、删除也为 O(logn)。
(3). 最底层的链表包含所有元素。
(4). 跳跃表是一种随机化的数据结构(通过抛硬币来决定层数)。
(5). 跳跃表的空间复杂度为 O(n)。
有人可能会说，也可以采用二叉查找树啊，因为查找查找树的插入、删除、查找也是近似 O(logn) 的时间复杂度。
不过，二叉查找树是有可能出现一种极端的情况的，就是如果插入的数据刚好一直有序，那么所有节点会偏向某一边。例如
这种接结构会导致二叉查找树的查找效率变为 O(n),这会使二叉查找树大打折扣。
红黑可以说是二叉查找树的一种变形，红黑在查找，插入，删除也是近似O(logn)的时间复杂度，但学过红黑树的都知道，红黑树比跳跃表复杂多了，反正我是被红黑树虐过。在选择一种数据结构时，有时候也是需要考虑学习成本的。
而且红黑树插入，删除结点时，是通过调整结构来保持红黑树的平衡，比起跳跃表直接通过一个随机数来决定跨越几层，在时间复杂度的花销上是要高于跳跃表的。
当然，红黑树并不是一定比跳跃表差，在有些场合红黑树会是更好的选择，所以选择一种数据结构，关键还得看场合。
总上所述，维护一组有序的集合，并且希望在查找、插入、删除等操作上尽可能快，那么跳跃表会是不错的选择。redis 中的数据数据便是采用了跳跃表，当然，ridis也结合了哈希表等数据结构，采用的是一种复合数据结构。
代码如下