江苏龙网

  1. 主页 > 生活百科 > >

比红黑树更快的跳表到底是什么数据结构？如何实现？

数据结构


比红黑树更快的跳表到底是什么数据结构？如何实现？

文章插图
 
前言在头条创作了一个月左右的时间，收获了50+粉丝，很是开心，我会把数据结构与算法的文章更新到底，第一次看我文章的同仁如果觉得不错的话就关注一下我哦，你的支持就是我创作的动力 。
 
一、什么是跳表我们在之前介绍了十分优秀的二分查找算法，但是它只能作用于有序数组上，查找起来比较方便，但是数组中插入和删除元素是比较麻烦的；那么有没有办法让二分查找也能作用于有序链表上，从而达到查找、插入和删除元素都十分的快速呢？
对于普通的有序列表来说，当然不能实现我们的目标，如下查找的时间复杂度为O(n)；
比红黑树更快的跳表到底是什么数据结构？如何实现？

文章插图
原始有序单链表
我们可以基于原始链表建立一个 索引层，比如每两个节点提取一个节点到索引层：
比红黑树更快的跳表到底是什么数据结构？如何实现？

文章插图
带一级索引的跳表
如此，两种数据结构我们查找元素16的比较次数分别为10次和8次，确实能提高查询速度；我们更近一步，再次建立第二级索引：
比红黑树更快的跳表到底是什么数据结构？如何实现？

文章插图
带二级索引的跳表 带二级索引的跳表
此时查找元素16比较的次数只需要比较7次即可；
如果在大数据量的有序链表中，我们建立很多层索引，使得最高层索引只有两个节点，那么就实现了类似二分查找的算法思想，此时这种数据结构就被成为跳表 。
二、跳表性能分析2.1 时间复杂度假设有序链表总节点个数为n，我们建立索引时每两个节点提取一个索引节点；那么第一级索引共有n/2个节点；
第k级索引共有（n/2^k）个节点，假设k为最高级索引，为2个节点，那么2=(n/2^k)，n=2(k+1)，k=logn-1，如果原始链表也算进去的话，k=logn正好是整个数据结构的高度 。
假设每一层需要遍历m个节点，那么时间复杂度就可以表示为O(mlogn)，但是推断m是常量级别的，因此可以忽略，那么整个查找过程时间复杂度就是O(logn)，竟然和二分查找是一样的高效！
2.2 空间复杂度第一级索引需要n/2个节点，第二级需要n/2^2个节点，依次类推，第k级索引需要的节点个数为n/2^k，这正好是一个等比数列，等比数列求和的结果是n-2，所以空间复杂度为O(n)，这是一个以空间换时间的策略；
我们可以每3个节点或者每4个节点往上提取一个索引节点，如此可以适当减少需要的额外空间，但是空间复杂度仍然为O(n)；如果有序链表存储的是大对象，那么索引节点中无需存放整个大对象，只要存储对象的指针即可，所以此时空间复杂度就显得不那么重要了；
2.3 跳表的插入和删除跳表因为是顺序链表，所以真正插入和删除的时间复杂度都是O(1)，但是找到需要插入节点的位置或者找到待删除的节点时间复杂度为O(logn)；
跳表在删除的时候，除了需要删除原始有序链表中的节点，还需要同步删除k级索引中的全部该索引节点；
跳表在插入元素式，极端情况下会导致两个索引节点中存在大量的原始节点，时间效率极有可能会退化为单链表的O(n)，所以需要动态地平衡和更新k级索引节点；
三、跳表使用场景redis在存储有序集合的时候就用到了跳表+散列表的数据结构，跳表和红黑树相比，插入、删除、查找的时间复杂度相同，但是跳表在按照区间查找时明显具有效率优势，而且跳表实现起来比红黑树要简单易懂，不容易出错 。
【比红黑树更快的跳表到底是什么数据结构？如何实现？】红黑树等常用数据结构在程序语言中都是封装好的，我们想用的话直接拿来用即可，比如HashMap，但是跳表却没有对应的封装好的数据结构，想用的话开发者必须自己去实现 。
四、代码实现跳表Skiplist以及优化代码来源于极客时间《数据结构和算法之美》
github地址：
https://github.com/wangzheng0822/algo（数据结构和算法必知必会的50个代码实现）
4.1 作者王争给出的跳表实现方式/** * 跳表的一种实现方法 。* 跳表中存储的是正整数，并且存储的是不重复的 。* */public class SkipList {private static final float SKIPLIST_P = 0.5f;private static final int MAX_LEVEL = 16;private int levelCount = 1;private Node head = new Node();// 带头链表public Node find(int value) {Node p = head;for (int i = levelCount - 1; i >= 0; --i) {while (p.forwards[i] != null && p.forwards[i].data < value) {p = p.forwards[i];}}if (p.forwards[0] != null && p.forwards[0].data == value) {return p.forwards[0];} else {return null;}}public void insert(int value) {int level = randomLevel();Node newNode = new Node();newNode.data = value;newNode.maxLevel = level;Node update[] = new Node[level];for (int i = 0; i < level; ++i) {update[i] = head;}// record every level largest value which smaller than insert value in update[]Node p = head;for (int i = level - 1; i >= 0; --i) {while (p.forwards[i] != null && p.forwards[i].data < value) {p = p.forwards[i];}update[i] = p;// use update save node in search path}// in search path node next node become new node forwords(next)for (int i = 0; i < level; ++i) {newNode.forwards[i] = update[i].forwards[i];update[i].forwards[i] = newNode;}// update node hightif (levelCount < level) levelCount = level;}public void delete(int value) {Node[] update = new Node[levelCount];Node p = head;for (int i = levelCount - 1; i >= 0; --i) {while (p.forwards[i] != null && p.forwards[i].data < value) {p = p.forwards[i];}update[i] = p;}if (p.forwards[0] != null && p.forwards[0].data == value) {for (int i = levelCount - 1; i >= 0; --i) {if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {update[i].forwards[i] = update[i].forwards[i].forwards[i];}}}while (levelCount>1&&head.forwards[levelCount]==null){levelCount--;}}// 理论来讲，一级索引中元素个数应该占原始数据的 50%，二级索引中元素个数占 25%，三级索引12.5% ，一直到最顶层 。// 因为这里每一层的晋升概率是 50% 。对于每一个新插入的节点，都需要调用 randomLevel 生成一个合理的层数 。// 该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且 ：//50%的概率返回 1//25%的概率返回 2//12.5%的概率返回 3 ...private int randomLevel() {int level = 1;while (Math.random() < SKIPLIST_P && level < MAX_LEVEL)level += 1;return level;}public void printAll() {Node p = head;while (p.forwards[0] != null) {System.out.print(p.forwards[0] + " ");p = p.forwards[0];}System.out.println();}public class Node {private int data = -1;private Node forwards[] = new Node[MAX_LEVEL];private int maxLevel = 0;@Overridepublic String toString() {StringBuilder builder = new StringBuilder();builder.Append("{ data: ");builder.append(data);builder.append("; levels: ");builder.append(maxLevel);builder.append(" }");return builder.toString();}}}


推荐阅读


上一篇：秋招Android进阶面经，面试10余家经验分享，拿到offer真不难

下一篇：面试让我手写红黑树