栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

数据结构学习:跳表

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

数据结构学习:跳表

跳表
    • 一、如何理解跳表
    • 二、跳表的动态更新
    • 三、代码实现
    • 四、跳表的优势

一、如何理解跳表

  • 跳表是由链表组成的,如上图,为一个单链表,每个节点存储本身和指向下一节点的指针
  • 即使单链表是有序的,在其中随机查找某个值的时候,还是需要遍历链表,时间复杂度为O(n)
  • 链表追加或给定节点插入或删除的时间复杂度为O(1),但如果在其中插入或删除某个节点,时间复杂度还是O(n)

如上图所示,这是一张跳表结构

  • 跳表是一张有序链表
  • 查找的时候,比如查找8,可以先找2-10,然后6-10,就可以不用遍历链表,层数设置的好的情况下,可以达到O(logn)的复杂度,类似于二分查找
  • 插入和删除也是,插入和删除的时候也可以通过类似于二分查找找到待插入的前置节点,时间复杂度也是O(logn)
二、跳表的动态更新
  • 假如跳表在增加的过程中,出现某两个层数中出现节点特别多的情况,这就会导致跳表退化为单链表,性能也会下降
  • 红黑树等平衡二叉查找树会利用左旋、右旋的方式来保持平衡;跳表也可以采用随机函数的方式生成层数,具体可看代码实现
三、代码实现
package LinkedList;



public class SkipList {
    private final static float SKIPLIST_P = 0.5f;
    private final static int MAX_LEVEL = 16; //最大层数

    private int level_count = 1;
    private Node head = new Node(); //带头链表

    static class Node{
        private int data = -1;
        private Node[] next = new Node[MAX_LEVEL];
        private int level = 0;

        @Override
        public String toString(){
            StringBuilder builder = new StringBuilder();
            builder.append("{data:");
            builder.append(data);
            builder.append(";level : ");
            builder.append(level);
            builder.append("};");
            return builder.toString();
        }
    }

    public Node find(int value){
        
        Node p = head;
        for (int i = level_count - 1; i >= 0; i++){
            while(p.next[i] != null && p.next[i].data < value){
                p = p.next[i];
            }
        }

        if (p.next[0] != null && p.next[0].data == value){
            return p.next[0];
        }else{
            return null;
        }
    }

    // 理论来讲,一级索引中元素个数应该占原始数据的 50%,二级索引中元素个数占 25%,三级索引12.5% ,一直到最顶层。
    // 因为这里每一层的晋升概率是 50%。对于每一个新插入的节点,都需要调用 randomLevel 生成一个合理的层数。
    // 该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数,且 :
    //        50%的概率返回 1
    //        25%的概率返回 2
    //      12.5%的概率返回 3 ...
    private int randomLevel(){
        int level = 1;

        while (Math.random() < SKIPLIST_P && level < MAX_LEVEL){
            level += 1;
        }
        return level;
    }

    public void printAll(){
        Node p = head;
        while (p.next[0] != null){
            System.out.print(p.next[0].data + " ");
            p = p.next[0];
        }
        System.out.println();
    }

    public void insert(int value){
        
        int level = randomLevel();
        Node newNode = new Node();
        newNode.data = value;
        newNode.level = level;

        Node[] prev = new Node[level]; //前置节点
        for (int i = 0; i < level;i++){
            prev[i] = head;
        }

        Node p = head;
        for (int i = level - 1;i >= 0;i--){
            while (p.next[i] != null && p.next[i].data < value){
                p = p.next[i];
            }
            prev[i] = p;
        }

        //prev[i]为每层待插入的前置节点,p为最底层待插入的前置节点
        for (int i = 0; i < level;i++){
            newNode.next[i] = prev[i].next[i];
            prev[i].next[i] = newNode;
        }

        if (level_count < level){
            level_count = level;
        }
    }

    public void delete(int value){
        
        Node p = head;
        Node[] prev = new Node[level_count];

        for (int i = level_count - 1; i >= 0; i--){
            while (p.next[i] != null && p.next[i].data < value){
                p = p.next[i];
            }
            prev[i] = p;
        }

        if (p.next[0] != null && p.next[0].data == value){
            for (int i = level_count - 1; i >= 0;i--){
                if (p.next[i] != null && p.next[i].data == value){
                    prev[i].next[i] = prev[i].next[i].next[i];
                }
            }
        }


        while (level_count > 1 && head.next[level_count] == null){
            level_count--;
        }
    }
}
四、跳表的优势
  1. 支持快速的插入、删除、查找操作,性能不逊色于红黑树
  2. 通过改变索引策略,有效平衡执行效率和内存消耗
  3. 更容易代码实现,相比红黑树,跳表还是更容易理解和实现的
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/969834.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号