首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

跳跃表

编程知识
2024年09月07日 14:31

概述

跳跃表(SkipList)是链表加多级索引组成的数据结构。链表的数据结构的查询复条度是 O(N)。为了提高查询效率,可以在链表上加多级索引来实现快速查询。跳跃表不仅能提高搜索性能。也能提高插入和删除操作的性能。索引的层数也叫作跳跃表的高度


查找

在跳跃表的结构中会首先从顶层开始查找,当顶层不存在时向下一层查找,重复此查找过程直到跳跃到原始链表。如图所示,在 [1,3,4,10,1,20] 的链表中查找 10,首先从二级索引中查找,由于 1 和 4 都比 10 小,因此接着在一级索引查找,由于 10 大于 4 小于 11,因此接着向下查找,原始链表中 4 的下一个节点 10 便是需要查找的数据


插入

首先按照查找流程找到待插入元素的前驱和后继,然后按照随机算法生成一个高度值 height,最后将待插入的节点按照高度值生成一个垂直节点(这个节点的层数正好等于高度值),并将其插人跳跃表的多条链表中。如果高度值 heigh 大于插入前跳跃表的高度,那么跳跃表的高度被提升为 height,同时需要更新头节点和尾节点的指针指向。如果 height 小于或等于跳跃表的高度,那么需要更新待插入元素的前驱和后继的指针指向。在 [1,3,4.10,11,20] 的跳跃表中插入 18 的过程如图所示


删除

在删除节点时首先需要找到待删除的节点在每一层的前驱和后继,接着将其前驱节点的后继替换为待删除的节点的后继,删除 4 的过程如图所示


代码实现

import java.util.Random;
import java.util.Stack;

class SkipNode<T> {

    int key;
    T value;
    SkipNode right,down;//左右上下四个方向的指针
    public SkipNode (int key,T value) {
        this.key=key;
        this.value=value;
    }

}

public class SkipList <T> {

    SkipNode headNode;//头节点,入口
    int highLevel;//层数
    Random random;// 用于投掷硬币
    final int MAX_LEVEL = 32;//最大的层
    
    SkipList(){
        random=new Random();
        headNode=new SkipNode(Integer.MIN_VALUE,null);
        highLevel=0;
    }
    
    public SkipNode search(int key) {
        SkipNode team=headNode;
        while (team!=null) {
            if(team.key==key){
                return  team;
            }
            else if(team.right==null) { //右侧没有了,只能下降
                team=team.down;
            }
            else if(team.right.key>key) { //需要下降去寻找
                team=team.down;
            }
            else { //右侧比较小向右
                team=team.right;
            }
        }
        return null;
    }

    public void delete(int key) { //删除不需要考虑层数
        SkipNode team=headNode;
        while (team!=null) {
            if (team.right == null) { //右侧没有了,说明这一层找到,没有只能下降
                team=team.down;
            }
            else if(team.right.key==key) { //找到节点,右侧即为待删除节点
                team.right=team.right.right;//删除右侧节点
                team=team.down;//向下继续查找删除
            }
            else if(team.right.key>key) { //右侧已经不可能了,向下
                team=team.down;
            }
            else { //节点还在右侧
                team=team.right;
            }
        }
    }
    
    public void add(SkipNode node) {
    
        int key=node.key;
        SkipNode findNode=search(key);
        if(findNode!=null) { //如果存在这个key的节点
        
            findNode.value=node.value;
            return;
        }

        Stack<SkipNode>stack=new Stack<SkipNode>();//存储向下的节点,这些节点可能在右侧插入节点
        SkipNode team=headNode;//查找待插入的节点   找到最底层的哪个节点。
        while (team!=null) {//进行查找操作
            if(team.right==null) { //右侧没有了,只能下降
                stack.add(team);//将曾经向下的节点记录一下
                team=team.down;
            }
            else if(team.right.key>key) { //需要下降去寻找
                stack.add(team);//将曾经向下的节点记录一下
                team=team.down;
            }
            else { //向右
                team=team.right;
            }
        }

        int level=1;//当前层数,从第一层添加(第一层必须添加,先添加再判断)
        SkipNode downNode=null;//保持前驱节点(即down的指向,初始为null)
        while (!stack.isEmpty()) {
            //在该层插入node
            team=stack.pop();//抛出待插入的左侧节点
            SkipNode nodeTeam=new SkipNode(node.key, node.value);//节点需要重新创建
            nodeTeam.down=downNode;//处理竖方向
            downNode=nodeTeam;//标记新的节点下次使用
            if(team.right==null) {//右侧为null 说明插入在末尾
                team.right=nodeTeam;
            }
            //水平方向处理
            else {//右侧还有节点,插入在两者之间
                nodeTeam.right=team.right;
                team.right=nodeTeam;
            }
            //考虑是否需要向上
            if(level>MAX_LEVEL)//已经到达最高级的节点啦
                break;
            double num=random.nextDouble();//[0-1]随机数
            if(num>0.5)//运气不好结束
                break;
            level++;
            if(level>highLevel) { //比当前最大高度要高但是依然在允许范围内 需要改变head节点
                highLevel=level;
                //需要创建一个新的节点
                SkipNode highHeadNode=new SkipNode(Integer.MIN_VALUE, null);
                highHeadNode.down=headNode;
                headNode=highHeadNode;//改变head
                stack.add(headNode);//下次抛出head
            }
        }
    }
    
    public void printList() {
        SkipNode teamNode=headNode;
        int index=1;
        SkipNode last=teamNode;
        while (last.down!=null){
            last=last.down;
        }
        while (teamNode!=null) {
            SkipNode enumNode=teamNode.right;
            SkipNode enumLast=last.right;
            System.out.printf("%-8s","head->");
            while (enumLast!=null&&enumNode!=null) {
                if(enumLast.key==enumNode.key) {
                    System.out.printf("%-5s",enumLast.key+"->");
                    enumLast=enumLast.right;
                    enumNode=enumNode.right;
                }
                else {
                    enumLast=enumLast.right;
                    System.out.printf("%-5s","");
                }
            }
            teamNode=teamNode.down;
            index++;
            System.out.println();
        }
    }
}
From:https://www.cnblogs.com/Yee-Q/p/18401654
本文地址: http://www.shuzixingkong.net/article/1810
0评论
提交 加载更多评论
其他文章 设计模式之模板方法模式(三分钟学会一个设计模式)
模板方法模式(Template Method Pattern)也称之为模板模式(Template Pattern),是设计模式中最简单的模式之一。 先来看定义:定义一个操作中算法的骨架(模板),将一些步骤延迟到子类中,模板方法使得子类可以不改变算法的结构即可重新定义算法某些特定的步骤。这个定义还是有
设计模式之模板方法模式(三分钟学会一个设计模式) 设计模式之模板方法模式(三分钟学会一个设计模式)
事务发件箱模式在 .NET 云原生开发中的应用(基于Aspire)
原文:Transactional Outbox in .NET Cloud Native Development via Aspire 作者:Oleksii Nikiforov 总览 这篇文章提供了使用 Aspire、DotNetCore.CAP、Azure Service Bus、Azure SQ
事务发件箱模式在 .NET 云原生开发中的应用(基于Aspire) 事务发件箱模式在 .NET 云原生开发中的应用(基于Aspire) 事务发件箱模式在 .NET 云原生开发中的应用(基于Aspire)
HashMap深入讲解
HashMap是Java中最常用的集合类框架,也是Java语言中非常典型的数据结构, 而HashSet和HashMap者在Java里有着相同的实现,前者仅仅是对后者做了一层包装,也就是说HashSet里面有一个HashMap(适配器模式)。因此了解HashMap源码也就了解HashSet了 介绍 K
HashMap深入讲解
真人模特失业?AI虚拟试衣一键成图,IDM-VTON下载介绍
在电商行业竞争尤为激烈的当下,除了打价格战外,如何有效的控制成本,是每个从业者都在思考的问题 IDM-VTON是一个AI虚拟换装工具,旨在帮助服装商家解决约拍模特导致的高昂成本问题,只需一张服装图片,就可以生成各种身穿该服装的模特,大大简化了传统的产品展示过程 IDM-VTON最新中文版: 百度网盘
真人模特失业?AI虚拟试衣一键成图,IDM-VTON下载介绍 真人模特失业?AI虚拟试衣一键成图,IDM-VTON下载介绍 真人模特失业?AI虚拟试衣一键成图,IDM-VTON下载介绍
Java是值传递还是引用传递,又是怎么体现的
关于Java是值传递还是引用传递,可以从代码层面来实现一下拿到结果 执行下面的代码: public static void main(String[] args) { int num = 10; String name = &quot;Tom&quot;; modify(num, name); Sy
五子棋AI:实现逻辑与相关背景探讨(下)
前文回顾 在上篇文章中,我们约定了一种衡量格子价值的方式,如下表。 综合价值排序 己方价值 敌方价值 对应的奖励数值 1 Lv1 ? \(2^{20}\) 2 ? Lv1 \(2^{16}\) 3 Lv2 ? \(2^{12}\) 4 ? Lv2 \(2^{8}\) 5 Lv3 ? \(2^{4}\
使用 `Roslyn` 分析器和修复器对.cs源代码添加头部注释
之前写过两篇关于Roslyn源生成器生成源代码的用例,今天使用Roslyn的代码修复器CodeFixProvider实现一个cs文件头部注释的功能, 代码修复器会同时涉及到CodeFixProvider和DiagnosticAnalyzer, 实现FileHeaderAnalyzer 首先我们知道修
使用 `Roslyn` 分析器和修复器对.cs源代码添加头部注释 使用 `Roslyn` 分析器和修复器对.cs源代码添加头部注释 使用 `Roslyn` 分析器和修复器对.cs源代码添加头部注释
线性dp:LeetCode516 .最长回文子序列
LeetCode516 .最长回文子序列 题目叙述: 力扣题目链接(opens new window) 给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。 子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。 示例 1: 输入:s = &quot
线性dp:LeetCode516 .最长回文子序列 线性dp:LeetCode516 .最长回文子序列 线性dp:LeetCode516 .最长回文子序列