数据结构 跳表SkipList的原理和代码实现

2024-04-01 15:08

本文主要是介绍数据结构 跳表SkipList的原理和代码实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

跳表简介

跳表是平衡树的一种替代的数据结构,但是和红黑树不相同的是,跳表对于树的平衡的实现是基于一种随机化的算法的,这样也就是说跳表的插入和删除的工作是比较简单的。

我们知道,普通单链表查询一个元素的时间复杂度为O(n),即使该单链表是有序的,我们也不能通过2分的方式缩减时间复杂度。

这里写图片描述

如上图,我们要查询元素为55的结点,必须从头结点,循环遍历到最后一个节点,不算-INF(负无穷)一共查询8次。那么用什么办法能够用更少的次数访问55呢?最直观的,当然是新开辟一条捷径去访问55。

这里写图片描述

如上图,我们要查询元素为55的结点,只需要在L2层查找4次即可。在这个结构中,查询结点为46的元素将耗费最多的查询次数5次。即先在L2查询46,查询4次后找到元素55,因为链表是有序的,46一定在55的左边,所以L2层没有元素46。然后我们退回到元素37,到它的下一层即L1层继续搜索46。非常幸运,我们只需要再查询1次就能找到46。这样一共耗费5次查询。

那么,如何才能更快的搜寻55呢?有了上面的经验,我们就很容易想到,再开辟一条捷径。

这里写图片描述

如上图,我们搜索55只需要2次查找即可。这个结构中,查询元素46仍然是最耗时的,需要查询5次。即首先在L3层查找2次,然后在L2层查找2次,最后在L1层查找1次,共5次。很显然,这种思想和2分非常相似,那么我们最后的结构图就应该如下图。
这里写图片描述

我们可以看到,最耗时的访问46需要6次查询。即L4访问55,L3访问21、55,L2访问37、55,L1访问46。我们直觉上认为,这样的结构会让查询有序链表的某个元素更快。那么究竟算法复杂度是多少呢?

如果有n个元素,因为是2分,所以层数就应该是log n层 (本文所有log都是以2为底),再加上自身的1层。以上图为例,如果是4个元素,那么分层为L3和L4,再加上本身的L2,一共3层;如果是8个元素,那么就是3+1层。最耗时间的查询自然是访问所有层数,耗时logn+logn,即2logn。为什么是2倍的logn呢?我们以上图中的46为例,查询到46要访问所有的分层,每个分层都要访问2个元素,中间元素和最后一个元素。所以时间复杂度为O(logn)

实现跳跃表

插入

跳跃表的初试状态如下图,表中没有一个元素:

这里写图片描述

如果我们要插入元素2,首先是在底部插入元素2,如下图:

这里写图片描述

然后我们抛硬币,结果是正面,那么我们要将2插入到L2层,如下图
这里写图片描述

继续抛硬币,结果是反面,那么元素2的插入操作就停止了,插入后的表结构就是上图所示。接下来,我们插入元素33,跟元素2的插入一样,现在L1层插入33,如下图:

这里写图片描述

然后抛硬币,结果是反面,那么元素33的插入操作就结束了,插入后的表结构就是上图所示。接下来,我们插入元素55,首先在L1插入55,插入后如下图:

这里写图片描述

然后抛硬币,结果是正面,那么L2层需要插入55,如下图:

这里写图片描述

继续抛硬币,结果又是正面,那么L3层需要插入55,如下图:

这里写图片描述

继续抛硬币,结果又是正面,那么要在L4插入55,结果如下图:

这里写图片描述

继续抛硬币,结果是反面,那么55的插入结束,表结构就如上图所示。

以此类推,我们插入剩余的元素。当然因为规模小,结果很可能不是一个理想的跳跃表。但是如果元素个数n的规模很大,学过概率论的同学都知道,最终的表结构肯定非常接近于理想跳跃表。

搜索

这里写图片描述
例子:查找元素 117
(1) 比较 21, 比 21 大,往后面找
(2) 比较 37, 比 37大,比链表最大值小,从 37 的下面一层开始找
(3) 比较 71, 比 71 大,比链表最大值小,从 71 的下面一层开始找
(4) 比较 85, 比 85 大,从后面找
(5) 比较 117, 等于 117, 找到了节点。

/* 如果存在 x, 返回 x 所在的节点, * 否则返回 x 的后继节点 */  
find(x)   
{  p = top;  while (1) {  while (p->next->key < x)  p = p->next;  if (p->down == NULL)   return p->next;  p = p->down;  }  
}  

删除

在各个层中找到包含 x 的节点,使用标准的 delete from list 方法删除该节点。
例子:删除 71

这里写图片描述

Java的跳表实现

表节点SkipListNode

package com.hqq.list;import java.net.CacheRequest;/*** SkipListNode* 跳跃表的节点,包括key-value和上下左右4个指针* Created by heqianqian on 2017/6/1.*/
public class SkipListNode<T> {private int key;private T value;public SkipListNode<T> up, down, left, right;public static final int HEAD_KEY = Integer.MIN_VALUE;//负无穷public static final int TAIL_KEY = Integer.MAX_VALUE;//正无穷public SkipListNode(int k, T v) {this.key = k;this.value = v;}public int getKey() {return key;}public void setKey(int key) {this.key = key;}public T getValue() {return value;}public void setValue(T value) {this.value = value;}@SuppressWarnings("unchecked")public boolean equals(Object o) {if (this == o) {return true;}if (o == null) {return false;}if (!(o instanceof SkipListNode<?>)) {return false;}SkipListNode<T> ent;try {ent = (SkipListNode<T>) o;} catch (Exception e) {return false;}return (ent.getKey() == key) && (ent.getValue() == value);}@Overridepublic String toString() {return "key-value:"+key+"-"+value;}
}

