当前位置:

首页 > 系统应用 > 数据结构与算法笔记-数据结构-跳表

数据结构与算法笔记-数据结构-跳表

[TOC]数据结构与算法笔记-数据结构-跳表跳表(skip list)跳表代码-gitee跳表代码-github关键词跳表是基于链表的一种动态数据结构,可以简单认为就是对链表的节点添加了多级索引.跳表支持快速地插入,删除,查找操作,时间复杂度都是O(logn),空间复杂度为O(n)跳表是通过添加索引

本文目录

    [TOC]

    数据结构与算法笔记-数据结构-跳表

    跳表(skip list)

    跳表代码-gitee

    跳表代码-github

    关键词

    1. 跳表是基于链表的一种动态数据结构,可以简单认为就是对链表的节点添加了多级索引.
    2. 跳表支持快速地插入,删除,查找操作,时间复杂度都是O(logn),空间复杂度为O(n)
    3. 跳表是通过添加索引使用空间换时间的设计思路,构建多级索引来提升查询效率
    4. 跳表的时间复杂度为O(logn)
    5. 跳表数通过随机函数来维护平衡
    6. 跳表插入数据时要维护索引和节点的平衡,否则极端情况下可能会导致跳表退化成为链表
    7. 跳表更加灵活,可以通过改变索引构建策略,有效平衡执行效率和内存消耗.
    8. 跳表有可与红黑树匹敌的性能,跳表写起来却好写很多.很多时候可以直接替代红黑树
    9. 按照区间来查找数据这个操作,红黑树的效率没有跳表高.对于按照区间查找数据这个操作,跳表可以做到,O(logn) 的时间复杂度定位区间的起点,而后在原始链表中顺序往后遍历即可

    理解跳表

    二分查找法底层依赖的时数组随机访问的特性,所以只能用数组来实现.

    链表也有类似二分的查找操作, 叫做跳表(skip list)

    链表可是个性能卓越的动态数据结构,它支持快速插入、删除和查找操作,而且编写起来也非常简单,甚至在某些情况下可以替代红黑树。

    其中Redis的有序列表(sorted set)就是利用跳表来实现的,因为:

    严格来说Redis还用到了Hash table
    主要Redis手册,有序集合的核心操作就是
    插入一个数据;
    删除一个数据;
    查找一个数据;
    按照区间查找数据(比如查找值在[100, 356]之间的数据);
    迭代输出有序序列。

    其中,插入、删除、查找以及迭代输出有序序列这几个操作,红黑树也可以完成,时间复杂度跟跳表是一样的。但是,按照区间来查找数据这个操作,红黑树的效率没有跳表高。
    对于按照区间查找数据这个操作,跳表可以做到 O(logn) 的时间复杂度定位区间的起点,然后在原始链表中顺序往后遍历就可以了
    还有,跳表更加灵活,它可以通过改变索引构建策略,有效平衡执行效率和内存消耗。

    单项链表的数据就算是有序的,要获取指定的数据也要从头逐个遍历,时间复杂度为O(n)

    如图:

    一级索引

    想要提高查询效率,可以通过对链表建一级索引来实现.在每两个节点中提取一个节点到作为索引或索引层

    如图: 下面的down代表下一个节点的指针

    设若获取节点16:

    1. 首先遍历索引层,当遍历到索引层中值为13的节点时,发现其下一个节点是17,那么节点16必然位于这两个节点之间。

    2. 通过索引层及诶单的down指针,到原始接链表中继续向后遍历

    3. 此时,只需再向后遍历两个及诶单即可找到值等于16的节点

    4. 原来需要查找16次,现在只要7次遍历

    可见, 加一层索引之后,查找一个节点需要遍历的次数就减少了很多,查找效率提升很高.

    二级索引

    和建立第一级索引的方式类似, 在第一级索引的基础上,每两个节点抽出一个节点到第二级作为二级索引.

    此时再来查找16,只需要遍历6个节点.

    如图:

    当数据量够大,够大的时候, 查询效率会有更大的提升,下图一个64个节点的链表.建立了五级索引

    要找到值为62的节点, 在没有索引时需要遍历62个节点.

    现在只需要遍历11个节点即可

    如图:

    上面这种链表加多级索引的结构就是跳表 ,可以看到跳表大大减少了查询次数.对链表的优化是显而易见的.

    跳表查询有多快

    单项链表中查询指定数据的时间复杂度是O(n)

    具有多级索引的跳表中, 假设有n个节点需要多少级索引:

    设,若每两个节点抽出一个节点作为上一级索引

    1. 第一级索引约为n/2个
    2. 第二级索引约为n/4个
    3. 第三极索引约为n/8个
    4. 第四级索引约为n/16个
    5. ......以此类推
    6. 第k级索引的节点个数是k-1级索引的节点个数的1/2
    7. 第k级索引节点的个数就是n/(2^k)

    设,索引有h级,最高级的索引有2个节点,

    1. 套用上面的公式得到n/(2^h)=2,求得h=log2n-1
    2. 如果包含原始链表这一层,整个跳表的高度就是log2n
    3. 在跳表查询某个数据时,若每一次都要遍历m个节点,那在跳表中查询一个数据的时间复杂度就是O(m*logn)

    多级索引

    如果每三个或五个抽出一个作为索引,如图有14个节点:

    1. 第一级索引需要n/3个节点
    2. 第二级索引需要n/9个节点
    3. ......每向上一级,索引的个数都除以3
    4. 假设做高级的索引个数为1, 把每级节点个数列出来,就是一个等比数列

    通过等比数列求和公式, 总的索引结点大约就是 n/3+n/9+n/27+…+9+3+1=n/2

    尽管空间复杂度还是 O(n),但比上面的每两个结点抽一个结点的索引构建方法,要减少了一半索引结点存储空间.

    一般在真正的开发中,不考虑索引占的空间,索引结点只需要存储关键值和几个指针,并不需要存储对象.

    高效的动态插入和删除

    插入和删除实际上是需要两步的:

    1. 找到合适的节点
    2. 插入或删除

    查找

    跳表还支持动态插入,删除,切插入和删除的时间复杂度都是O(logn)

    相比之下,单项链表的插入是O(1),但是这是在定好插入位置之后的时间复杂度.

    但是为了保证链表数据的顺序性, 在插入之前还需要找到插入位置,查找一通这就费了劲了.

    单向链表, 需要遍历每一个节点来找到插入的位置

    插入操作

    上面说过了, 跳表通过查找指定节点的时间复杂度是O(logn),找到插入位置也一样, 插入过程如下图:

    删除操作

    1. 如果这个节点同时在索引中,想要删除原始链表中的节点,同时还要删除索引中的节点.

    2. 单项连表的删除操作需要拿到要该节点的前一个节点,然后通过指针来删除后一个节点,以完成删除该节点的操作.

    3. 所以在查找要删除的节点时,一定要获取到该节点的前一个节点.(双向链表不考虑这个问题)

    跳表索引动态更新

    在不断的插入数据而不去更新索引时,可能会出现两个索引之间节点数特别多的情况.

    在极端情况下,会导致跳表退化成为链表.

    如下图:

    跳表作为一个动态数据结构,需要我们不断地维护索引与原始链表之间的平衡.

    如果链表节点多了,索引节点就要增加,以避免复杂度退化,导致查找和删除性能下降.

    红黑树和avl数是通过左右旋的方式保持左右子树的大小平衡,而跳表数通过随机函数来维护平衡.

    通过随机函数,决定该节点插入到哪几级索引中,

    如随机函数生成了值k,那就将这个节点添加到第一级到第K级的, 这几级的索引中

    如下图:

    随机函数要比较高,从概率上来讲要保证跳表的索引大小和数据大小平衡性,不至于性能过度退化.

    总结

    跳表的实现方式是很简单的,但是要特别注意的是随机函数的选择,

    如果随机函数选择不当,会导致索引分配极不均衡.

    极端情况下,跳表的一部分节点之间会退化为链表, 那就尴尬了.

    插入

    1. 首先随机,得到要索引要补充的高度
    2. 从大到小循环,高度为上次得到的索引高度
    3. 循环数据,在上一步的循环中嵌套循环, 直到找到数据要插入的位置或者查到了链表的最后
    4. 找到位置后,将该位置后面的节点取出,将当前要插入的节点的下一个指针标记为该节点.
    5. 将该位置的前一个节点的下一个节点的指针修改为当前节点
    6. 插入完成

    删除

    查找

    删除和查找流程类似, 不再赘述.

    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
    作者最新文章
    系统应用
    相关文章 更多
    悟空浏览器怎么彻底清理浏览器配置文件
    悟空浏览器怎么彻底清理浏览器配置文件

    彻底清理悟空浏览器的数据,通常有三个路径:通过手机系统设置能一次性清除所有配置和用户信息;利用浏览器内置功能,可以只清理缓存而保留个性化设置;最彻底的则是卸载重装,让应用回到初始状态。 悟空浏览器用久了,是不是偶尔会感觉变慢,或者出现一些难以解释的小毛病?有时候,与其一个个排查问题,不如来一次彻底的

    漫蛙漫画官网首页登录入口
    漫蛙漫画官网首页登录入口

    漫蛙漫画首页登录入口https://www.manwamh.top/:一触即达的漫画世界核心枢纽 对于漫画迷而言,找到那个可靠的资源门户至关重要。漫蛙漫画的首页登录入口,正是这样一个核心渠道。通过它,你可以直接跳转到漫蛙2漫画APP的下载页面,轻松几步完成安装,马上就能投入到精彩纷呈的漫画之旅中。 漫蛙漫画首页登录入口: 官方入口地址已经为你备好

    漫蛙漫画官方入口
    漫蛙漫画官方入口

    漫蛙漫画官方入口与核心功能解析 寻找一个稳定、资源丰富的漫画在线阅读平台,是许多漫画爱好者的共同需求。其中,漫蛙漫画官方入口及其免费全集服务,受到了不少关注。那么,这个平台究竟如何?下面,我们就来深入了解一下它的具体信息与特色功能。 平台的官方访问地址是:https://www.manwa123.c

    漫蛙动漫APP最新版本下载
    漫蛙动漫APP最新版本下载

    对于动漫爱好者而言,找到一个资源全、体验佳的追番平台,常常是件头疼事。漫蛙动漫APP的定位很明确:就是要打造一个聚合全球正版动漫资源的专属乐园。无论是当季火爆的日漫新番、值得回味的经典国创,还是那些小众却精彩的优质动画,在这里基本都能一网打尽。平台底层采用了智能缓冲技术,最大程度保证了播放的流畅度,

    漫蛙官网入口免费下载最新版
    漫蛙官网入口免费下载最新版

    想要获取正版manwa漫蛙APP?官方指定下载渠道就是漫蛙官网入口。 对于漫画迷而言,找到一款心仪的阅读神器至关重要。漫蛙APP正是这样一款专为全球漫画爱好者打造的平台,它汇聚了从日韩人气连载到本土原创精品的海量资源。说它“应有尽有”毫不为过。更重要的是,其界面设计清爽直观,搭配智能检索功能,能让用

    漫蛙漫画在线观看入口
    漫蛙漫画在线观看入口

    想要畅享海量正版漫画资源?漫蛙漫画平台不容错过 对于漫画迷来说,找到一个资源丰富、体验流畅的正版平台实属幸事。漫蛙漫画凭借其优质的在线阅读服务,已经成为了许多资深读者的心头好。今天,我们就来详细拆解一下平台的访问方法与实用技巧,助你轻松开启漫画之旅。 漫蛙漫画网页入口页面指南 想立刻体验?官方在线观

    漫蛙如何下载最新版本
    漫蛙如何下载最新版本

    漫蛙漫画网APP官方下载方法全解析 对于资深漫画迷来说,找到一个资源全、更新快、体验佳的阅读平台,就像淘到了宝藏。漫蛙漫画网APP,正是这样一个专为爱好者打造的精品集散地。它汇聚了全球优质的正版漫画,从火爆的日漫连载到崛起的国创佳作,平台都能做到实时同步更新。当然,第一步得先把它装到设备上。接下来,

    漫蛙漫画APP最新版本下载
    漫蛙漫画APP最新版本下载

    漫蛙漫画APP:专业漫画阅读工具的全面革新 作为一款专业的漫画阅读工具,漫蛙漫画APP整合了全球优质漫画资源,其升级版漫蛙2在功能与体验上可谓全面革新。这款应用不仅囊括日漫经典与国漫新作,更通过简洁直观的界面设计和流畅操作,为用户打造沉浸式阅读环境,充分满足各类漫画爱好者的多样化需求。 漫蛙漫画特色

    卖茶叶妈妈3d漫蛙安卓版下载
    卖茶叶妈妈3d漫蛙安卓版下载

    当下动漫圈热议的卖茶叶妈妈3d漫蛙下载,凭借其突破性的3D视觉技术成为焦点 最近动漫爱好者们都在讨论一个现象级产品——卖茶叶妈妈3d漫蛙下载。这款由漫蛙漫画平台倾力打造的3D作品专区,用立体建模与动态分镜彻底颠覆了传统二维漫画的阅读模式。你猜怎么着?现在只需通过专区提供的便捷下载通道,无论是热血冒险

    漫蛙下载最新版本
    漫蛙下载最新版本

    漫蛙APP:资深漫画迷的移动图书馆与阅读利器 对于漫画爱好者来说,找到一个资源全、体验好的阅读平台,从来都不是件容易的事。而漫蛙APP,恰恰就是为这个需求而生的。它凭借海量的正版漫画库和极其便捷的离线下载功能,在圈内积累了相当不错的口碑。更重要的是,从经典的日本热血漫到新兴的国产原创作品,它几乎一网

    查看更多
    精品专题 更多
    装机必备
    装机必备

    正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

    Windows
    Windows

    正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

    PDF教程
    PDF教程

    正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

    Mac软件 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    Aperty macOS版
    Aperty macOS版
    macOS

    Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

    WINDOWS 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    PixTV 网页版
    PixTV 网页版
    Windows

    PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台,提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具,适合短剧、漫剧、广告及社交媒体内容制作。