跳表原理-课堂笔记

课程地址

跳表是一种基于随机化的有序数据结构,它提出是为了赋予有序单链表以 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+树

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

贪心day04(买卖股票的最佳时机)

1.买卖股票的最佳时机 题目链接:. - 力扣(LeetCode) 思路:我们其实只需遍历一篇就可以解决这个问题。首先我们定义一个min为无穷大值,再遍历只要有数字比min跟小我们就更改min的值就好,此时我们只需要找出…

【Python爬虫实战】深入解锁 DrissionPage:ChromiumPage 自动化网页操作指南

🌈个人主页:易辰君-CSDN博客 🔥 系列专栏:https://blog.csdn.net/2401_86688088/category_12797772.html ​ 目录 前言 一、ChromiumPage基础操作 (一)初始化Drission 和 ChromiumPage 对象 &#xff0…

VS Code 插件 MySQL Shell for VS Code

https://marketplace.visualstudio.com/items?itemNameOracle.mysql-shell-for-vs-code

稳压二极管详解

目录 1. 工作原理 2. 稳压二极管的伏安特性曲线 3. 正向特性: 4. 反向特性 5. 稳定电压(Vz) 6. 动态电阻(rz) 7.最大耗散功率(PzM) 8. 最大稳定工作电流(IzMAX)和…

Springboot 一个西餐主题网站-计算机设计毕业源码73020

目录 摘要 1 绪论 1.1 选题背景与意义 1.2国内外研究现状 1.3论文结构与章节安排 2系统分析 2.1 可行性分析 2.2 系统流程分析 2.2.1 数据流程 2.2.2 业务流程 2.3 系统功能分析 2.3.1 功能性分析 2.3.2 非功能性分析 2.4 系统用例分析 2.5本章小结 3 系统总体设…

JS渗透(安全)

JS逆向 基本了解 作用域: 相关数据值 调用堆栈: 由下到上就是代码的执行顺序 常见分析调试流程: 1、代码全局搜索 2、文件流程断点 3、代码标签断点 4、XHR提交断点 某通js逆向结合burp插件jsEncrypter 申通快递会员中心-登录 查看登录包…

世界技能竞赛大数据应用开发环境1:1还原

关注我,私信我获得集群环境 集群情况 模块A搭建环境,在容器中搭建大数据平台 Hadoop HA环境 Pc机,安装安装比赛需要软件 模块B中使用idea快速开发完成数据处理 模块E包含了接口数据,使用vs code快速搭建vue数据可视化

【c++丨STL】vector模拟实现

🌟🌟作者主页:ephemerals__ 🌟🌟所属专栏:C、STL 目录 前言 一、vector底层刨析 二、模拟实现 1. 属性、迭代器以及函数声明 2. 功能实现 交换两个容器的内容 构造函数 拷贝构造 赋值重载 析构…

指针的运用

接下来我将会用的话,讲解我对指针运用仅有的印象 1.解引用 int a23; int*p&a; *p666; 而*p666;,便是解引用操作,跟简单地说*p便是解引用,它的意思是,对p中所储存的地址所在位置的内容进行操作&#xf…

三周精通FastAPI:38 针对不同的编程语言来生成客户端

官方文档:https://fastapi.tiangolo.com/zh/advanced/generate-clients/ 生成客户端 因为 FastAPI 是基于OpenAPI规范的,自然您可以使用许多相匹配的工具,包括自动生成API文档 (由 Swagger UI 提供)。 一个不太明显而又特别的优势是&#…

广告联盟有哪些

随着互联网的发展,越来越多的人开始投身于网站建设和运营。对于站长来说,如何在提供优质内容的同时获取收益是一个重要的问题。广告联盟作为一种常见的盈利模式,受到了广大站长的青睐。本文将介绍5个适合国内站长的广告联盟平台,帮…

兵马未动,粮草先行-InnoDB统计数据是如何收集的

我们前面介绍查询成本的时候经常用到一些统计数据,比如通过SHOW TABLE STATUS可以看到关于表的统计数据,通过SHOW INDEX可以看到关于索引的统计数据,那么这些统计数据是怎么来的呢?它们是以什么方式收集的呢?本章将聚焦…

【Promise】JS 异步之宏队列与微队列

文章目录 1 原理图2 说明3 相关面试题3.1 面试题13.2 面试题23.3 面试题33.4 面试题4 1 原理图 2 说明 JS 中用来存储待执行回调函数的队列包含 2 个不同特定的队列:宏队列和微队列。宏队列:用来保存待执行的宏任务(回调),比如:定…

基础概念理解

一,数据结构分类 连续结构,跳转结构。 二,对变量的理解 在 C 语言中,变量是用于存储数据的抽象符号。变量本质上是一块内存区域的标识符(即它代表内存中的某一块区域),用来存储数据&#xff…

C 学习(4)

return 0; 前提:C 语言规定,main()是程序的入口函数,即所有的程序一定要包含一个main()函数。程序总是从这个函数开始执行,如果没有该函数,程序就无法启动。其他函数都是通过它引入程序的。 main()的写法&#xff0c…

欺诈文本分类检测(十八):基于llama.cpp+CPU推理

1. 前言 前文我们用Lora训练出自己的个性化模型后,首先面临的问题是:如何让模型在普通机器上跑起来?毕竟模型微调时都是在几十G的专用GPU上训练的,如果换到只有CPU的普通电脑上,可能会面临几秒蹦一个词的尴尬问题。 …

工程数学线性代数(同济第七版)附册课后习题答案PDF

《线性代数附册 学习辅导与习题全解》是与同济大学数学科学学院编《工程数学 线性代数》第七版教材配套的教学辅导书,由同济大学作者团队根据教材内容和要求编写而成。本书在《工程数学 线性代数》第六版附册(即辅导书)的基础上修改而成。全书…

传输层协议、ACL

第六章 传输层协议、ACL 文章目录 第六章 传输层协议、ACL1.TCP和UDP协议1.1 TCP协议1.2 TCP报文段1.3 TCP连接 2.UDP协议3.ACL概述ACL原理及种类ACL组成规则编号通配符(反掩码) 4.ACL应用ACL匹配规则ACL匹配规则 1.TCP和UDP协议 TCP/IP协议族的传输层协…

(蓝桥杯C/C++)——搜索

一、回溯法 1.回溯法简介 回溯法一般使用 ** DFS(深度优先搜索) ** 实现,DFS是一种遍历或搜索图、树或图像等数据结构的算法,当然这个图、树未必要存储下来(隐式处理就是回溯法),常见的是通过某种关系构造出的搜索树,搜索树一般…

Turtlebot3 buger 硬件与操作平台详细介绍

引言 TurtleBot3 有三个版本,分别是紧凑型的 Burger、功能更强的 Waffle和性能提升的 Waffle Pi,分别适用于不同的应用需求。使用 Raspberry Pi 作为主控单板计算机(SBC),而 Waffle Pi 可以使用更强大的 NVIDIA Jetson…