IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 跳表的原理与实现 [图解] -> 正文阅读

[数据结构与算法]跳表的原理与实现 [图解]

下文介绍一种基于单链表的高级数据结构, 跳表 。?

单链表先进行排序,然后针对 有序链表?为了实现高效的查找,可以使用跳表这种数据结构。

其根本思想是 二分查找 的思想。

跳表的前提条件是?针对?有序的单链表 ,实现高效地查找,插入,删除。

Redis中的 有序集合 sorted set?就是用跳表实现的。

一. 跳表的原理

对于单链表,即使是 存储的有序数据(即 有序链表),想在其中查找某个数据,也只能从头到尾遍历,查找效率低,时间复杂度是O(n),如下图所示:

怎么才能提高查找效率呢??

为了提高查找效率,使用二分查找的思想,对有序链表建立一级“索引”。 每两个节点提取一个节点到索引层。?索引层中的每个节点 都包含两个指针,一个指向下一个节点,一个down指针,指向下一级节点。

假设要查找图中 18这个节点:

首先在一级索引层遍历,当遍历到14这个节点的时候,发现其下一个节点是23,则要查找的18就在14和23之间。?然后,通过14节点的?down 指针,下降到原始链表这一层,继续在原始链表中遍历。?此时,只需要在原始链表中,遍历两个节点,14和18,就找到18这个节点了。? ? 查找18这个节点,在原始链表需要遍历10个节点现在只需要遍历7个节点(一级索引层遍历5个节点,原始链表遍历2个节点)。?

从以上示例可以看出,加上一层索引之后,查找一个节点的遍历节点数减少了,效率提高了。如果再增加一级索引,那么效率会不会更高呢?

建立二级索引

与建立一级索引的方式类似,在第一级索引的基础上,每两个节点抽出一个节点到第二级索引,如下图:

?现在如果要查找18节点,只需要遍历6个节点(二级索引层遍历3个节点,一级索引层1个节点,原始链表2个节点)。

通过建立索引的方式,对于数据量越大的有序链表,通过建立多级索引,查找效率提升会非常明显。

这种链表加多级索引的结构?就是?跳表

二.跳表的?时间复杂度?和 空间复杂度

2.1 跳表的查询时间复杂度

假设链表包含n个节点,在单链表中查询某个数据的时间复杂度是O(n)。

一个包含n个节点的有序单链表最多会有多少级索引?

每两个节点抽出一个节点作为上一级索引的节点,则 :

第一级索引的节点个数大约是?n/2 ,第二级索引的节点个数大约是 n/4,第三级索引的节点个数大约是?n/8,则第k级索引节点的个数大约是

假设有 h?级索引,最高一级的索引有两个节点,也就是? ,从而求得?如果把原始链表这一层也算进去,那么整个跳表的高度约为?

在跳表查询时,每一级索引 最多需要遍历3个节点。?

因为假设在上图跳表中,从二级索引层,查找?节点12,则从节点1遍历到节点7,然后再遍历节点14(节点12 小于?节点14) ,从节点7向下一级索引层遍历到节点7,然再向右遍历节点11,再遍历节点14,发现节点12小于节点14,?则继续向下一级遍历,最终在下一级遍历到节点12。?

在上面遍历节点12的过程,在二级索引层遍历了3个节点(1—>7---->14),在一级索引层遍历了3个节点(7—>11---->14)。因此每一级最多遍历3个节点。

那么在跳表中查询数据的时间复杂度就是? ? ?每一层遍历的节点数乘以层数??,因此跳表中查找的时间复杂度就是O(logn).? 与二分查找的时间复杂度相同。

基于单链表实现了二分查找,查询效率的提升依赖构建了多级索引,是一种空间换时间的设计思路。

2.2 空间复杂度

建立索引后 的 总的索引点 的 空间复杂度:

????????

跳表的查询数据的空间复杂度是O(n),也就是说,基于单链表构造跳表,需要额外再用一倍的存储空间。

有没有办法降低索引占用的存储空间呢?

如果每3个节点 或 每5个节点抽1个节点到上一级索引,索引节点就会相应减少。假设每3个节点抽取一个节点到上一级,总的索引节点个数为:

? ? ? ?

每3个节点抽1个节点到上一级索引的方法? 比 每2个节点抽1个节点构建索引的方式,减少了一半的索引节点存储空间。

因此,通过调节抽取节点的间隔,控制索引节点占用的存储空间,以此来达到空间复杂度 和 时间复杂度的平衡。

三.?跳表的插入和删除

跳表作为一个动态数据结构,不仅支持查找操作,还支持数据的插入和删除操作,并且?插入和删除的操作的时间复杂度都是O(logn).

3.1? 插入操作

为了保证原始链表中数据的有序性,我们需要先找到新数据应该插入的位置。 可以基于多级索引,快速查找到新数据的插入位置,时间复杂度为O(log n)。

假设插入数据为6的节点,如下图:

3.2? 删除操作

删除原链表中的节点,如果节点存在于索引中,也要删除索引中的节点。 因为单链表中的删除需要用到 要删除节点前驱动节点。 可以像插入操作一样,通过索引逐层向下遍历到原始链表中,要删除的节点,并记录其 前驱节点,从而实现删除操作。

四. 跳表索引动态更新

当频繁地向跳表中插入数据时,如果插入过程不伴随着索引更新,就有可能导致某2个索引节点之间数据非常多,在极端地情况下,跳表就会退化成单链表。

作为一种动态数据结构,为了避免性能下降,我们需要在数据插入,删除的过程中,动态地更新跳表的索引结构。? 就像红黑树,二叉平衡树是通过左右旋来保持左右子树的大小平衡, 而跳表是借助随机函数来更新索引结构。

当向跳表中插入数据时,我们选择同时将这个数据插入到部分索引层中。 如何决定插入到哪些索引层中呢? 通过一个随机函数来决定,比如通过? 随机函数得到某个值 K, 那么就将这个节点添加到第一级到第K级索引中

五.总结

为什么Redis中的有序集合用跳表而非红黑树来实现呢?

1.对于插入,删除,查找 以及 输出有序序列 这几个操作,红黑树也可以完成,时间复杂度 与 用跳表实现是相同的。 但是,对于按照区间查找数据这个操作(比如 [20,300]),红黑树的效率没有跳表高,跳表可以做到 O(logn)的时间复杂度定位区间的起点,然后在原始链表中顺序向后遍历输出,直到遇到值大于区间终点的节点为止。

2.跳表更加灵活,它可以通过改变节点的抽取间隔,灵活地平衡空间复杂度和时间复杂度

3.相比红黑树,跳表更容易实现,代码更简单。

六. 代码实现

1.C++版本(参考 Leetcode1206题 题解)

struct Node
{
     //向右向下指针
    Node* right;
    Node* down;  
    int val;
    Node(Node *right, Node *down, int val)
            : right(right), down(down), val(val){}
};

class Skiplist {
private:
    Node *head;
    // 预先分配后,提升性能
    const static int MAX_LEVEL = 32;
    // 查找时临时使用的变量
    vector<Node*> pathList;
public:
    Skiplist() {
        //初始化头结点
        head = new Node(NULL, NULL, -1);
        pathList.reserve(MAX_LEVEL);
    }
    
    bool search(int target)
    {
        Node *p = head;
        while(p)
        {
            // 左右寻找目标区间
            while(p->right && p->right->val < target)
            {
                p = p->right;
            }
            // 没找到目标值,则继续往下走
            if(!p->right || target < p->right->val)
            {
                p = p->down;
            }
            else
            {   
                //找到目标值,结束
                return true;
            }
        }
        return false;
    }
    
    void add(int num) {
         //从上至下记录搜索路径
        pathList.clear();
        Node *p = head;
        // 从上到下去搜索 次小于num的 数字,等于就是另外一种实现里的 prevs
        while(p)
        {
            // 向右找到次小于num的p
            while (p->right && p->right->val < num)
            { 
                p = p->right;
            }
            pathList.push_back(p);
            p = p->down;
        }

        bool  insertUp = true;
        Node* downNode = NULL;
        // 从下至上搜索路径回溯,50%概率
        // 这里实现是会保证不会超过当前的层数的,然后靠头结点去额外加层, 即每次新增一层
        while (insertUp && pathList.size() > 0)
        {
            Node *insert = pathList.back();
            pathList.pop_back();
            // add新结点
            insert->right = new Node(insert->right,downNode,num); 
            // 把新结点赋值为downNode
            downNode = insert->right; 
            // 50%概率   
            insertUp = (rand()&1)==0;
            
        }
        // 插入新的头结点,加层
        if(insertUp)
        {  
            
            head = new Node(new Node(NULL,downNode,num), head, -1);
        }
    }
    
