20 张图击溃，跳表！

跳跃链表及其应用是非常热门的问题，面试时也非常常问，深入了解其中奥秘大有裨益，不吹了，直接开始！

跳跃链表的基本概念

初识跳表

跳跃列表是一种数据结构。它允许快速查询一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(log n)，优于普通队列的O(n)。

跳跃列表由威廉·普发明，发明者对跳跃列表的评价：跳跃链表是在很多应用中有可能替代平衡树而作为实现方法的一种数据结构。

跳跃列表的算法有同平衡树一样的渐进的预期时间边界，并且更简单、更快速和使用更少的空间。

这种数据结构是由William Pugh(音译为威廉·普)发明的，最早出现于他在1990年发表的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。

我在谷歌上找到一篇作者关于跳表的论文，感兴趣强烈建议下载阅读：

https://epaperpress.com/sortsearch/download/skiplist.pdf

看下这篇论文的摘要部分：

从中我们获取到的信息是：跳表在动态查找过程中使用了一种非严格的平衡机制来让插入和删除都更加便利和快捷，这种非严格平衡是基于概率的，而不是平衡树的严格平衡。

说到非严格平衡，首先想到的是红黑树RbTree，它同样采用非严格平衡来避免像AVL那样调整树的结构，这里就不展开讲红黑树了，看来跳表也是类似的路子，但是是基于概率实现的。

动态查找的数据结构

所谓动态查找就是查找的过程中存在元素的删除和插入，这样就对实现查找的数据结构有一定的挑战，因为在每次删除和插入时都要调整数据结构，来保持秩序。

可以作为查找数据结构的包括：

• 线性结构：数组、链表
• 非线性结构：平衡树

来分析一下各种数据结构在应对动态查找时的优劣吧！

数组结构

数组结构简单内存连续，可以实现二分查找等基于下标的操作，我一直认为数组的杀手锏就是下标，连续的内存也带来了问题。

当进行插入和删除时就面临着整体的调整，就像在火车站排队买票，队头走一个整个队伍向前挪一步，有加塞的后面的又整体向后挪一步，这种整体移动操作在数组结构中性能损耗很大，并且在大数据量时对连续内存要求很高，当然这个在大内存机器上可能没有什么问题。

如图插入6和删除5时 数组元素的移动：

链表结构

链表结构也比较简单，但是不要求内存连续，不连续也就没有下标可以加速，但是链表在执行删除和插入时影响的只是插入删除点的前后元素，影响非常小。

但是每次查找元素是需要进行遍历，就算我知道某个元素一定在大致的什么位置，也只能一步步走过去，看到这里要觉得有优化的空间，那你也蛮厉害的了，说不定早几年跳表就是你的发明了。

如图删除元素5和插入元素49时的处理：

平衡树

平衡树也是处理动态查找问题的一把好手，树一般是基于链表实现的，只不过树的节点之间并不是链表简单的线性关系，会有兄弟姐妹父亲等节点，并且各个层级有数量的限制，可以看到树其实还是蛮复杂的。

节点需要存储的信息很多，各个指针指来指去，复杂的结构增加了调整平衡性的难度，不同情况下的左旋右旋，所以出现了红黑树这种工程版本的AVL，但是在实际场景中可能并不需要这些兄弟姐妹父亲关系，有种杀鸡宰牛刀的意味了。

红黑树的节点结构定义：

#define COLOR_RED  0x0
#define COLOR_BLACK 0x1

typedef struct RBNode{
   int key;
   unsigned char color;
   struct RBNode *left;
   struct RBNode *right;
   struct RBNode *parent;
}rb_node_t, *rb_tree_t;
另外红黑树调整属性过程中插入分为3种情况，删除分为4种情况，还是比较难以理解的，除非你穿红上衣