数据结构：跳表讲解

跳表

    • 1.什么是跳表-skiplist
      • 1.1简介
      • 1.2设计思路
    • 2.跳表的效率分析
    • 3.跳表实现
      • 3.1类成员设计
      • 3.2查找
      • 3.3插入
      • 3.4删除
      • 3.5完整代码
    • 4.skiplist跟平衡搜索树和哈希表的对比

1.什么是跳表-skiplist

1.1简介

skiplist本质上也是一种查找结构，用于解决算法中的查找问题，跟平衡搜索树和哈希表的价值是一样的，可以作为key或者key/value的查找模型。后面我会进行比对。

skiplist是由William Pugh发明的，最早出现于他在1990年发表的论文《Skip Lists: A
Probabilistic Alternative to Balanced Trees》。

skiplist，顾名思义，首先它是一个list。实际上，它是在有序链表的基础上发展起来的。如果是一个有序的链表，查找数据的时间复杂度是O(N)。


1.2设计思路


（1）假如我们每相邻两个节点升高一层，增加一个指针，让指针指向下下个节点，如下图所示。这样所有新增加的指针连成了一个新的链表，但它包含的节点个数只有原来的一半。由于新增加的指针，我们不再需要与链表中每个节点逐个进行比较了，需要比较的节点数大概只有原来的一半（后面讲为什么）。

在这里插入图片描述
这样设计利于查找，查找规则为：

  1. cur表示当前节点，nextV为节点指针数组，j表示下标，key为要查找的值。 其中cur一开始为哨兵节点，j为顶部下标。
  2. 从cur位置向右看，如果key大于右边，就直接向右走，即更新cur为右节点
    (即cur = cur->nextV[j])。
  3. 如果key小于右边或者右边为空，直接向下走，即让j减一。
  4. 右边等于key找到。
  5. 不存在的情况，j最后会走到-1（看后面图解）。

查找存在的情况：
在这里插入图片描述

查找不存在的情况：
在这里插入图片描述


（2）以此类推，我们可以在第二层新产生的链表上，继续为每相邻的两个节点升高一层，增加一个指针，从而产生第三层链表。如下图，这样搜索效率就进一步提高了。

在这里插入图片描述


（3）skiplist正是受这种多层链表的想法的启发而设计出来的。实际上，按照上面生成链表的方式，上面每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常类似二分查找，使得查找的时间复杂度可以降低到O(log n)。但是这个结构在插入删除数据的时候有很大的问题，插入或者删除一个节点之后，就会打乱上下相邻两层链表上节点个数严格的2:1的对应关系。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也包括新插入的节点）重新进行调整，这会让时间复杂度重新退化成O(n)。


（4）skiplist的设计为了避免这种问题，做了一个大胆的处理，不再严格要求对应比例关系，而是插入一个节点的时候随机出一个层数。这样每次插入和删除都不需要考虑其他节点的层数，这样就好处理多了。细节过程入下图（插入和删除过程后面详细讲，现在只需知道随机层数一样可行）：

在这里插入图片描述



2.跳表的效率分析

上面我们说到，skiplist插入一个节点时随机出一个层数，听起来怎么这么随意，如何保证搜索时的效率呢？

这里首先要细节分析的是这个随机层数是怎么来的。一般跳表会设计一个最大层数maxLevel的限制，其次会设置一个多增加一层的概率p。那么计算这个随机层数的代码如下：

int RandomLevel()
{
     int level = 1;
     //RAND_MAX为rand函数可生成的最大值
     //即rand()落到[0, RAND_MAX * _p]的概率为_p
     while(rand() < RAND_MAX * _p)
     {
         level++;
     }
     return level;
 }

根据前面RandomLevel()，我们很容易看出，产生越高的节点层数，概率越低。定量的分析如下：

  • 节点层数至少为1。而大于1的节点层数，满足一个概率分布。
  • 节点层数恰好等于1的概率为1-p（即第一次就失败）。
  • 节点层数大于等于2的概率为p，而节点层数恰好等于2的概率为p(1-p)（第一次成功，第二次失败）。
  • 节点层数大于等于3的概率为p^2， 而节点层数恰好等于3的概率为p^2*(1-p)。
  • 节点层数大于等于4的概率为p^3， 而节点层数恰好等于4的概率为p^3*(1-p)。
  • ……

因此，一个节点的平均层数（也即包含的平均指针数目），计算如下：
在这里插入图片描述

现在很容易计算出：

  • 当p=1/2时，每个节点所包含的平均指针数目为2；
  • 当p=1/4时，每个节点所包含的平均指针数目为1.33。
  • p越大，平均层数越多，时间效率就越快，但太大可能导致空间浪费，故一般都会限制最大层数。

跳表的平均时间复杂度为O(logN)，我会用图解来帮助大家理解大概，但完整推导的过程较为复杂，需要有一定的数学功底，有兴趣的同学，可以参考以下文章中的讲解：

铁蕾大佬的博客：Redis内部数据结构详解(6)——skiplist

在这里插入图片描述



3.跳表实现

本文跳表实现以本题为准：设计跳表

3.1类成员设计

//跳表节点
struct SkiplistNode
{
    SkiplistNode(int val, int level)
    {
        _val = val;
       _nextV.resize(level, nullptr); 
    }
    int _val;  //节点值
    vector<SkiplistNode*> _nextV;  //指针数组
};

//跳表
class Skiplist {
public:
    typedef SkiplistNode Node;
    Skiplist() {
        srand(time(0));  //设置随机数种子
        _head = new Node(-1, 1);
    }
    
    double _p = 0.25;  //增加层数的概率
    int _maxLevel = 32;  //限制最大层数
    Node* _head;  //哨兵头节点，存储的是无效数据
    //头节点从一层开始，后面生成了更高层数节点在扩容，减少不必要的查询工作
};

3.2查找

参照设计思路里面讲的即可

bool search(int target) 
{
    int level = _head->_nextV.size() - 1;  //下标从顶部开始
    Node* cur = _head;  //从哨兵位开始
    while(level >= 0)
    {
        //大于，跳到下个节点
        //小于或者空，向下走
        if(cur->_nextV[level] && cur->_nextV[level]->_val < target)  
        {
            cur = cur->_nextV[level];
        }
        else if(!cur->_nextV[level] || cur->_nextV[level]->_val > target)  
        {
            level--;
        }
        else  //找到了
        {
            return true;
        }
    }
    return false;
}

3.3插入

思路很简单，假设当前插入节点有x层，只需要找到这x层每一层对应的前置节点，然后做简单的链接工作即可。
在这里插入图片描述

//找前置节点
vector<SkiplistNode*> GetPrev(int num)
{
    //核心是找到每一层的前置节点
    //本题允许冗余
    int level = _head->_nextV.size() - 1;
    vector<SkiplistNode*> prevV(level + 1, nullptr);
    Node* cur = _head;
    while(level >= 0)
    {
        //大于，跳到下个节点
        //小于或者空，向下走
        if(cur->_nextV[level] && cur->_nextV[level]->_val < num)  
        {
            cur = cur->_nextV[level];
        }
        else  
        {
            prevV[level] = cur;
            level--;
        }
    }
    return prevV;
}

//插入节点
void add(int num) {
    vector<SkiplistNode*> prevV = GetPrev(num);
    //生成节点
    int n = RandomLevel();
    Node* newnode = new Node(num, n);
    if(n > _head->_nextV.size())   //节点层数超过当前最大
    {
        _head->_nextV.resize(n, nullptr);
        prevV.resize(n, _head);
    }
    //链接节点
    for(int i = 0; i < n; i++)
    {
        newnode->_nextV[i] = prevV[i]->_nextV[i];
        prevV[i]->_nextV[i] = newnode;
    }
}

3.4删除

删除大体分两种情况：

  1. 存在该节点，思路与插入类似，假设当前删除节点有x层，只需要找到这x层每一层对应的前置节点，然后做简单的链接工作即可。
  2. 不存在该节点，那找前置节点的时候第0层的右边要么是空，要么就不是目标值。

在这里插入图片描述

删除还有个可优化的点，不做也不影响正确性：
在这里插入图片描述

bool erase(int num) {
  vector<SkiplistNode*> prevV = GetPrev(num);
    //随机生成至少有一层节点
    if(prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num)  //不存在
    {
        return false;
    }
    else 
    {
        //记录待删除的节点
        SkiplistNode* del = prevV[0]->_nextV[0];
        for(int i = 0; i < del->_nextV.size(); i++)
        {
            prevV[i]->_nextV[i] = del->_nextV[i];
        }
        delete del;
        //这里不影响正确性，对头节点的多余空间做处理
        int j = _head->_nextV.size() - 1;
        while(j >= 0)
        {
            if(_head->_nextV[j] == nullptr)
            {
                j--;
            }
            else
            {
                break;
            }
        }
        _head->_nextV.resize(j + 1);
        return true;
    }
}

3.5完整代码

struct SkiplistNode
{
    SkiplistNode(int val, int level)
    {
        _val = val;
       _nextV.resize(level, nullptr); 
    }
    int _val;
    vector<SkiplistNode*> _nextV;
};

class Skiplist {
public:
    typedef SkiplistNode Node;
    Skiplist() {
        srand(time(0));
        _head = new Node(-1, 1);
    }
    
    bool search(int target) {
        int level = _head->_nextV.size() - 1;
        Node* cur = _head;
        while(level >= 0)
        {
            //大于，跳到下个节点
            //小于或者空，向下走
            if(cur->_nextV[level] && cur->_nextV[level]->_val < target)  
            {
                cur = cur->_nextV[level];
            }
            else if(!cur->_nextV[level] || cur->_nextV[level]->_val > target)  
            {
                level--;
            }
            else  //找到了
            {
                return true;
            }
        }
        return false;
    }

    vector<SkiplistNode*> GetPrev(int num)
    {
        //核心是找到每一层的前置节点
        //本题允许冗余
        int level = _head->_nextV.size() - 1;
        vector<SkiplistNode*> prevV(level + 1, nullptr);
        Node* cur = _head;
        while(level >= 0)
        {
            //大于，跳到下个节点
            //小于或者空，向下走
            if(cur->_nextV[level] && cur->_nextV[level]->_val < num)  
            {
                cur = cur->_nextV[level];
            }
            else  
            {
                prevV[level] = cur;
                level--;
            }
        }
        return prevV;
    }
    
    void add(int num) {
        vector<SkiplistNode*> prevV = GetPrev(num);
        //链接节点
        int n = RandomLevel();
        Node* newnode = new Node(num, n);
        if(n > _head->_nextV.size())
        {
            _head->_nextV.resize(n, nullptr);
            prevV.resize(n, _head);
        }
        for(int i = 0; i < n; i++)
        {
            newnode->_nextV[i] = prevV[i]->_nextV[i];
            prevV[i]->_nextV[i] = newnode;
        }
    }
    
    bool erase(int num) {
        vector<SkiplistNode*> prevV = GetPrev(num);
        //随机生成至少有一层节点
        if(prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num)  //不存在
        {
            return false;
        }
        else 
        {
            //记录待删除的节点
            SkiplistNode* del = prevV[0]->_nextV[0];
            for(int i = 0; i < del->_nextV.size(); i++)
            {
                prevV[i]->_nextV[i] = del->_nextV[i];
            }
            delete del;
            //这里不影响正确性，对头节点的多余空间做处理
            int j = _head->_nextV.size() - 1;
            while(j >= 0)
            {
                if(_head->_nextV[j] == nullptr)
                {
                    j--;
                }
                else
                {
                    break;
                }
            }
            _head->_nextV.resize(j + 1);
            return true;
        }
    }

    int RandomLevel()
    {
        int level = 1;
        while(rand() < RAND_MAX * _p)
        {
            level++;
        }
        return level;
    }
    double _p = 0.25;
    int _maxLevel = 32;
    Node* _head;
};



4.skiplist跟平衡搜索树和哈希表的对比

  1. skiplist相比平衡搜索树(AVL树和红黑树)对比，都可以做到遍历数据有序，时间复杂度也差不多。
    skiplist的优势是：
    a、skiplist实现简单，容易控制。平衡树增删查改遍历都更复杂。
    b、skiplist的额外空间消耗更低。平衡树节点存储每个值有三叉链，平衡因子/颜色等消耗。skiplist中p=1/2时，每个节点所包含的平均指针数目为2；skiplist中p=1/4时，每个节点所包含的平均指针数目为1.33；
  2. skiplist相比哈希表而言，就没有那么大的优势了哈希表平均时间复杂度是O(1)，比skiplist快。。
    skiplist优势如下：
    a、遍历数据有序b、skiplist空间消耗略小一点，哈希表存在链接指针和表空间消耗。
    b、哈希表扩容有性能损耗。
    c、哈希表再极端场景下哈希冲突高，效率下降厉害，需要红黑树补足接力，实现复杂。

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

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

相关文章

H12-821_30

H12-821_30

30.某交换机运行RSTP协议,其相关配置信息如图所示,请根据命令配置情况指出对于Instance 1,该交换机的角色是: A.根交换机 B.非根交换机 C.交换机 D.无法判断 答案&#xff1a;A 注释&#xff1a; 这道题很容易判断&#xff0c;MSTID表示的是实例ID。实例1上端口的角色都…
阅读更多...
各种手型都合适，功能高度可定制，雷柏VT9PRO mini和VT9PRO游戏鼠标上手

各种手型都合适，功能高度可定制，雷柏VT9PRO mini和VT9PRO游戏鼠标上手

去年雷柏推出了一系列支持4KHz回报率的鼠标&#xff0c;有着非常敏捷的反应速度&#xff0c;在游戏中操作体验十分出色。尤其是这系列4K鼠标不仅型号丰富&#xff0c;而且对玩家的操作习惯、手型适应也很好&#xff0c;像是VT9系列就主打轻巧&#xff0c;还有专门针对小手用户的…
阅读更多...
深度学习图像处理基础

深度学习图像处理基础

这里写目录标题 分辨率是什么 视网膜屏视网膜屏人眼的视觉视力 像素密度设置合适的PPI&#xff0c;制造视网膜屏 色彩是什么色匹配实验色彩匹配的意义量化色彩匹配白色合为1色度图 总结 HDR光亮度&#xff08;尼特&#xff09;灰阶亮度范围HDR显示技术总结 一级目录二级目录二级…
阅读更多...
Element UI 组件的安装及使用

Element UI 组件的安装及使用

Element UI 组件的安装及使用 Element UI 是一套基于 Vue.js 的桌面端 UI 组件库&#xff0c;提供了丰富的、高质量的 UI 组件&#xff0c;可以帮助开发者快速构建用户界面。 1、安装 Element UI 使用 npm 安装 npm install element-ui -S2、使用 CDN 安装 在 HTML 页面中引…
阅读更多...
redis 异步队列

redis 异步队列

//produceMessage.ts 模拟生产者 import Redis from ioredis; const redis new Redis(); // 生产者&#xff1a;将消息推送到队列 async function produceMessage(queueName:string, message:string) {try {await redis.rpush(queueName, message);console.log(Produced messa…
阅读更多...
Mysql 8.0新特性详解

Mysql 8.0新特性详解

建议使用8.0.17及之后的版本&#xff0c;更新的内容比较多。 1、新增降序索引 MySQL在语法上很早就已经支持降序索引&#xff0c;但实际上创建的仍然是升序索引&#xff0c;如下MySQL 5.7 所示&#xff0c;c2字段降序&#xff0c;但是从show create table看c2仍然是升序。8.0…
阅读更多...
Unity—JSON

Unity—JSON

每日一句&#xff1a;手简素中&#xff0c;感生活恬淡&#xff0c;心有所期&#xff0c;忙而不茫 目录 服务器 常见的服务器语言 Unity的开发语言 JSON 功能&#xff1a; JSON最简单的格式 JSON工具 支持的数据结构&#xff08;C#对于JSON&#xff09; 字符含义 JSON…
阅读更多...
Java Web(六）--XML

Java Web(六）--XML

介绍 官网&#xff1a;XML 教程 为什么需要&#xff1a; 需求 1 : 两个程序间进行数据通信&#xff1f;需求 2 : 给一台服务器&#xff0c;做一个配置文件&#xff0c;当服务器程序启动时&#xff0c;去读取它应当监听的端口号、还有连接数据库的用户名和密码。spring 中的…
阅读更多...
箱形理论在交易策略中的实战应用与优化

箱形理论在交易策略中的实战应用与优化

箱形理论&#xff0c;简单来说&#xff0c;就是将价格波动分成一段一段的方框&#xff0c;研究这些方框的高点和低点&#xff0c;来推测价格的趋势。 在上升行情中&#xff0c;价格每突破新高价后&#xff0c;由于群众惧高心理&#xff0c;可能会回跌一段&#xff0c;然后再上升…
阅读更多...
2024年了，如何从 0 搭建一个 Electron 应用

2024年了，如何从 0 搭建一个 Electron 应用

简介 Electron 是一个开源的跨平台桌面应用程序开发框架&#xff0c;它允许开发者使用 Web 技术&#xff08;如 JavaScript、HTML 和 CSS&#xff09;来构建桌面应用程序。Electron 嵌入了 Chromium&#xff08;一个开源的 Web 浏览器引擎&#xff09;和 Node.js&#xff08;一…
阅读更多...
最新Unity游戏主程进阶学习大纲(2个月)

最新Unity游戏主程进阶学习大纲(2个月)

过完年了&#xff0c;很多同学开始重新规划自己的职业方向,找更好的机会,准备升职或加薪。今天给那些工作了1~5年的开发者梳理”游戏开发客户端主程”的学习大纲&#xff0c;帮助大家做好面试准备。适合Unity客户端开发者。进阶主程其实就是从固定的几个方面搭建好完整的知识体…
阅读更多...
【Spring】IoC容器 控制反转 与 DI依赖注入 XML实现版本 第二期

【Spring】IoC容器 控制反转 与 DI依赖注入 XML实现版本 第二期

文章目录 基于 XML 配置方式组件管理前置 准备项目一、 组件&#xff08;Bean&#xff09;信息声明配置&#xff08;IoC&#xff09;&#xff1a;1.1 基于无参构造1.2 基于静态 工厂方法实例化1.3 基于非静态 工厂方法实例化 二、 组件&#xff08;Bean&#xff09;依赖注入配置…
阅读更多...
Docker vs VM

Docker vs VM

关于应用程序的托管和开发&#xff0c;市场中的技术和产品琳琅满目。对比 Docker 和 VM&#xff0c;如何取舍&#xff1f;这主要由自身团队的因素决定&#xff0c;在选择 Docker 的情况下&#xff0c;你需要保证程序可在容器和虚拟机中运行。另外&#xff0c;成本和易用性也是重…
阅读更多...
前端跨域问题解决，本地代理到域名

前端跨域问题解决，本地代理到域名

1.学习黑马uniapp时遇见的问题: 报跨域错误 但是已经设置了代理&#xff0c;仍然无效。 2.解决&#xff08;多次遇见此问题&#xff0c;特此记录&#xff09;&#xff1a; 最后发现是这里少写了/api&#xff0c;遇见以api开头的接口&#xff0c;则把这些接口转发到target所指向…
阅读更多...
32单片机基础：GPIO输出

32单片机基础：GPIO输出

目录 简介&#xff1a; GPIO输出的八种模式 STM32的GPIO工作方式 GPIO支持4种输入模式&#xff1a; GPIO支持4种输出模式&#xff1a; 浮空输入模式 上拉输入模式 下拉输入模式 模拟输入模式&#xff1a; 开漏输出模式&#xff1a;&#xff08;PMOS无效&#xff0c;就…
阅读更多...
详细分析Python中的Pyautogui库（附Demo）

详细分析Python中的Pyautogui库（附Demo）

目录 前言1. 基本知识2. 常用方法2.1 通用方法2.2 鼠标操作2.3 消息窗口2.4 截图 前言 该博客主要以入门了解其函数为主&#xff0c;灵活运用&#xff0c;后续会出一些实战结合类&#xff01; 1. 基本知识 PyAutoGUI 是 Python 的一个库&#xff0c;用于实现自动化的图形用户…
阅读更多...
信号系统之连续信号处理

信号系统之连续信号处理

1 Delta 函数 连续信号可以分解为缩放和移位的增量函数&#xff0c;就像处理离散信号一样。不同之处在于&#xff0c;连续 delta 函数比其离散函数复杂得多&#xff0c;在数学上也抽象得多。我们不是用它是什么来定义连续 delta 函数&#xff0c;而是用它所具有的特征来定义它…
阅读更多...
【眼科大模型】Ophtha-LLaMA2：视觉模型提取图像特征 + LLM基于特征生成眼底病变的诊断报告

【眼科大模型】Ophtha-LLaMA2：视觉模型提取图像特征 + LLM基于特征生成眼底病变的诊断报告

Ophtha-LLaMA2&#xff1a;视觉模型提取图像特征 LLM基于特征生成眼底病变的诊断报告 提出背景设计思路选择大模型基座生成诊断报告 论文&#xff1a;https://arxiv.org/pdf/2312.04906.pdf 提出背景 目标是开发一个全面的眼科模型&#xff0c;可以根据不同仪器的检查报告准确…
阅读更多...
GitHub | 在 GitHub 上在线展示 Vue 项目

GitHub | 在 GitHub 上在线展示 Vue 项目

简洁版&#xff1a;上传所有代码 << 构建项目并上传 dist 目录 << 设置仓库 << 访问 Step1&#xff1a;在 GitHub 上新建仓库&#xff0c;并将 Vue 项目的代码 push 到该仓库中。坑点在于&#xff0c;如果你是从 GitHub 上 clone 的别人的项目&#xff0c;那…
阅读更多...
vulnhub练习 DC-1复现及分析

vulnhub练习 DC-1复现及分析

一、搭建环境 1.工具 靶机&#xff1a;DC-1 192.168.200.17 攻击机&#xff1a;kali 192.168.200.13 2.注意 攻击机和靶机的网络连接方式要相同&#xff0c;另外DC-1的网络连接方式我这里采用NAT模式&#xff0c;是与kali的网络连接模式相同的&#xff08;当然亦可以选用桥…
阅读更多...
最新文章

Copyright @ 2022~2023