首页 > 编程语言 >跳表及其Java实现

跳表及其Java实现

时间:2023-08-08 17:12:41浏览次数:43  
标签:right Java SkipNode 及其 跳表 key null pointer 节点

跳表及其实现

参考https://zhuanlan.zhihu.com/p/339750543

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

/**
 * 参考https://zhuanlan.zhihu.com/p/339750543
 */
public class SkipListPractice {
    static class SkipNode<T>{
        SkipNode<T> right;
        SkipNode<T> down;
        int key;
        T value;
        public SkipNode(int _key,T _value){
            key = _key;
            value = _value;
        }
    }

    /**
     * 跳表其实是作为红黑树和AVL树的同类型的数据结构,
     * 跳表(Skip List)是一种数据结构,通常用于存储有序的键值对集合。
     * 在大多数实现中,跳表的键(key)是唯一的,这意味着键值不会重复。
     * @param <T>
     */
     static class SkipList<T>{
        SkipNode<T> head;
        int currentHighestLevel;//高度
        Random random;
        final int MAX_LEVEL = 32;
        public SkipList(){
            head = new SkipNode<T>(-1, null);
            random = new Random();
            currentHighestLevel = 0;
        }
        public void put(int key,T value){
            SkipNode<T> searchResult = search(key);
            if (Objects.nonNull(searchResult)){
                //说明已经有这个key了,那么就不要再处理了
                return;
            }
            Stack<SkipNode<T>> stack = new Stack<>();
            //用来存向下遍历时经过的节点,因为添加节点是从下往上进行的
            //在n层添加完新节点后,如何马上在n+1层快速找到添加新节点的位置?
            //答:那就是通过栈,栈非空则表示还需要进行添加新节点的操作
            SkipNode<T> pointer = head;
            while(pointer != null){
                if (pointer.right == null || pointer.right.key > key){
                    stack.add(pointer);//该往下层走了,就需要入栈了
                    pointer = pointer.down;
                }else{
                    pointer = pointer.right;
                }
            }
            int level = 1;
            SkipNode<T> downNode = null;//用于记录新节点创立后,新节点的down节点
            while (!stack.isEmpty()){
                //在该层插入node
                pointer = stack.pop();//pointer是新节点的前驱节点
                SkipNode<T> tempNode = new SkipNode<>(key, value);//新节点
                tempNode.down = downNode;//给新节点的down字段赋值
                downNode = tempNode;//如果还有新节点,那么新节点的down节点就是本节点
                //进行新加节点操作
                tempNode.right = pointer.right;
                pointer.right = tempNode;//因为pointer是前驱节点,所以直接赋值即可插入新节点
                if (level > MAX_LEVEL){//如果当前的level已经大于跳表允许的最大level,则跳出循环
                    break;
                }
                double num = random.nextDouble();//概率计算,是否往上再加一层
                if (num > 0.5){
                    //大于0.5才再继续往上新建一层
                    break;
                }
                level++;
                if (level > currentHighestLevel){
                    //大于当前的高度了,只有这种情况,才需要重新初始化新的头节点了
                    currentHighestLevel = level;
                    SkipNode<T> highHeadNode = new SkipNode<T>(-1, null);//头节点的key不重要,随机即可,
                    highHeadNode.down = head;
                    head = highHeadNode;
                    stack.add(highHeadNode);
                    //因为我要给新的头节点的右侧添加新节点,这个过程是否会再次往上呢?
                    //这个我们不清楚,索性就加到栈里面,再走一次这样的流程即可。
                }
            }
        }
        public SkipNode<T> search(int key){
            SkipNode<T> pointer = this.head;
            boolean ifFirst = true;//用于标记是否是第一次访问到head
            while(pointer != null){
                if (pointer.key == key && !ifFirst){
                    return pointer;
                }else if(pointer.right == null || pointer.right.key > key){
                    pointer = pointer.down;
                }else{
                    pointer = pointer.right;
                }
                ifFirst = false;
            }
            return null;
        }

        public void delete(int key){
            SkipNode<T> pointer = head;
            while(pointer != null){
                if (pointer.right == null || pointer.right.key > key){
                    pointer = pointer.down;
                }else if (pointer.right.key == key){
                    //说明找到了,进行删除节点操作并且继续向下;
                    //这里不暂存这个节点的原因是,我们需要找到前序的节点才能进行删除,
                    //所以删除完毕之后直接在本pointer向下继续查找;
                    pointer.right = pointer.right.right;
                    pointer = pointer.down;
                }else{
                    pointer = pointer.right;
                }
            }
        }

