资讯专栏INFORMATION COLUMN

数据结构之跳跃链表

yiliang / 2701人阅读

摘要:从这里我们可以看到,从插入时我们只要保证上一层的元素个数为下一层元素个数的,我们的跳跃表就能成为理想的跳跃表。

数据结构之跳跃链表 简介

总的来说跳跃链表最大的好处就是提高了检索了的速率,可以说说是大幅度的提高,相对于单链表来说是一种高效率的检索结构

原理

跳跃表的结构是:假如底层有10个节点, 那么底层的上一层理论上就有5个节点,再上一层理论上就有2个或3个节点,再上一层理论上就有1个节点。所以从这里可以看出每一层的节点个数为其下一层的1/2个元素,以此类推。从这里我们可以看到,从插入时我们只要保证上一层的元素个数为下一层元素个数的1/2,我们的跳跃表就能成为理想的跳跃表。那么怎么才能保证我们插入时上层元素个数是下层元素个数的1/2呢,?很简单 抛硬币就可以解决了,假设元素X要插入跳跃表,最底层是肯定要插入X的,那么次低层要不要插入呢,我们希望上层元素个数是下层的1/2,那么我们有1/2的概率要插入到次低层,这样就来抛硬币吧,正面就插入,反面就不插入,次次底层相对于次低层,我们还是有1/2的概率插入,那么就继续抛硬币吧 , 以此类推元,素X插入第n层的概率是(1/2)的n次。这样,我们能在跳跃表中插入一个元素了。基本的样子如下图:

代码实现(java语言) 节点定义
package skip;

public class Node
{
    public Integer value;    //插入的数据
    public Node left;     //分别对应的四个方向的指针
    public Node down;
    public Node right;
    public Node up;
    public Node(Integer value)   //构造函数
    {
        this.value=value;
        down=up=right=left=null;
    }
}
表的实现
package skip;
import java.util.Random;

public class SkipList {
    private Node head;   //最上面一侧的头结点,这里使用的是双链表
    private Node tail;   //最上面一层的尾节点,这里的头尾节点是不存储数据的,数据域全是null
    private int level;    //表中的最高的层数,就是总共的层数
    private int size;    //插入节点的个数,头尾节点除外
    private Random random;   //用来判断是否需要增加高度的随机函数

    public SkipList() {
        level = 0;     //level默认是0层,就是只有最下面的一层
        head = new Node(null);
        tail = new Node(null);
        head.right = tail;    //这里初始化成一个只有一层的双链表
        tail.left = head;
        size = 0;     //size初始化为0
        random = new Random();
    }

    //这个函数的作用是找到插入节点的前面一个节点,这里默认的是将表升序存储
    public Node findFirst(Integer value) {
        Node p = head;
        while (true) {
            //判断要插入的位置,当没有查到尾节点并且要插入的数据还是比前面的大的话,就将节点右移,知道找到合适的位置
            //这里需要注意的是这里的head代表不一定是最底层的,因此这里的查找都是从最高层进行查找的,如果满足条件就要向下移动
            //直到最底层
            while (p.right.value != null && p.right.value <= value) {
                p = p.right;
            }

            //向下移动,直到到达最后一层
            if (p.down != null) {
                p = p.down;
            } else {   //到达最底层跳出即可
                break;
            }
        }
        return p;  //此时这里的p就是要插入节点的前面一个节点
    }

    //这是插入函数,这里先执行插入,然后判断是否需要增加高度
    public void insert(int value) {
        Node curr = findFirst(value);  //先找到插入位置的前面一个节点

        Node q = new Node(value);   //新建一个插入的节点

        //下面执行插入步骤,这个和双链表是一样的步骤
        q.right = curr.right;
        q.left = curr;
        curr.right.left = q;
        curr.right = q;

        int i = 0;   //表示当前节点所在的层数,开始插入的是在下面插入的,所以开始的时候是在0层

        //这里判断是否需要增加高度,每一层相对域下面来说都有二分之一的概率,也就是说每一层增加的概率是(1/2)^n
        //通俗的说就是每一层的节点是将会保证是下面一层的1/2
        while (random.nextDouble() < 0.5) {
            if (i >= level) {   //如果当前插入的节点所处的层数大于等于最大的层数,那么就需要增加高度了,因为这里要保证头尾节点的高度是最高的

                //下面的代码就是在头尾节点的上插入新的节点,以此来增加高度
                Node p1 = new Node(null);
                Node p2 = new Node(null);

                p1.right = p2;
                p1.down = head;

                p2.left = p1;
                p2.down = tail;

                head.up = p1;    //将头尾节点上移,成为最顶层的节点,这就是为什么每次插入和查询的时候都是最上面开始查询的,因为这里的head默认的就是从最上面开始的
                tail.up = p2;

                head = p1;
                tail = p2;
                level++;    //最高层数加一
            }

            while (curr.up == null) {    //当然增加高度就是在插入节点上面新插入一个节点,然后将之与插入的节点相连
                //既然这里新插入节点增高了,那么就需要找到与新插入节点上面的那个节点相连接,这里我们将新插入节点的前面的同等高度的节点与之相连
                curr = curr.left;
            }

            curr = curr.up;    //通过前面的一个节点找到与之相连的节点


            //下面就是创建一个节点插入到插入节点的头上以此来增加高度,并且这个节点与前面一样高的节点相连
            Node e = new Node(value);
            e.left = curr;
            e.right = curr.right;
            curr.right.left = e;    //此时的curr就是与之同等高度的节点
            curr.right = e;
            e.down = q;
            q.up = e;

            q = e;   //将新插入的节点上移到最上面,因为后面可能还要在这里增加高度,就是在最上面插入新的一模一样的节点

            i++;   //增加当前所处的高度,这里一定能要记得写上,如果还要继续增加的话,需要判读是否需要增加头尾节的高度
        }
        size++;   //节点加一
    }


