跳表原理笔记

课程地址

跳表是一种基于随机化的有序数据结构,它提出是为了赋予有序单链表以 O(logn) 的快速查找和插入的能力

创建

在这里插入图片描述
首先在头部创建一个 sentinel 节点,然后在 L1 层采用“抛硬币”的方式来决定 L0 层的指针是否增长到 L1 层

在这里插入图片描述

例如上图中,L0 层的节点2,10,11,13,20,26 都增长到了 L1 层。继续采用抛硬币的方式,来决定 L1 层的指针是否增长到 L2 层

在这里插入图片描述
例如上图中,L1 层的节点2,13,26 都增长到了 L2 层。继续采用抛硬币的方式,来决定 L2 层的指针是否增长到 L3 层

在这里插入图片描述
例如上图中,L2 层的节点 13 增长到了 L3 层。至此我们停止层数增长,层数一般定为 logn 层

所以 L0 层保存了原始数据,逐个串联。L1 层平均每次跳过 1 个,L2 层平均每次跳过 2 个,L3 层平均每次跳过 4 个

跳跃相当于快速通道,使我们得以快速确定查找的元素是否在当前区间中

查找

首先查找 key = 13,从 L3 层开始查找,第一个节点的值就是 13,直接找到了
在这里插入图片描述

然后查找 key = 8,从 L3 出发,第一个节点的值是 13,大于 8,则从 Sentinel 向下走一层到 L2

从 L2 的 Sentinel 出发,第一个节点的值是 2,小于 8,则继续向后走一步,下一个节点的值是 13,大于 8,则从 L2 的第一个节点(2)向下走一层到 L1

从 L1 的第一个节点(2)出发,下一个节点的值是 10,大于 8,则从 L1 的第一个节点(2)向下走一层到 L0

从 L0 的第一个节点(2)出发,下一个节点的值是8,则找到了

在这里插入图片描述

然后查找 key = 20,从 L3 的 Sentinel 出发,下一个节点的值是 13,小于 20,因为 13 节点已经是最后一个节点,不能再往后走,所以向下走一层到 L2

从 L2 的第二个节点(13)出发,下一个节点的值是 26,大于 13,则向下走一层到 L1 层

从 L1 层的第 4 个节点出发,下一个节点的值是 20,则找到了

在这里插入图片描述

最后一个查找的例子是查找 key = 21,从 L3 的 Sentinel 出发,下一个节点的值是 13,小于 21,因为 13 节点已经是最后一个节点,所以向下走一层到 L2

从 L2 的第二个节点(13)出发,下一个节点的值是 26,大于 13,则向下走一层到 L1 层

从 L1 层的第 4 个节点出发,下一个节点的值是 20,小于 21,则向后走一步到 26,大于 21,则从 20 向下走一步到达 L0 层

从 L0 层的第 7 个节点(20)出发,下一个节点的值是 22,已经大于 21,因为 L0 已经是最底层,所以 20 和 22 之间没有其他节点,故 key = 21 不存在

在这里插入图片描述

新增

在这里插入图片描述
首先需要确定新节点的插入位置,这个过程跟查找是一致的,上图中红色箭头就表示新节点需要插入到这个范围内

同时使用一张哈希表记录下每个红色箭头的起点(指针)

在这里插入图片描述

接下来创建一个新节点,它的指针域采用“抛硬币”的方式决定是否向上层增长:如果正面朝上就增加一层,如果反面朝上就终止这个过程,那么新节点的高度会以指数的方式快速收敛。例如上图中,新节点 9 就是抛了 2 次硬币都正面朝上,第三次反面朝上

最后,借助表中记录的指针,将新的节点插入到跳表中

在这里插入图片描述

跳表 vs B+树

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/909376.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

医院信息化与智能化系统(17)

医院信息化与智能化系统(17) 这里只描述对应过程,和可能遇到的问题及解决办法以及对应的参考链接,并不会直接每一步详细配置 如果你想通过文字描述或代码画流程图,可以试试PlantUML,告诉GPT你的文件结构,让他给你对应…

selenium操作已开启的浏览器,方便调试

一、谷歌浏览器配置: 在所安装的谷歌下面,执行下面命令,打开谷歌浏览器,用来selenium的操作: 注意事项:端口需要不被占用,--user-data-dir"D:\workspace\chrome-data"这个路径需要有…

深度强化学习:从理论到应用

目录 1.引言 2.什么是强化学习? 3.深度学习和强化学习的结合 4.深度强化学习的主要方法 5.深度强化学习的应用领域 6.深度强化学习的挑战与未来 7.总结 1.引言 深度强化学习(Deep Reinforcement Learning,DRL)是近年来人工…

[Linux] 进程控制之创建和终止

🪐🪐🪐欢迎来到程序员餐厅💫💫💫 主厨:邪王真眼 主厨的主页:Chef‘s blog 所属专栏:青果大战linux 总有光环在陨落,总有新星在闪烁 每日吐槽 不得不说&a…

介绍一下rand函数生成随机数(c基础)

适合对象 c语言初学者 总结语言用色&#xff0c;个人强调用红色&#xff0c;注意为易错点&#xff0c;若有问题请告诉我谢谢。(建议通过目录观看)。一定要自己动手打代码。 rand函数 是生成随机数的函数&#xff0c;但实则是伪随机数。(即是同一个值) 格式 #include<st…

vue3入门知识(一)

vue3简介 性能的提升 打包大小减少41%初次渲染快55%&#xff0c;更新渲染快133%内存减少54% 源码的升级 使用Proxy代替defineProperty实现响应式重写虚拟DOM的实现和Tree-Shaking 新的特性 1. Composition API&#xff08;组合API&#xff09; setupref与reactivecomput…

