数据结构学习——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)


相关推荐

发表回复

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

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