    //下面是打印每一层节点的情况
    public void display() {

        while (level >= 0) {
            Node p = head;
            while (p != null) {
                System.out.print(p.value + "-------->");
                p = p.right;
            }
            System.out.println();
            System.out.println("*****************************");
            level--;
            head = head.down;

        }
    }


    /*在链表中查找某个值是否存在,如果存在找到的节点,当然先从最高层开始查找,如果找到了在比这个值小的最后一个值,那么就顺着这个值的下面开始寻找,按照上面的步骤
    再次寻找,如过这个值正好等于要找的值,就返回true,形象的来说就是形成一个梯度的感觉。注意这里返回的节点一定是最底层的节点,利于下面的删除操作
    * */
    public Node search(int value) {
        Node p = head;
        while (true) {

            /*这里一定要写成p.right.value!=null,如果写成p.right!=null运行可能有错误,
            因为这里的尾节点的值为null,但是它的节点不是空的,如果成这样的话,那么节点可能会找到尾节点都没有找到,此时在判断value的值就出现错误
            相当与判断tail.right.value<=value,这个肯定是不行的,因为这个节点不存在,是空的更别说值了
            */

            //从最高层开始判断找到比这个小的最后一个值,就是找到一个节点的前面比value小的,后面的节点的值比value大的
            while (p.right.value != null && p.right.value <= value) {
                p = p.right;    //如果没有找到就后移直到找到这个节点

            }

            //如果找到的这个节点不是最底层的话,就向下移动一层,然后循环再次寻找,总之就是从最高层开始,一层一层的寻找
            if (p.down != null) {   //这个表示上面的循环没有找到的相等的,那么就向下移动一层
                p = p.down;
            } else {    //如果到了最底层了,这里的值仍然没有找到这个值,那么就表示不存在这个值
                if (p.value == value) {   //判断是否存在value相等的值
//                    System.out.println(p.value + "----->");
                    return p;    //返回节点
                }

                return null;    //仍然没有找到返回null
            }


        }

    }


    /*
    这里是利用上面的查找函数,找到当前需要删除的节点,当然这个节点是最底层的节点,然后循环从最底层开始删除所有的节点
    * */
    public void delete(int value) {
        Node temp = search(value);   //这里返回的必须是最底层的节点,因为要从最下面的往上面全部删除所有层的节点,否则的话可能在某一层上仍然存在这个节点
        while (temp != null) {
            temp.left.right = temp.right;
            temp.right.left = temp.left;
            temp = temp.up;   //节点上移,继续删除上一层的节点
        }

    }

    public static void main(String args[]) {
        SkipList skipList = new SkipList();
        Random random = new Random();
        skipList.insert(33);
        skipList.insert(44);
        skipList.insert(11);
        skipList.insert(10);
        skipList.insert(22);
        skipList.insert(22);

        for (int i = 0; i < 500; i++) {
            int value = (int) (random.nextDouble() * 1000);
            skipList.insert(value);
//            System.out.println(value);
        }


        Node p = skipList.search(22);
        if (p != null) {
            System.out.println(p.value);
        } else
            System.out.println("没有找到");

        skipList.delete(33);
        skipList.display();


    }
}
源码地址

跳跃链表

双链表

单链表

参考文章

java实现跳跃链表

更多文章请移步本人博客

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/69998.html

相关文章

  • 以后有面试官问你跳跃表,你就把这篇文章扔给他

    摘要:跳跃表的空间复杂度为。不过,二叉查找树是有可能出现一种极端的情况的,就是如果插入的数据刚好一直有序,那么所有节点会偏向某一边。例如这种接结构会导致二叉查找树的查找效率变为这会使二叉查找树大打折扣。假如我们要用某种数据结构来维护一组有序的int型数据的集合,并且希望这个数据结构在插入、删除、查找等操作上能够尽可能着快速,那么,你会用什么样的数据结构呢? 数组 一种很简单的方法应该就是采用数组了...

    nidaye 评论0 收藏0
  • 你确定不来了解下 Redis 跳跃表的原理吗

    摘要:前言本章将介绍中和的基本使用和内部原理因为这两种数据结构有很多相似的地方所以把他们放到一章中介绍并且重点介绍内部一个很重要的数据结构跳跃表基本介绍先来看看中集合很像中键值对无序唯一不为空值重复无序是中最特别的基础数据结构其他几个都能和大致对 前言 本章将介绍 Redis中 set 和 zset的基本使用和内部原理.因为这两种数据结构有很多相似的地方所以把他们放到一章中介绍.并且重点介绍...

    BigTomato 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<