数据结构:跳表(Skip list)（有一个类似跳表的数据结构）
ztj100 2025-02-03 16:17 14 浏览 0 评论
跳表[Skip list]是由分层的有序链表实现的数据结构，使用概率平衡，可以用来替代平衡树。它的插入、查找、删除时间复杂度跟平衡树相同，都是log(N), 但相比于平衡树，跳表的实现更加简单，并且节省空间。Redis的Sorted Set（有序集合）、LevelDB中的Memtable等都使用跳表实现。
性能比较
实现细节
我们考虑一个有序单链表：
在链表中查找一个数据需要遍历整个链表，时间复杂度是O(N)。
如果是有序数组，我们可以通过二分查找，时间复杂度O(logN)。
能不能把二分查找的思想用到链表上呢？
跳表就是通过快速定位元素所在的区间段而增加查询效率。 每个链表的节点会有不同的高度，高度是随机的，越高层两个节点的间距越大，如下图：
具体实现(Go语言描述)
具体代码可参考：
https://github.com/liwnn/algorithms-go/blob/master/skiplist/skiplist.go
随机层数
- p 取值范围为[0.0,1.0)，代表第i层能否出现的固定概率，通常为1/4
- MaxLevel 最大层数，跟节点数有关。(1/p)^MaxLevel要大于最多节点数 算法如下：
结构定义
查找
如上图所示，对于一个从小到大的跳表
如果我们需要查找元素e=17或19，只需要找到前置节点12，然后比较12的下一个节点是否是要查找的值即可
插入
跟查找类似，不过需要记录每一层的前置节点。插入元素的随机层数，并对每一层进行链表插入。
删除
跟插入一样，都需要要查找前置节点，然后删除元素所有层的链表元素
参考
- Skip Lists: A Probabilistic Alternative toBalanced Trees：https://www.epaperpress.com/sortsearch/download/skiplist.pdf
相关推荐
- 30天学会Python编程:16. Python常用标准库使用教程
-
16.1collections模块16.1.1高级数据结构16.1.2示例...
- 强烈推荐!Python 这个宝藏库 re 正则匹配
-
Python的re模块（RegularExpression正则表达式）提供各种正则表达式的匹配操作。...
- Python爬虫中正则表达式的用法，只讲如何应用，不讲原理
-
Python爬虫：正则的用法(非原理)。大家好，这节课给大家讲正则的实际用法，不讲原理，通俗易懂的讲如何用正则抓取内容。·导入re库，这里是需要从html这段字符串中提取出中间的那几个文字。实例一个对...
- Python数据分析实战-正则提取文本的URL网址和邮箱(源码和效果)
-
实现功能：Python数据分析实战-利用正则表达式提取文本中的URL网址和邮箱...
- python爬虫教程之爬取当当网 Top 500 本五星好评书籍
-
我们使用requests和re来写一个爬虫作为一个爱看书的你（说的跟真的似的）怎么能发现好书呢？所以我们爬取当当网的前500本好五星评书籍怎么样？ok接下来就是学习python的正确姿...
- 深入理解re模块:Python中的正则表达式神器解析
-
在Python中，"re"是一个强大的模块，用于处理正则表达式（regularexpressions）。正则表达式是一种强大的文本模式匹配工具，用于在字符串中查找、替换或提取特定模式...
- 如何使用正则表达式和 Python 匹配不以模式开头的字符串
-
需要在Python中使用正则表达式来匹配不以给定模式开头的字符串吗？如果是这样，你可以使用下面的语法来查找所有的字符串，除了那些不以https开始的字符串。r"^(?!https).*&...
- 先Mark后用!8分钟读懂 Python 性能优化
-
从本文总结了Python开发时，遇到的性能优化问题的定位和解决。概述：性能优化的原则——优化需要优化的部分。性能优化的一般步骤：首先，让你的程序跑起来结果一切正常。然后，运行这个结果正常的代码，看看它...
- Python“三步”即可爬取，毋庸置疑
-
声明：本实例仅供学习，切忌遵守robots协议，请不要使用多线程等方式频繁访问网站。#第一步导入模块importreimportrequests#第二步获取你想爬取的网页地址，发送请求，获取网页内...
- 简单学Python——re库(正则表达式)2(split、findall、和sub)
-
1、split（）：分割字符串，返回列表语法：re.split（'分隔符','目标字符串'）例如：importrere.split('，','...
- Lavazza拉瓦萨再度牵手上海大师赛
-
阅读此文前，麻烦您点击一下“关注”，方便您进行讨论和分享。Lavazza拉瓦萨再度牵手上海大师赛标题:2024上海大师赛:网球与咖啡的浪漫邂逅在2024年的上海劳力士大师赛上,拉瓦萨咖啡再次成为官...
- ArkUI-X构建Android平台AAR及使用
-
本教程主要讲述如何利用ArkUI-XSDK完成AndroidAAR开发，实现基于ArkTS的声明式开发范式在android平台显示。包括：1.跨平台Library工程开发介绍...
- Deepseek写歌详细教程（怎样用deepseek写歌功能）
-
以下为结合DeepSeek及相关工具实现AI写歌的详细教程，涵盖作词、作曲、演唱全流程：一、核心流程三步法1.AI生成歌词-打开DeepSeek（网页/APP/API），使用结构化提示词生成歌词：...
- “AI说唱解说影视”走红，“零基础入行”靠谱吗?本报记者实测
-
“手里翻找冻鱼，精心的布局；老漠却不言语，脸上带笑意……”《狂飙》剧情被写成歌词，再配上“科目三”背景音乐的演唱，这段1分钟30秒的视频受到了无数网友的点赞。最近一段时间随着AI技术的发展，说唱解说影...
- AI音乐制作神器揭秘!3款工具让你秒变高手
-
在音乐创作的领域里，每个人都有一颗想要成为大师的心。但是面对复杂的乐理知识和繁复的制作过程，许多人的热情被一点点消磨。...
欢迎 你 发表评论:
- 一周热门
- 最近发表
-
- 30天学会Python编程:16. Python常用标准库使用教程
- 强烈推荐!Python 这个宝藏库 re 正则匹配
- Python爬虫中正则表达式的用法，只讲如何应用，不讲原理
- Python数据分析实战-正则提取文本的URL网址和邮箱(源码和效果)
- python爬虫教程之爬取当当网 Top 500 本五星好评书籍
- 深入理解re模块:Python中的正则表达式神器解析
- 如何使用正则表达式和 Python 匹配不以模式开头的字符串
- 先Mark后用!8分钟读懂 Python 性能优化
- Python“三步”即可爬取，毋庸置疑
- 简单学Python——re库(正则表达式)2(split、findall、和sub)
- 标签列表
-
- idea eval reset (50)
- vue dispatch (70)
- update canceled (42)
- order by asc (53)
- spring gateway (67)
- 简单代码编程 贪吃蛇 (40)
- transforms.resize (33)
- redisson trylock (35)
- 卸载node (35)
- np.reshape (33)
- torch.arange (34)
- npm 源 (35)
- vue3 deep (35)
- win10 ssh (35)
- vue foreach (34)
- idea设置编码为utf8 (35)
- vue 数组添加元素 (34)
- std find (34)
- tablefield注解用途 (35)
- python str转json (34)
- java websocket客户端 (34)
- tensor.view (34)
- java jackson (34)
- vmware17pro最新密钥 (34)
- mysql单表最大数据量 (35)