跳表-披着链表外衣的伪搜索树

本文参考资源:

【数据结构与算法】之跳表(Java实现)---第九篇Java震哥聊校招-CSDN博客

跳表的原理及实例 - Rogn - 博客园

跳表Java实现Java偏离的定弦-CSDN博客

跳表概述

如果说某一种数据结构能达到以logn的速度查找数据,相信大多数人第一反应都是二分查找或是搜索树。

对于二分查找来说,它通常是一个有序数组,虽然查找效率达到了logn,但插入效率要么就是数组不允许插入,要么就是arraylist为logn。

对于搜索树,则必须要是自平衡的搜索树才能在插入了很多数据之后依然保持logn的查找效率,这就要求插入涉及到旋转平衡操作,实现较复杂。

而我们今天要介绍的主角——跳表,相较于红黑树、AVL等自平衡搜索树的实现会更简单些,查找效率和插入效率也都达到了logn。

跳表的性质

  1. 由很多层结构组成,level是通过一定的概率随机产生的
  2. 每一层都是一个有序的链表,默认是升序
  3. 最底层(Level 1)的链表包含所有元素;
  4. 如果一个元素出现在Level i 的链表中,则它在Level i 之下的链表也都会出现; 
  5. 每个节点包含两个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素。

跳表原理

用图片形式来理解跳表:

跳表-披着链表外衣的伪搜索树

如下图,对初始链表做一层“索引”,每两个节点提取一个节点到上一层,然后用down指针连接到下一层。

跳表-披着链表外衣的伪搜索树

现在我们查询16这个节点。从第一级索引开始,找到13,并且下一个为17,显然16在这两个节点之间,利用down指针下降一层,这次我们遍历2次即可。利用索引后,遍历了5+2=7次,而原始链表需要10次,这里加一层索引遍历次数减少了,效率提高了一点,但还不够,我们继续往上添加索引层。

跳表-披着链表外衣的伪搜索树

这里我不再算了,结果是6次,效率又提高了!

那么这种链表加多级索引就是跳表的结构了。可以看出来最后形成的就是一个类似于搜索树的结构。

跳表的操作

Java中已经有了跳表思想的实现:concurrent包下的ConcurrentSkipListMap(在功能上对应HashTable、HashMap、TreeMap)和 ConcurrentSkipListSet(在功能上对应HashSet)。

跳表的插入

跳表插入的时间复杂度为:O(logn),支持高效的动态插入。

在单链表中,一旦定位好要插入的位置,插入结点的时间复杂度是很低的,就是O(1)。但是为了保证原始链表中数据的有序性,我们需要先找到要插入的位置,这个查找的操作就会比较耗时。

对于纯粹的单链表,需要遍历每个结点,来找到插入的位置。但是对于跳表来说,查找的时间复杂度为O(logn),所以这里查找某个数据应该插入的位置的时间复杂度也是O(logn),如下图所示:

跳表-披着链表外衣的伪搜索树

跳表的删除

跳表的删除操作时间复杂度为:O(logn),支持动态的删除。

在跳表中删除某个结点时,如果这个结点在索引中也出现了,我们除了要删除原始链表中的结点,还要删除索引中的。因为单链表中的删除操作需要拿到删除结点的前驱结点,然后再通过指针操作完成删除。所以在查找要删除的结点的时候,一定要获取前驱结点(双向链表除外)。因此跳表的删除操作时间复杂度即为O(logn)。

跳表索引动态更新

当我们不断地往跳表中插入数据时,我们如果不更新索引,就有可能出现某2个索引节点之间的数据非常多的情况,在极端情况下,跳表还会退化成单链表,如下图所示:

跳表-披着链表外衣的伪搜索树

作为一种动态数据结构,我们需要某种手段来维护索引与原始链表大小之间的平衡,也就是说,如果链表中的结点多了,索引结点就相应地增加一些,避免复杂度退化,以及查找、插入和删除操作性能的下降。

如果你了解红黑树、AVL树这样的平衡二叉树,你就会知道它们是通过左右旋的方式保持左右子树的大小平衡,而跳表是通过随机函数来维护“平衡性”。

当我们往跳表中插入数据的时候,我们可以通过一个随机函数,来决定这个结点插入到哪几级索引层中,比如随机函数生成了值K,那我们就将这个结点添加到第一级到第K级这个K级索引中。如下图中要插入数据为6,K=2的例子:

跳表-披着链表外衣的伪搜索树

随机函数的选择是非常有讲究的,从概率上讲,能够保证跳表的索引大小和数据大小平衡性,不至于性能的过度退化。至于随机函数的选择,见下面的代码实现过程,而且实现过程并不是重点,掌握思想即可。

跳表的Java实现

// 跳表中存储的是正整数,并且存储的数据是不重复的
public class SkipList {

    private static final int MAX_LEVEL = 16;    // 结点的个数

    private int levelCount = 1;   // 索引的层级数

    private Node head = new Node();    // 头结点

    private Random random = new Random();

    // Node内部类
    public class Node{
        private int data = -1;
        private Node next[] = new Node[MAX_LEVEL];
        private int maxLevel = 0;

