漫画:什么是 “跳表” ?
算法与数据结构 2022-11-03
来自公众号:程序员小灰



—————  第二天  —————




如何进行二分查找呢?


首先根据数组下标,定位到数组的中间元素:



由于要查找的元素20,大于中间元素12,再次定位到数组半部分的中间元素:



这一次定位到的元素正好是20,查找成功。


如果数组的长度是n,二分查找的时间复杂度是O(logn),比起从左到右逐个遍历元素进行查找的方式,大大提升了查找性能。






如上图所示,想要定位到链表的中间结点9,是无法直接定位的,需要从头结点开始,顺着next指针,逐个访问下一个结点。


因此,链表这种数据结构并不适用于二分查找。



————————————


常见的图书目录,就像下面这样:



第5章对应的页码是170,因此我们直接翻到书的第170页,就是第5章的内容。




如图所示,在原始链表的基础上,我们增加了一个索引链表。原始链表的每两个结点,有一个结点也在索引链表当中。



这样做有什么好处呢?当我们想要定位到结点20,我们不需要在原始链表中一个一个结点访问,而是首先访问索引链表:



在索引链表找到结点20之后,我们顺着索引链表的结点向下,找到原始链表的结点20:



这个过程,就像是先查阅了图书的目录,再翻到章节所对应的页码。


由于索引链表的结点个数是原始链表的一半,查找结点所需的访问次数也相应减少了一半。




多层次的图书目录,就像下面这样:




如图所示,我们基于原始链表的第1层索引,抽出了第2层更为稀疏的索引,结点数量是第1层索引的一半。


这样的多层索引可以进一步提升查询效率,假如仍然要查找结点20,让我们来演示一下过程:


首先,我们从最上层的索引开始查找,找到该层中仅小于结点20的前置索引结点12:



接下来,我们顺着结点12访问下一层索引,在该层中找到结点20:


最后,我们顺着第1层索引的结点20向下,找到原始链表的结点20:



在这个例子中,由于原始链表的结点数量较少,仅仅需要2层索引。如果链表的结点数量非常多,我们就可以抽出更多的索引层级,每一层索引的结点数量都是低层索引的一半。


假设原始链表有n个结点,那么索引的层级就是log(n)-1,在每一层的访问次数是常量,因此查找结点的平均时间复杂度是O(logn)。这比起常规的查找方式,也就是线性依次访问链表节点的方式,效率要高得多。


但相应的,这种基于链表的优化增加了额外的空间开销。假设原始链表有n个结点,那么各层索引的结点总数是n/2+n/4+n/8+n/16+......2,约等于n。


也就是说,优化之后的数据结构所占空间,是原来的2倍。这是典型的以空间换时间的做法。



假设我们要插入的结点是10,首先我们按照跳表查找结点的方法,找到待插入结点的前置结点(仅小于待插入结点):



接下来,按照一般链表的插入方式,把结点10插入到结点9的下一个位置:



这样是不是插入工作就完成了呢?并不是。随着原始链表的新结点越来越多,索引会渐渐变得不够用了,因此索引结点也需要相应作出调整。


如何调整索引呢?我们让新插入的结点随机“晋升”,也就是成为索引结点。新结点晋升成功的几率是50%。


假设第一次随机的结果是晋升成功,那么我们把结点10作为索引结点,插入到第1层索引的对应位置,并且向下指向原始链表的结点10:


新结点在成功晋升之后,仍然有机会继续向上一层索引晋升。我们再进行一次随机,假设随机的结果是晋升失败,那么插入操作就告一段落了。


小灰说的是什么意思呢?让我们看看下图,新结点10已经晋升到第2层索引,下一次随机的结果仍然是晋升成功,这时候该怎么办呢?




假设我们要从跳表中删除结点10,首先我们按照跳表查找结点的方法,找到待删除的结点:



接下来,按照一般链表的删除方式,把结点10从原始链表当中删除:


这样是不是删除工作就完成了呢?并不是。我们需要顺藤摸瓜,把索引当中的对应结点也一一删除:




刚才的例子当中,第3层索引的结点已经没有了,因此我们把整个第3层删去:



最终的删除结果如下:




1. 程序中跳表采用的是双向链表,无论前后结点还是上下结点,都各有两个指针相互指向彼此。


2. 程序中跳表的每一层首位各有一个空结点,左侧的空节点是负无穷大,右侧的空节点是正无穷大。


之所以这样设计,是为了方便代码实现。代码中的跳表就像下图这样:


public class SkipList{    //结点“晋升”的概率     private static final double PROMOTE_RATE = 0.5;    private Node head,tail;    private int maxLevel;    public SkipList() {        head = new Node(Integer.MIN_VALUE);        tail = new Node(Integer.MAX_VALUE);        head.right = tail;        tail.left = head;    }    //查找结点     public Node search(int data){        Node p= findNode(data);        if(p.data == data){            System.out.println("找到结点:" + data);            return p;        }        System.out.println("未找到结点:" + data);        return null;    }    //找到值对应的前置结点     private Node findNode(int data){        Node node = head;        while(true){            while (node.right.data!=Integer.MAX_VALUE && node.right.data<=data) {                node = node.right;            }            if (node.down == null) {                break;            }            node = node.down;        }        return node;    }    //插入结点     public void insert(int data){        Node preNode= findNode(data);        //如果data相同,直接返回         if (preNode.data == data) {            return;        }        Node node=new Node(data);        appendNode(preNode, node);        int currentLevel=0;        //随机决定结点是否“晋升”         Random random = new Random();        while (random.nextDouble() < PROMOTE_RATE) {            //如果当前层已经是最高层,需要增加一层             if (currentLevel == maxLevel) {                addLevel();            }            //找到上一层的前置节点             while (preNode.up==null) {                preNode=preNode.left;            }            preNode=preNode.up;            //把“晋升”的新结点插入到上一层             Node upperNode = new Node(data);            appendNode(preNode, upperNode);            upperNode.down = node;            node.up = upperNode;            node = upperNode;            currentLevel++;        }    }    //在前置结点后面添加新结点     private void appendNode(Node preNode, Node newNode){        newNode.left=preNode;        newNode.right=preNode.right;        preNode.right.left=newNode;        preNode.right=newNode;    }    //增加一层     private void addLevel(){        maxLevel++;        Node p1=new Node(Integer.MIN_VALUE);        Node p2=new Node(Integer.MAX_VALUE);        p1.right=p2;        p2.left=p1;        p1.down=head;        head.up=p1;        p2.down=tail;        tail.up=p2;        head=p1;        tail=p2;    }    //删除结点     public boolean remove(int data){        Node removedNode = search(data);        if(removedNode == null){            return false;        }        int currentLevel=0;        while (removedNode != null){            removedNode.right.left = removedNode.left;            removedNode.left.right = removedNode.right;            //如果不是最底层,且只有无穷小和无穷大结点,删除该层             if(currentLevel != 0 && removedNode.left.data == Integer.MIN_VALUE && removedNode.right.data == Integer.MAX_VALUE){                removeLevel(removedNode.left);            }else {                currentLevel ++;            }            removedNode = removedNode.up;        }        return true;    }    //删除一层     private void removeLevel(Node leftNode){        Node rightNode = leftNode.right;        //如果删除层是最高层         if(leftNode.up == null){            leftNode.down.up = null;            rightNode.down.up = null;        }else {            leftNode.up.down = leftNode.down;            leftNode.down.up = leftNode.up;            rightNode.up.down = rightNode.down;            rightNode.down.up = rightNode.up;        }        maxLevel --;    }    //输出底层链表     public void printList() {        Node node=head;        while (node.down != null) {            node = node.down;        }        while (node.right.data != Integer.MAX_VALUE) {            System.out.print(node.right.data + " ");            node = node.right;        }        System.out.println();    }    //链表结点类     public class Node {        public int data;        //跳表结点的前后和上下都有指针         public Node up, down, left, right;        public Node(int data) {            this.data = data;        }    }    public static void main(String[] args) {        SkipList list=new SkipList();        list.insert(50);        list.insert(15);        list.insert(13);        list.insert(20);        list.insert(100);        list.insert(75);        list.insert(99);        list.insert(76);        list.insert(83);        list.insert(65);        list.printList();        list.search(50);        list.remove(50);        list.search(50);    }}



	

本文源自微信公众号:算法与数据结构,不代表用户或本站观点,如有侵权,请联系nick.zong@aspencore.com 删除!

声明: 本文转载自其它媒体或授权刊载,目的在于信息传递,并不代表本站赞同其观点和对其真实性负责,如有新闻稿件和图片作品的内容、版权以及其它问题的,请联系我们及时删除。(联系我们,邮箱:evan.li@aspencore.com )
0
评论
  • 【7.24 深圳】2025国际AI+IoT生态发展大会/2025全球 MCU及嵌入式技术论坛