跳表SkipList

package com.hqq.list;import java.util.Comparator;
import java.util.Random;/*** SkipList* 不固定层级的跳跃表* Created by heqianqian on 2017/6/1.*/
public class SkipList<T extends Comparable<? super T>> {private SkipListNode<T> head, tail;private int nodes;//节点总数private int listLevel;//层数private Random random;//用于产生随机数private static final double PROBABILITY = 0.5;//向上提升一个的概率public SkipList() {random = new Random();clear();}/*** 清空跳跃表*/public void clear() {head = new SkipListNode<T>(SkipListNode.HEAD_KEY, null);tail = new SkipListNode<T>(SkipListNode.TAIL_KEY, null);horizontalLink(head, tail);listLevel = 0;nodes = 0;}/*** 水平双向连接*/private void horizontalLink(SkipListNode<T> node1, SkipListNode<T> node2) {node1.right = node2;node2.left = node1;}/*** 垂直双向连接*/private void vertiacallLink(SkipListNode<T> node1, SkipListNode<T> node2) {node1.down = node2;node2.up = node1;}/*** 在最下面一层,找到要插入的位置前面的那个key*/private SkipListNode<T> findNode(int key) {SkipListNode<T> p = head;while (true) {while (p.right.getKey() != SkipListNode.TAIL_KEY && p.right.getKey() <= key) {p = p.right;}if (p.down != null) {p = p.down;} else {break;}}return p;}/*** 查找是否存储key,存在则返回该节点,否则返回null*/public SkipListNode<T> search(int key) {SkipListNode<T> p = findNode(key);return (key == p.getKey()) ? p : null;}/*** 向跳跃表中添加key-value*/public void put(int k, T v) {SkipListNode<T> p = findNode(k);//如果key值相同,替换原来的vaule即可结束if (k == p.getKey()) {p.setValue(v);return;}SkipListNode<T> q = new SkipListNode<T>(k, v);backLink(p, q);int currentLevel = 0;//当前所层次是0//产生随机数while (random.nextDouble() < PROBABILITY) {//新建一个层if (currentLevel >= listLevel) {listLevel++;SkipListNode<T> p1 = new SkipListNode<T>(SkipListNode.HEAD_KEY, null);SkipListNode<T> p2 = new SkipListNode<T>(SkipListNode.TAIL_KEY, null);horizontalLink(p1, p2);vertiacallLink(p1, head);vertiacallLink(p2, tail);head = p1;tail = p2;}//把p移动到上一层while (p.up == null) {p = p.left;}p = p.up;SkipListNode<T> e = new SkipListNode<T>(k, null);backLink(p, e);vertiacallLink(e, q);q = e;currentLevel++;}nodes++;}/*** 在node1后插入node2*/private void backLink(SkipListNode<T> node1, SkipListNode<T> node2) {node2.left = node1;node2.right = node1.right;node1.right.left = node2;node1.right = node2;}public boolean isEmpty() {return nodes == 0;}public int size() {return nodes;}@Overridepublic String toString() {if (isEmpty()) {return "跳跃表为空";}StringBuilder builder = new StringBuilder();SkipListNode<T> p = head;while (p.down != null) {p = p.down;}while (p.left != null) {p = p.left;}if (p.right != null) {p = p.right;}while (p.right != null) {builder.append(p);builder.append("\n");p = p.right;}return builder.toString();}
}

测试

package com.hqq.list;/*** SkipListTest* Created by heqianqian on 2017/6/1.*/
public class SkipListTest {public static void main(String[] args) {SkipList<String> list = new SkipList<>();System.out.println(list);list.put(2, "he");list.put(1, "qianqian");list.put(1, "qianqian");//测试同一个key值list.put(3, "何");list.put(4, "芊");System.out.println(list);System.out.println(list.size());}
}

测试结果

跳跃表为空
key-value:1-qianqian
key-value:2-he
key-value:3-何
key-value:4-芊4

参考文章
http://www.cnblogs.com/acfox/p/3688607.html
http://kenby.iteye.com/blog/1187303

这篇关于数据结构 跳表SkipList的原理和代码实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

深入探索协同过滤:从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤(UserCF)2. 基于物品的协同过滤(ItemCF)3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代,推荐系统成为连接用户与内容的桥梁。本文聚焦于

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

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

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

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

hdu4407(容斥原理)

题意:给一串数字1,2,......n,两个操作:1、修改第k个数字,2、查询区间[l,r]中与n互质的数之和。 解题思路:咱一看,像线段树,但是如果用线段树做,那么每个区间一定要记录所有的素因子,这样会超内存。然后我就做不来了。后来看了题解,原来是用容斥原理来做的。还记得这道题目吗?求区间[1,r]中与p互质的数的个数,如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount