数据结构学习——skiplist跳表

数据结构学习——skiplist跳表目录1.skiplist简介2.skiplist核心思想3.skiplist原理3.1跳表的查找3.2跳表的插入3.3跳表的删除4.skiplist简单实现1.skiplist简介Skiplist是一个用于有序元素序列快速搜索的数据结构,由美国计算机科学家WilliamPugh发明于1989年。他在论文《Skiplists:aprobabilisticalternativetobalancedtrees》中详细介绍了跳表的数据结构和插入删除等…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

目录

 

1.skiplist简介

2.skiplist核心思想

3.skiplist原理

 3.1 跳表的查找

3.2 跳表的插入

3.3 跳表的删除

4.skiplist简单实现


1.skiplist简介

Skiplist是一个用于有序元素序列快速搜索数据结构,由美国计算机科学家William Pugh发明于1989年。他在论文《Skip lists: a probabilistic alternative to balanced trees》中详细介绍了跳表的数据结构和插入删除等操作。论文是这么介绍跳表的:

  • Skip lists are a data structure that can be used in place of balanced trees.
  • Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

也就是说,Skip list是一个“概率型”的数据结构,可以在很多应用场景中替代平衡树。Skip list算法与平衡树相比,有相似的渐进期望时间边界,但是它更简单,更快,使用更少的空间。 参考算法导论,跳表插入、删除、查找的复杂度均为O(logN)。

选择跳表的原因:

  • 目前经常使用的平衡数据结构有:B树,红黑树,AVL树,Splay Tree, Treep等,但是实现细节过于复杂。
  • 相比之下,跳表的原理相当简单,只要你能熟练操作链表,就能轻松实现一个 SkipList。目前开源软件 Redis 和 LevelDB 都有用到它。

2.skiplist核心思想

先从链表开始,如果是一个单链表,那么我们知道在链表中查找一个元素I的话,需要将整个链表遍历一次,时间复杂度为O(n)。

数据结构学习——skiplist跳表

如果是说链表是排序的,并且结点中还存储了指向后面第二个结点的指针的话,那么在查找一个结点时,仅仅需要遍历N/2个结点即可。因此查找的时间复杂度为O(n/2)。

数据结构学习——skiplist跳表

其实,上面基本上就是跳跃表的思想,每一个结点不单单只包含指向下一个结点的指针,可能包含很多个指向后续结点的指针,这样就可以跳过一些不必要的结点,从而加快查找、删除等操作。对于一个链表内每一个结点包含多少个指向后续元素的指针,这个过程是通过一个随机函数生成器得到,这样子就构成了一个跳跃表。这就是为什么论文“Skip Lists : A Probabilistic Alternative to Balanced Trees ”中有“概率”的原因了,就是通过随机生成一个结点中指向后续结点的指针数目。随机生成的跳跃表可能如下图所示。

数据结构学习——skiplist跳表

如果一个结点存在k个指向后续元素指针的话,那么称该结点是一个k层结点。一个跳表的层MaxLevel义为跳表中所有结点中最大的层数。跳表的所有操作均从上向下逐层进行,越上层一次next操作的跨度越大。

3.skiplist原理

skiplist的结构定义如下:

  1. 由多层结构组成;
  2. 每一层都是一个有序的链表;
  3. 最底层(Level 1)的链表包含所有元素;
  4. 如果一个元素出现在 Level i 的链表中,则它在 Level i 之下的链表也都会出现;
  5. 每个节点包含两个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素。

为了便于描述,将跳表结构绘画成如下形式。

数据结构学习——skiplist跳表

 3.1 跳表的查找

数据结构学习——skiplist跳表

例子:查找元素 117,会经历如下几个步骤:

  1.  比较 21, 比 21 大,往后面找
  2.  比较 37,   比 37大,比链表最大值小,从 37 的下面一层开始找
  3.  比较 71,  比 71 大,比链表最大值小,从 71 的下面一层开始找
  4.  比较 85, 比 85 大,从后面找
  5.  比较 117, 等于 117, 找到了节点。

3.2 跳表的插入

1)K小于链表的层数

先确定该元素要占据的层数 K(采用丢硬币的方式,这完全是随机的),然后在 Level 1 … Level K 各个层的链表都插入元素。
例子:插入 119, K = 2

数据结构学习——skiplist跳表

2)K大于链表的层数

如果 K 大于链表的层数,则要添加新的层。
例子:插入 119, K = 4

数据结构学习——skiplist跳表

插入元素的时候,元素所占有的层数完全是随机的,通过某种随机算法产生。

3.3 跳表的删除

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

例子:删除 71

数据结构学习——skiplist跳表

4.skiplist简单实现

增加层数的方案用的是抛硬币,即根据随机数来确定是否增加“快线”,这也是MIT公开课上给出的一个比较简单的实现方法。

头文件定义如下,使用prev,next,down,top来表示Node节点之间的指向,即前、后、下、上。

//SkipList.h
#ifndef __SKIPLIST_H__
#define __SKIPLIST_H__
 
#include <climits>
#include <cstdlib>
#include <ctime>
#include <cmath>
 
class Skiplist {
private :
    struct Node {
        int key;
        Node * prev;
        Node * next;
        Node * down;
        Node * top;
        Node() : key(0), prev(nullptr), next(nullptr), down(nullptr), top(nullptr) {}
    };
private :
    Node * head;
    int level;
    int size;
private :
    void bindNewNode(Node * x, Node * p);
    void delNode(Node * x);
    Node * searchNode(int key);
public :
    Skiplist() : head(new Node), level(1),size(0)
        {head->key = INT_MIN; srand(static_cast<int>(time(0)));}
    ~Skiplist() {delete head;}
    void insert(int key);
    void remove(int key);
    bool search(int key) {return (searchNode(key) != nullptr);}
    void showSkiplist();
    int getLevel() {return level;}
    int getSize() {return size;}
};
 
#endif // __SKIPLIST_H__

函数实现:

//Skiplist.cpp
#include <iostream>
#include "SkipList.h"
 
using namespace std;

void Skiplist::bindNewNode(Node * x, Node * p) {
    if (!x->next) {
        x->next = p;
        p->prev = x;
    }
    else {
        p->next = x->next;
        x->next->prev = p;
        p->prev = x;
        x->next = p;
    }
}

void Skiplist::insert(int key) {
    Node * p = new Node;
    p->key = key;

    Node * x = head;
    while (1) { //find the prev node of p, which represents the right insert place
        if (x->key <= key) {
            if (x->next)
                x = x->next;
            else if (x->down)
                x = x->down;
            else break;
        }
        else if (x->prev->down)
            x = x->prev->down;
        else {
            x = x->prev;
            break;
        }
    }
    bindNewNode(x, p);
    while (rand() % 2) {  //throw the coin, then judge whether it needs to be higher according to the results
        Node * highp = new Node;
        highp->key = key;
        while (!x->top && x->prev)
            x = x->prev;
        if (x->top) {
            x = x->top;
            bindNewNode(x, highp);
            highp->down = p;
            p->top = highp;
        }
        else { //already the top, add a sentry
            Node * top = new Node;
            x = top;
            top->key = INT_MIN;
            top->down = head;
            head->top = top;
            head = top;
            bindNewNode(top, highp);
            highp->down = p;
            p->top = highp;
            ++level;
        }
        p = highp;
    }
    ++size;
}

void Skiplist::delNode(Node * x) {
    if (!x->next) { //node x is the last one
        if (x->prev == head && head->down) { //x is not at the bottom and x is the last one of this level
            head = head->down;
            head->top = nullptr;
            delete x->prev;
            --level;
        }
        else
            x->prev->next = nullptr;
    }
    else {
        x->prev->next = x->next;
        x->next->prev = x->prev;
    }
    delete x;
}

void Skiplist::remove(int key) {
    Node * x = searchNode(key);
    if (x) {
        while (x->down) {
            Node * y = x->down;
            delNode(x);
            x = y;
        }
        delNode(x);
        --size;
    }
}

Skiplist::Node * Skiplist::searchNode(int key) {
    Node * x = head;
    while (1) { //find the prev node of p, which represents the right insert place
        if (x->key == key)
            return x;
        else if (x->key < key) {
            if (x->next)
                x = x->next;
            else if (x->down)
                x = x->down;
            else
                return nullptr;
        }
        else if (x->prev->down)
            x = x->prev->down;
        else {
            return nullptr;
        }
    }
}

void Skiplist::showSkiplist() {
    Node * x = head, * y = head;
    while (y) {
        x = y;
        while (x) {
            if (x->prev != nullptr)
                cout << x->key << ' ';
            x = x->next;
        }
        cout << endl;
        y = y->down;
    }
}

主函数和执行结果:

//main.cpp
#include "SkipList.h"

int main()
{
	Skiplist* m_Skiplist = new Skiplist();
	
	m_Skiplist->insert(7);
    m_Skiplist->insert(14);
    m_Skiplist->insert(21);
    m_Skiplist->insert(32);
    m_Skiplist->insert(37);
    m_Skiplist->insert(71);
    m_Skiplist->insert(85);
	
	m_Skiplist->showSkiplist();

	return 0;
}

————————————————————————————————————————————————————
使用方法,创建g++ -std=c++11 -o main main.cpp SkipList.cpp 生成main可执行文件

因为增加层数的方案用的是抛硬币,每次执行结果生成的level层数不一致,如下:

[root@192 skiplist1]# ./main
7 14 32
7 14 32 37
7 14 32 37 85
7 14 32 37 71 85
7 14 21 32 37 71 85
[root@192 skiplist1]# ./main
21
21
21
7 14 21 32 71
7 14 21 32 37 71 85
[root@192 skiplist1]# ./main
21
21
21
21
21
21 32
21 32 37
7 14 21 32 37 71 85


参考链接:https://blog.csdn.net/caoshangpa/article/details/78862339

参考链接:https://www.cnblogs.com/yxsrt/p/12249745.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/179611.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • IIS中WEB服务器的日志存放到SQL Server 2005中

    IIS中WEB服务器的日志存放到SQL Server 2005中

  • HTML如何加背景图片_css设置背景图片

    HTML如何加背景图片_css设置背景图片在HTML中,我们可以使用两种不同的方法在HTML网页上显示背景图片:使用背景属性(HTML标签)使用CSS内部样式表提示:HTML5不再支持标签的background属性,建议使用CSS在Html文档中添加背景图片。使用背景属性使用Background属性在Html文档中添加背景图片。按照以下步骤,我们可以轻松实现。步骤1:我们在文本编辑器中键入HTML代码,或者用文本编辑器打开现有的HTML文件。<!DOCTYPEhtml><html><hea

  • 50分钟学会Laravel 50个小技巧(基于laravel5.2,仅供参考)

    50分钟学会Laravel 50个小技巧(基于laravel5.2,仅供参考)

  • java面试题及答案整理_nginx优化面试

    java面试题及答案整理_nginx优化面试nginx负载均衡的算法怎么实现的nginx的upstream目前支持4种方式的分配1)、轮询(默认)每个请求按时间顺序逐一分配到不同的后端服务器,如果后端服务器down掉,能自动剔除。2)、weight指定轮询几率,weight和访问比率成正比,用于后端服务器性能不均的情况。2)、ip_hash每个请求按访问ip…

  • MATLAB GUI编程总结

    MATLAB GUI编程总结MATLABGUI编程总结:创建MatlabGUI界面通常有两种方式:1使用.m文件直接动态添加控件2使用GUIDE快速的生成GUI界面一、创建GUI方法一.:在.m文件中动态添加h_main=figure(‘name’,‘ademoofguidesign’,‘menubar’,‘none’,…’numbertitle’,’off’,’posi…

  • intellij idea运行配置_idea2017配置jdk

    intellij idea运行配置_idea2017配置jdkIntelliJidea2017.2配置Tomcat8.5前期准备IDEA、JDK、Tomcat什么的先装好,环境配置好,本文中没有这些配置博客图片为主请注意看仔细第一步当然先得建一个web项目1、file-&gt;new-&gt;project-Next-&gt;Finish-项目建好了接下来就是配置了-工具栏点击上图图标或【F4】或项目右键【OpenModuleS…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号