    bool erase(int num) {
        Node *p = head;
        bool seen = false;
        while (p)
        {
            // 当前层向右找到次小的点
            while (p->right && p->right->val < num)
            {
                p = p->right;
            }
            // 无效点,或者 太大, 则到下一层去
            if (!p->right || p->right->val > num)
            {  
                p = p->down;
            }
            else
            {
                // 搜索到目标结点,进行删除操作,结果记录为true
                // 继续往下层搜索,删除一组目标结点
                seen = true;
                p->right = p->right->right;
                p = p->down;
            }
        }
        return seen;
    }
};

2.Java版本(参考 Leetcode1206题 题解)

class Skiplist {
        /**
         * 最大层数
         */
        private static int DEFAULT_MAX_LEVEL = 32;
        /**
         * 随机层数概率,也就是随机出的层数,在 第1层以上(不包括第一层)的概率,层数不超过maxLevel,层数的起始号为1
         */
        private static double DEFAULT_P_FACTOR = 0.25;

        Node head = new Node(null,DEFAULT_MAX_LEVEL); //头节点

        int currentLevel = 1; //表示当前nodes的实际层数,它从1开始


        public Skiplist() {
        }

        public boolean search(int target) {
            Node searchNode = head;
            for (int i = currentLevel-1; i >=0; i--) {
                searchNode = findClosest(searchNode, i, target);
                if (searchNode.next[i]!=null && searchNode.next[i].value == target){
                    return true;
                }
            }
            return false;
        }

        /**
         *
         * @param num
         */
        public void add(int num) {
            int level = randomLevel();
            Node updateNode = head;
            Node newNode = new Node(num,level);
            // 计算出当前num 索引的实际层数,从该层开始添加索引
            for (int i = currentLevel-1; i>=0; i--) {
                //找到本层最近离num最近的list
                updateNode = findClosest(updateNode,i,num);
                if (i<level){
                    if (updateNode.next[i]==null){
                        updateNode.next[i] = newNode;
                    }else{
                        Node temp = updateNode.next[i];
                        updateNode.next[i] = newNode;
                        newNode.next[i] = temp;
                    }
                }
            }
            if (level > currentLevel){ //如果随机出来的层数比当前的层数还大,那么超过currentLevel的head 直接指向newNode
                for (int i = currentLevel; i < level; i++) {
                    head.next[i] = newNode;
                }
                currentLevel = level;
            }

        }

        public boolean erase(int num) {
            boolean flag = false;
            Node searchNode = head;
            for (int i = currentLevel-1; i >=0; i--) {
                searchNode = findClosest(searchNode, i, num);
                if (searchNode.next[i]!=null && searchNode.next[i].value == num){
                    //找到该层中该节点
                    searchNode.next[i] = searchNode.next[i].next[i];
                    flag = true;
                    continue;
                }
            }
            return flag;
        }

        /**
         * 找到level层 value 大于node 的节点
         */
        private Node findClosest(Node node,int levelIndex,int value){
            while ((node.next[levelIndex])!=null && value >node.next[levelIndex].value){
                node = node.next[levelIndex];
            }
            return node;
        }


        /**
         * 随机一个层数
         */
        private static int randomLevel(){
            int level = 1;
            while (Math.random()<DEFAULT_P_FACTOR && level<DEFAULT_MAX_LEVEL){
                level ++ ;
            }
            return level;
        }


        class Node{
            Integer value;
            Node[] next;

            public Node(Integer value,int size) {
                this.value = value;
                this.next = new Node[size];
            }

            
            public String toString() {
                return String.valueOf(value);
            }
        }

    }

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-09-02 11:37:50  更:2021-09-02 11:38:13 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 0:29:04-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码