SkipList跳表是怎么跳的？

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

什么背景下才诞生的跳表？

哪种数据结构能提供log(n)的检索复杂度，并且能够范围检索？

AVL树（左右子树高度差不超过1，并且左右子树都是AVL树）特点：检索O(logN)，不支持范围检索红黑树（任意一结点到每个叶子结点的路径都包含数量相同的黑结点）特点：检索O(logN)，不支持范围检索B/B+树（多路平衡查找树）特点：检索大于O(logN)，B树不支持范围检索，B+树支持

综上，没有能够提供log(n)的检索复杂度，并且能够范围检索的数据结构。

但是跳表可以！！！

跳表是如何实现log(n)的检索复杂度与范围检索的？

跳表：能够使用二分查找的链表，在检索过程中能够“跳跃式”的检索。

从上图查找26的过程可以看出，既然能够二分查找，那么检索效率为log(n)。又因为是链表，只需要检索区间两端，就可以实现范围检索。

跳表节点的数据结构是怎样的？

看一个数据结构怎么实现的，首先要看它的每个节点是如何定义的。

链表的节点：存储val值，和指向下一个节点的指针。由此构建成链表。

树的节点：存储val值，和指向左子树的left指针，以及指向右子树的right指针，由此构建成一棵二叉树。

跳表节点：存储val值，和一个指针数组。

那么问题来了：指针数组中的每一个指针都指向了哪里？如何构建成一个跳表的？

跳表是怎么跳的？

还是从这张跳表图说起。以下图中紫色节点为例，这个节点包含一个val值为7，以及一个长度为4的指针数组。指针数组中的指针从下至上依次指向了不同的节点。

如果把指针数组的长度看成层级（level），从下至上，一共有个4个层级，且最高层级为4。

紫色节点的第四层级指向了null，第三层级指向了粉红色节点（val为37），粉红色节点的第三层级指向了null。

跳表，相对于顺序遍历的链表可以实现跳跃。检索时候的跳跃发生在每一层级的匹配，如果小于当前值，会进行下一跳。综上，已经大概描述了跳表的结构。将指针数组的长度作为层级，指针数组长度最长的为最大层级。每个节点在相同层级就是一个完整的链表。

到这里，基本上描述了跳表的由来，节点的数据结构，以及跳表的表示方式，如果想知道add、search、erase的时候是如何操作的，请看后面的代码解析。

实现一个跳表

最枯燥的就是源码解析，不知道用什么方式来描述。还是直接上代码吧。。。。show me code。​​详细代码在此​​

跳表节点的数据结构

class SkiplistNode { int val; SkiplistNode[] forward; public SkiplistNode(int val, int maxLevel) { this.val = val; this.forward = new SkiplistNode[maxLevel]; }

跳表节点：存储（val）和指针数组

初始化

public Skiplist() { this.head = new SkiplistNode(-1, MAX_LEVEL); this.level = 0; this.random = new Random(); }

初始化一个跳表，head表示头结点，不存储任何东西，仅仅用来表示头结点。

随机创建的层级

private static int randomLevel() { int lv = 1; /* 随机生成 lv */ while (random.nextDouble() < P_FACTOR && lv < MAX_LEVEL) { lv++; } return lv; }

节点往跳表中插入的时候，需要随机创建一个层级。add节点的时候会使用，目的是将每个节点的层级更加分散，随机。

add节点

public void add(int num) { //update用来记录每个层级中小于num的最大值的节点 SkiplistNode[] update = new SkiplistNode[MAX_LEVEL]; Arrays.fill(update, head);//填充 SkiplistNode curr = this.head;//遍历指针 for (int i = level - 1; i >= 0; i--) { //从上至下遍历 //循环的目的是找到每个层级中小于num的最大值的节点，并记录在update中 while (curr.forward[i] != null && curr.forward[i].val < num) { curr = curr.forward[i]; } update[i] = curr;//使用update记录下来 } int lv = randomLevel();//随机生成一个层级 level = Math.max(level, lv);//最大层级 SkiplistNode newNode = new SkiplistNode(num, lv);//创建一个指针数组为lv（层级为lv）的节点 for (int i = 0; i < lv; i++) {//按照节点的指针数组长度（随机生成的层级）遍历 //以下两步是将newNode的第i个指针插入跳表中 newNode.forward[i] = update[i].forward[i];//newNode的第i个指针指向，大于num的最小值（update中记录的是小于num的最大值的节点） update[i].forward[i] = newNode;//插入 } }

add代码比较绕，也是比较核心的部分

问自己以下几个问题，review一下。

update中记录的是什么？

update和newNode中指针数组的长度是否相同？

erase节点

public boolean erase(int num) { //update用来记录每个层级中小于且最接近num的最大值的节点 SkiplistNode[] update = new SkiplistNode[MAX_LEVEL]; SkiplistNode curr = this.head; for (int i = level - 1; i >= 0; i--) { //找到第 i 层小于且最接近 num 的元素 while (curr.forward[i] != null && curr.forward[i].val < num) { curr = curr.forward[i]; } //记录下来 update[i] = curr; } //cur表示第一层小于且最接近num的节点 curr = curr.forward[0]; //如果值不存在则返回 false if (curr == null || curr.val != num) { return false; } for (int i = 0; i < level; i++) { if (update[i].forward[i] != curr) { break; } // 对第 i 层的状态进行更新，将 forward 指向被删除节点的下一跳 update[i].forward[i] = curr.forward[i]; } // 更新当前的 level while (level > 1 && head.forward[level - 1] == null) { level--; } return true; }

这里问自己几个问题

为什么curr这个临时变量，在第一层级的时候，指向谁？update中指针数组记录的什么？

search

public boolean search(int target) { SkiplistNode curr = this.head; for (int i = level - 1; i >= 0; i--) { /* 找到第 i 层小于且最接近 target 的元素*/ while (curr.forward[i] != null && curr.forward[i].val < target) { curr = curr.forward[i]; } } curr = curr.forward[0]; /* 检测当前元素的值是否等于 target */ if (curr != null && curr.val == target) { return true; } return false; }

searh比较简单些。

能够提供帮助的文档

​​程序员小灰-什么是跳表​​

​​跳表实现LeetCode ​​

​​跳表的研究论文​​

​​跳表原理以及优缺点​​

​​二叉树可视化​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。