FET113i-S核心板已支持RISC-V,打造国产化降本的更优解 -飞凌嵌入式

FET113i-S核心板是飞凌嵌入式基于全志T113-i处理器设计的国产工业级核心板&#xff0c;凭借卓越的稳定性和超高性价比&#xff0c;FET113i-S核心板得到了客户朋友们的广泛关注。作为一款拥有A7核RISC-V核DSP核的多核异构架构芯片&#xff0c;全志科技于近期释放了T113-i的RISC-…

C语言进阶:二.数据的存储(2)

❤个人主页❤&#xff1a;折枝寄北-CSDN博客 ❤学习专栏❤&#xff1a; C语言专栏&#xff1a;https://blog.csdn.net/2303_80170533/category_12794764.html?spm1001.2014.3001.5482https://blog.csdn.net/2303_80170533/category_12794764.html?spm1001.2014.3001.5482 在…

城市智慧公厕解决方案,建设城市智能化公厕

在城市的飞速发展进程中&#xff0c;公厕作为城市基础设施的重要一环&#xff0c;其智能化建设已成为提升城市品质与居民生活舒适度的关键举措。以下是关于城市智慧公厕的几点解决方案。 一、智能设施配备 首先&#xff0c;要引入智能化的卫生设备。例如&#xff0c;安装自动感…

【STL栈和队列】:高效数据结构的应用秘籍

前言&#xff1a; C 标准模板库&#xff08;STL&#xff09;为我们提供了多种容器&#xff0c;其中 stack&#xff08;栈&#xff09;和 queue&#xff08;队列&#xff09;是非常常用的两种容器。 根据之前C语言实现的栈和队列&#xff0c;&#xff08;如有遗忘&#xff0c;…

vue data变量之间相互赋值或进行数据联动

摘要&#xff1a; 使用vue时开发会用到data中是数据是相互驱动&#xff0c;经常会想到watch,computed&#xff0c;总结一下&#xff01; 直接赋值&#xff1a; 在 data 函数中定义的变量可以直接在方法中进行赋值。 export default {data() {return {a: 1,b: 2};},methods: {u…

HTML 基础标签——分组标签 <div>、<span> 和基础语义容器

文章目录 1. `<div>` 标签特点用途示例2. `<span>` 标签特点用途示例3. `<fieldset>` 标签特点用途示例4. `<section>` 标签特点用途示例5. `<article>` 标签特点用途示例总结HTML中的分组(容器)标签用于结构化内容,将页面元素组织成逻辑区域…

Java开发配置文件的详情教程配置文件类型

学习总结 1、掌握 JAVA入门到进阶知识(持续写作中……&#xff09; 2、学会Oracle数据库入门到入土用法(创作中……&#xff09; 3、手把手教你开发炫酷的vbs脚本制作(完善中……&#xff09; 4、牛逼哄哄的 IDEA编程利器技巧(编写中……&#xff09; 5、面经吐血整理的 面试技…

全面解析:网络协议及其应用

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 全面解析&#xff1a;网络协议及其应用 全面解析&#xff1a;网络协议及其应用 全面解析&#xff1a;网络协议及其应用 网络协议…

软件压力测试有多重要?北京软件测试公司有哪些?

软件压力测试是一种基本的质量保证行为&#xff0c;它是每个重要软件测试工作的一部分。压力测试是给软件不断加压&#xff0c;强制其在极限的情况下运行&#xff0c;观察它可以运行到何种程度&#xff0c;从而发现性能缺陷。 在数字化时代&#xff0c;用户对软件性能的要求越…

聊一聊Qt中的Slider和ProgressBar

目录 QAbstractSilder 主要属性 设置值 信号 其他功能 API QSlider 主要功能 控制刻度 信号 用户交互 键盘操作 API QProgressBar API QScrollBar 详细描述 QDial API 一个示例 Slider和ProgressBar从某种程度上都是反应了自己对目标控件的进度状态。在Qt中…

源鲁杯 2024 web(部分)

[Round 1] Disal F12查看: f1ag_is_here.php 又F12可以发现图片提到了robots 访问robots.txt 得到flag.php<?php show_source(__FILE__); include("flag_is_so_beautiful.php"); $a$_POST[a]; $keypreg_match(/[a-zA-Z]{6}/,$a); $b$_REQUEST[b];if($a>99999…

qt QFileDialog详解

1、概述 QFileDialog是Qt框架中的一个对话框类&#xff0c;用于提供一个标准的文件选择对话框。它允许用户浏览文件系统&#xff0c;选择一个或多个文件或目录&#xff0c;以及指定文件名。QFileDialog支持本地文件系统和远程文件系统&#xff08;如通过FTP或SFTP访问的文件系…

【客户服务】客户不是上帝---投诉管理新智慧

第一讲 怎样正确看待客户投诉 什么是客户投诉 当客户对于产品或服务产生不满&#xff0c;当客户的需求得不到满足时&#xff0c;就会产生客户投诉。 投诉的根源有两方面 产品质量服务质量 投诉对企业是好事还是坏事 坏事&#xff1a;不良口碑的传递和客户的升级投诉会影响…

责任链模式 Chain of Responsibility

1 意图 使多个对象都有机会处理请求&#xff0c;从而避免请求的发送者和接收者之间的耦合关系。将这些对象连成一条链&#xff0c;并沿着这条链传递该请求&#xff0c;直到有一个对象处理它为止。 2 结构 Handler 定义一个处理请求的接口;(可选)实现后继链。 ConcreteHandler …