        // 重写toString方法
        @Override
        public String toString(){
            StringBuilder builder = new StringBuilder();
            builder.append("{data:");
            builder.append(data);
            builder.append("; leves: ");
            builder.append(maxLevel);
            builder.append(" }");
            return builder.toString();
        }
    }

    // 查找操作
    public Node find(int value){
        Node p = head;
        for(int i = levelCount - 1; i >= 0; --i){
            while(p.next[i] != null && p.next[i].data < value){
                p = p.next[i];
            }
        }

        if(p.next[0] != null && p.next[0].data == value){
            return p.next[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;
        }

        Node p = head;
        for(int i = level - 1; i >= 0; --i){
            while(p.next[i] != null && p.next[i].data < value){
                p = p.next[i];
            }
            update[i] = p;
        }

        for(int i = 0; i < level; ++i){
            newNode.next[i] = update[i].next[i];
            update[i].next[i] = newNode;
        }
        if(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.next[i] != null && p.next[i].data < value){
                p = p.next[i];
            }
            update[i] = p;
        }

        if(p.next[0] != null && p.next[0].data == value){
            for(int i = levelCount - 1; i >= 0; --i){
                if(update[i].next[i] != null && update[i].next[i].data == value){
                    update[i].next[i] = update[i].next[i].next[i];
                }
            }
        }
    }

    // 随机函数
    private int randomLevel(){
        int level = 1;
        for(int i = 1; i < MAX_LEVEL; ++i){
            if(random.nextInt() % 2 == 1){
                level++;
            }
        }

        return level;
    }

    // 显示跳表中的结点
    public void display(){
        Node p = head;
        while(p.next[0] != null){
            System.out.println(p.next[0] + " ");
            p = p.next[0];
        }
        System.out.println();
    }

}

跳表的应用

  • Lucene3.0版本之前使用跳表结构存储词典,后来换成了FST(有限状态转移机)
  • Redis在两个地方用到了跳跃表,一个是实现有序集合键,另一个是在集群节点中用作内部数据结构。
  • ……

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e8%b7%b3%e8%a1%a8-%e6%8a%ab%e7%9d%80%e9%93%be%e8%a1%a8%e5%a4%96%e8%a1%a3%e7%9a%84%e4%bc%aa%e6%90%9c%e7%b4%a2%e6%a0%91/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年3月27日 20:46
下一篇 2020年3月28日

相关推荐

  • leetcode706-设计哈希映射

    原题 不使用任何内建的哈希表库设计一个哈希映射 具体地说,你的设计应该包含以下的功能 put(key, value):向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在,更…

    算法 2019年12月18日
    0120
  • AVL树-自平衡的二叉搜索树

    本文图片来源:手把手教,手写AVL树 - 不止是编程 - 博客园 AVL树的概念 自平衡 当二叉搜索树处于平衡状态的时候,其操作时间复杂度为O(logN),但当二叉搜索树是单支树的…

    2019年11月25日
    0430
  • leetcode232-用栈实现队列

    原题 使用栈实现队列的下列操作: push(x) – 将一个元素放入队列的尾部。 pop() – 从队列首部移除元素。 peek() – 返回队列首部的元素。 empty() – …

    算法 2019年12月13日
    0560
  • leetcode707-设计链表

    原题 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:val 和 next。val 是当前节点的值,next 是指向下一个节点的指针/引用。如果要使用…

    算法 2019年12月14日
    0290
  • 拉帮结派的数据结构-并查集

    本文参考资源: 超超有爱爱-----并查集~~~chen_zan_yu的博客-CSDN博客 概述 并查集通常用作集合的合并。 并查集是一种树形结构,又叫“不相交集合”,保持了一组不…

    2020年2月17日
    0140
  • leetcode622-设计循环队列

    设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是…

    算法 2019年11月24日
    0130
  • leetcode225--用队列实现栈

    原题 使用队列实现栈的下列操作: push(x) – 元素 x 入栈 pop() – 移除栈顶元素 top() – 获取栈顶元素 empty() – 返回栈是否为空 注意: 你只能…

    算法 2019年12月13日
    0120
  • 多叉平衡查找树-B树与B+树

    本文参考链接: 从B树、B+树、B*树谈到R 树_磁盘,数据结构,存储_结构之法 算法之道-CSDN博客 【数据结构】B树、B+树详解 - Assassinの - 博客园 BTre…

    2020年2月8日
    0160
  • leetcode385-迷你语法分析器

    原题 给定一个用字符串表示的整数的嵌套列表,实现一个解析它的语法分析器。 列表中的每个元素只可能是整数或整数嵌套列表 提示: 你可以假定这些字符串都是格式良好的: 字符串非空 字符…

    算法 2020年1月28日
    02260
  • 算法竞赛常用数据结构-字典树Trie

    本文参考资源: 详谈树结构(传统树、字典树、hash 树、Merkle Patricia Tree)_C/C++_smilejiasmile的博客-CSDN博客 概述 Tire树称…

    2020年2月17日
    0670

发表回复

登录后才能评论