        public void printList(){
            SkipNode<T> pointer = head;
            int index = 1;
            SkipNode<T> lowestNode = head;
            while(lowestNode.down != null){
                lowestNode = lowestNode.down;
            }
            while(pointer != null){
                SkipNode<T> enumNode = pointer.right;
                SkipNode<T> enumLast = lowestNode.right;
                System.out.printf("%-8s",index+"head->");
                //因为打印是从上往下打印的,为了方便与最底层对应
                //如果上层的key和最底层的key一致,那么就打印出来
                //如果不一致,那就空出位置来对应,不打印;不用担心
                //上层元素不会打印全部,因为底层元素是上层元素的超集
                while(enumLast != null && enumNode != null){
                    if (enumLast.key == enumNode.key){
                        System.out.printf("%-5s",enumLast.key+"->");
                        enumNode = enumNode.right;
                        enumLast = enumLast.right;
                    }else{
                        enumLast = enumLast.right;
                        System.out.printf("%-5s","");
                    }
                }
                pointer = pointer.down;
                index++;
                System.out.println();
            }
        }
    }



    public static void main(String[] args) {
        SkipList<Integer> skipList = new SkipList<>();
        for (int i = 0;i < 30;i++){
            skipList.put(i,324);
        }
        skipList.printList();
        System.out.println("删除后:");
        skipList.delete(5);
        skipList.delete(0);
        skipList.delete(10);
        skipList.printList();
    }
}

标签:right,Java,SkipNode,及其,跳表,key,null,pointer,节点
From: https://www.cnblogs.com/csq-66/p/17614855.html

相关文章

  • Sqoop 连接mysql 错误 java.lang.NoClassDefFoundError(已解决)
    错误信息Exceptioninthread"main"java.lang.NoClassDefFoundError:org/apache/commons/lang/StringUtilsatorg.apache.sqoop.manager.MySQLManager.initOptionDefaults(MySQLManager.java:73)atorg.apache.sqoop.manager.SqlManager.<init......
  • java heap space解决方法
    在JVM中如果98%的时间是用于GC(Garbage Collection)且可用的Heapsize不足2%的时候将抛出异常信息,java.lang.OutOfMemoryError:Javaheapspace。所以产生这个异样的原因通常有两种:1.程序中出现了死循环2.程序占用内存太多,超过了JVM堆设置的最大值。对于第一种情况,需要自己查看......
  • asterisk-java的测试使用
    asterisk-java的测试使用一个可用于FreePBX的封装库asterisk-java用于asteriskPBX集成的免费Java库。https://github.com/asterisk-java/asterisk-java最新版本为3.39.0<dependency><groupId>org.asteriskjava</groupId><artifactId>asterisk-java</artifactId><......
  • Java入门题-查找一个字符串中,所有想查找短字符串的起始位置
    问题:就是长短两串字符串,从长字符串中查找所有短字符串在长字符串中的位置方法:用截取方式来规避已经查找过的内容,重复遍历来确定位置代码:需要引用importjava.util.Scanner; Scanners=newScanner(System.in);//新定义一个ScannerStringS=s.next();......
  • JAVA 问题记录
     OOM(内存溢出) 先查看java进程pidjps使用jmp把内存导出查看那些对象内存占用比较高jmp-histo<pid>>/histo.txt在可以看堆内存使用情况jmp-heap<pid>>/heap.txt ......
  • 安装好了Java、Neo4j社区版3.5.5,和二者的环境变量后,如何浏览器登录Neo4j
    前提:安装好了Java、Neo4j社区版3.5.5,和二者的环境变量后。Win+R->cmd进入输入neo4j.batconsole回车正常情况下是这样: 不正常情况下是这样:解决办法:输入下图的两句但是记住:neo4jstart一次就要neo4jstop一次,不然会给如下报错:记得neo4jstop就行了 最后......
  • H7-TOOL的高速DAPLINK用于新版STM32CubeIDE V1.13及其以上版本的超简单实现方法(2023-0
    之前分享了一个方法,太繁琐了,H7-TOOL群的群友提供了一个方法,实现非常简单。1、使用STM32CubeMX或者自己创建一个STM32CubeIDE工程后,设置这两个地方即可: 配置调试器,设置完毕记得点击右下角的Apply2、然后修改这个cfg文件,F407IGTDebug.cfg,注意和第1步cfg是一个文件。修改......
  • Java 11 新特性
    Java11新特性Java11是Java8之后的第一个长期支持版本(longtermsuppoertLTS),Oracle将在2019年1月停止支持Java8.OracleVSOpenJDKJava10是最后一个免许可商用版本,如果不需要Oracle商业支持的话,可以选择OpenJDK直接运行java文件Java11之前需要先用......
  • 基于Java开发的智慧EHR人力系统(源码获取)
    一、项目介绍一款全源码可二开,可基于云部署、私有部署的企业级数字化人力资源管理系统,涵盖了招聘、人事、考勤、绩效、社保、酬薪六大模块,解决了从人事招聘到酬薪计算的全周期人力资源管理,符合当下大中小型企业组织架构管理运作模式,助力企业人力资源管控信息化、智能化、规范化,......
  • Java开发需要掌握哪些技术?
    Java开发需要掌握哪些技术? 想要找到一份不错的Java开发工作,首先需要掌握一定的Java技术。那么想成为一名合格的Java开发工程师都有哪些技术是必须掌握的呢?零基础开始学习Java开发主要需要学习四个方面的内容,分别为:JavaEE基础、JavaWeb开发、Java高级框架、大型微服务分布式项目......