7.跳表Skip List

2024-02-09 02:58
文章标签 list skip 跳表

本文主要是介绍7.跳表Skip List,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

什么是跳表?

二分查找底层依赖的是数组随机访问的特性。如果是一个链表,如何支持二分查找呢,就是给这个链表建立多层的索引,如下图所示,这种数据结构叫做跳表。
在这里插入图片描述在跳表中,每两个结点会抽出一个结点作为上一级索引的结点,对于大小为n的链表来讲,第一级索引的结点个数大约就是 n/2,第二级索引的结点个数大约就是 n/4,第三级索引的结点个数大约就是 n/8,依次类推,也就是说,第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2,那第 k级索引结点的个数就是 n/(2K)。

假设索引有 h 级,最高级的索引有 2 个结点。通过上面的公式,我们可以得到 n/(2K)=2,从而
求得 h=log2n-1。如果包含原始链表这一层,整个跳表的高度就是log2n

我们在跳表中查询某个数据的时候,如果每一层都要遍历 m 个结点,那在跳表中查询一个数据的时间复杂度就是O(m*logn)。每层遍历最多3个节点,因为第一层为2个,假设为x,y。判处出在x和y之间,下滑到下一层,对应的是3个节点,最多分别比对一次后获的到应该下滑的下一层位置。
跳表更加的占用空间,是利用空间换时间的思路。为了减少空间的存储,我们也可以调整为3个节点抽取一个索引。

优秀的动态数据结构,不仅支持查找操作,还支持动态的插入、删除操作,跳表的插入、删除操作的时间复杂度也是 O(logn)。

插入算法分析

在单链表中,一旦定位好要插入的位置,插入结点的时间复杂度是很低的,就是O(1)。但是,这里为了保证原始链表中数据的有序性,我们需要先找到要插入的位置,这个查找操作就会比较耗时。对于纯粹的单链表,需要遍历每个结点,来找到插入的位置。但是,对于跳表来说,我们讲过查找某个结点的的时间复杂度是 O(logn),所以这里查找某个数据应该插入的位置,方法也是类似的,时间复杂度也是 O(logn)。

删除算法分析

如果这个结点在索引中也有出现,我们除了要删除原始链表中的结点,还要删除索引中的。因为单链表中的删除操作需要拿到要删除结点的前驱结点,然后通过指针操作完成删除。所以在查找要删除的结点的时候,一定要获取前驱结点。当然,如果我们用的是双向链表,就不需要考虑这个问题了。

跳表索引动态更新

  当我们不停地往跳表中插入数据时,如果我们不更新索引,就有可能出现某 2 个索引结点之间数据非常多的情况。极端情况下,跳表还会退化成单链表。所以需要在插入数据的时候,选择同时将这个数据插入到部分索引层中。我们常通过通过一个随机函数,来决定将这个结点插入到哪几级索引中,比如随机函数生成了值 K,那我们就将这个结点添加到第一级到第 K 级这 K 级索引中。
  随机函数的选择很有讲究,从概率上来讲,能够保证跳表的索引大小和数据大小平衡性,不至于性能过度退化。Redis 中关于有序集合就是用跳表实现的。

这篇关于7.跳表Skip List的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/692943

相关文章

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

Collection List Set Map的区别和联系

Collection List Set Map的区别和联系 这些都代表了Java中的集合,这里主要从其元素是否有序,是否可重复来进行区别记忆,以便恰当地使用,当然还存在同步方面的差异,见上一篇相关文章。 有序否 允许元素重复否 Collection 否 是 List 是 是 Set AbstractSet 否

【Python报错已解决】AttributeError: ‘list‘ object has no attribute ‘text‘

🎬 鸽芷咕:个人主页  🔥 个人专栏: 《C++干货基地》《粉丝福利》 ⛺️生活的理想,就是为了理想的生活! 文章目录 前言一、问题描述1.1 报错示例1.2 报错分析1.3 解决思路 二、解决方法2.1 方法一:检查属性名2.2 步骤二:访问列表元素的属性 三、其他解决方法四、总结 前言 在Python编程中,属性错误(At

List list = new ArrayList();和ArrayList list=new ArrayList();的区别?

List是一个接口,而ArrayList 是一个类。 ArrayList 继承并实现了List。 List list = new ArrayList();这句创建了一个ArrayList的对象后把上溯到了List。此时它是一个List对象了,有些ArrayList有但是List没有的属性和方法,它就不能再用了。而ArrayList list=new ArrayList();创建一对象则保留了A

处理List采用并行流处理时,通过ForkJoinPool来控制并行度失控的问题

在使用parallelStream进行处理list时,如不指定线程池,默认的并行度采用cpu核数进行并行,这里采用ForJoinPool来控制,但循环中使用了redis获取key时,出现失控。具体上代码。 @RunWith(SpringRunner.class)@SpringBootTest(classes = Application.class)@Slf4jpublic class Fo

Java中集合类Set、List和Map的区别

Java中的集合包括三大类,它们是Set、List和Map,它们都处于java.util包中,Set、List和Map都是接口,它们有各自的实现类。Set的实现类主要有HashSet和TreeSet,List的实现类主要有ArrayList,Map的实现类主要有HashMap和TreeMap。那么它们有什么区别呢? Set中的对象不按特定方式排序,并且没有重复对象。但它的有些实现类能对集合中的对

List对象过滤

List materialInventoryList = materialInventories.stream().filter(mat -> mat.getQty().compareTo(BigDecimal.ZERO) > 0).collect(Collectors.toList()); stream().filter()方法可以过滤掉List的数据

c++stack和list 介绍

stack介绍 堆栈是一种容器适配器,专门设计用于在 LIFO 上下文(后进先出)中运行,其中元素仅从容器的一端插入和提取。 堆栈作为容器适配器实现,容器适配器是使用特定容器类的封装对象作为其基础容器 的类,提供一组特定的成员函数来访问其元素。元素从特定容器的 “back” 推送或弹出,这称为堆栈的顶部。 stack接口 stack() 构造空的栈 empty() 检测stack是否为

python+selenium2学习笔记unittest-04装饰器skip用法

在运行测试用例时,有时需跳过或判断用例时,可以用装饰器来实现 主要的几个方法就是下面的这几种 import unittestclass test(unittest.TestCase):def setUp(self):pass@unittest.skip('跳过')def test_01(self):print("直接跳过")@unittest.skipIf(3>2,'当条件为TRUE跳过')

C++——list的实现

目录 0.前言 1.节点类  2.迭代器类  ①普通迭代器 ②const迭代器  ③模板迭代器 3.list类  3.1 clear、析构函数、swap ①clear ② 析构函数  ③ swap 3.2构造函数  ①无参构造  ②赋值构造 3.3 迭代器 3.4插入函数 ①insert插入 ②头插 ③尾插 3.5 删除函数 ①erase删除 ②头删