  • 相关技术文库
  • C语言
  • 编程
  • 软件开发
  • 程序
  • 高效的C编程之:C编译器及其优化(上)

    本章将帮助读者在ARM处理器上编写高效的C代码。本章涉及的一些技术不仅适用于ARM处理器,也适用于其他RISC处理器。本章首先从ARM编译器及其优化入手,讲解C编译器在优化代码时所碰到的一些问题。理解这些问题,将有...

    前天
  • 有关C51的编程规范

    简介:编程首要是要考虑程序的可行性,然后是可读性、可移植性、健壮性以及可测试性。这是总则。但是很多人忽略了可读性、可移植性和健壮性(可调试的方法可能歌不相同),这是不对的。 下面就来说说有关C51的编程规...

    前天
  • 光立方程序编写步骤

    基于51单片机的4*4*4光立方程序实现原理及程序代码。LED光立方的复位电路、时钟电路、每层LED灯电路控制逻辑,系统总原理图,工作流程及相关C语言源码实现。希望能够对你学习了解LED光立方程序编写及LED立方实体制...

    07-04
  • 封装继承多态

    封装: 封装是实现面向对象程序设计的第一步,封装就是将数据或函数等集合在一个个的单元中(我们称之为类)。被封装的对象通常被称为抽象数据类型。 封装的意义: 封装的意义在于保护或者防止代码(数据)被我们无意中...

    07-04
  • 封装是什么意思?

    即隐藏对象的属性和实现细节,仅对外公开接口,控制在程序中属性的读和修改的访问级别;将抽象得到的数据和行为(或功能)相结合,形成一个有机的整体,也就是将数据与操作数据的源代码进行有机的结合,形成“类”,其中...

    07-04
  • 超声波模块测距51程序_单片机超声波测距c语言

    超声波检测原理 超声波测距的程序流程图 程序如下: //超声波模块程序 //超声波模块程序 //Trig = P2^0 //Echo = P3^2 #include #define uchar unsigned char #define uint unsigned int // void delay(uint z) {...

    07-01
  • 大佬带你看嵌入式系统,嵌入式系统该学习什么?

    嵌入式系统是当今的热门系统之一,在诸多领域,嵌入式系统都有所应用。为增进大家对嵌入式系统的认识,小编将为大家介绍嵌入式系统是一个什么样的专业,以及学习嵌入式系统该学习哪些内容。如果你对嵌入式系统具有...

    06-27
  • c51单片机编程要点总结

    c51单片机编程要点总结 1、头文件:#include (我用的是 STC 89C54RD+) 2、预定义:sbit LED = P1^0// 定义 P1 口的 0 位为 LED 注:“P1^0”这个写法,与 A51 不同(A51 是 P1.0),P1 是一组端口,端口号范围 0~7 注2...

    06-25
  • C语言基础知识点汇总

    总结C语言基础知识点

    06-23
  • Keil使用中的若干问题

      一、混合编程  1、模块内接口:  使用如下标志符:  #pragma asm  汇编语句  #pragma endasm  注意:如果在c51程序中使用了汇编语言,注意在keil编译器中需要激活Properties中的“Generate Assembler...

    06-23
  • ESP32-finsh

    esp32c2添加finsh实现了ping指令和AT指令解析

    06-13
下载排行榜
更多
评测报告
更多
广告