博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
跳跃表
阅读量:6480 次
发布时间:2019-06-23

本文共 356 字,大约阅读时间需要 1 分钟。

hot3.png

       跳跃表插入节点的流程有以下几步:

1.     新节点和各层索引节点逐一比较,确定原链表的插入位置。O(logN)

2.     把索引插入到原链表.O(1)

3.     利用抛硬币的随机方法,决定新节点是否提升为上一级索引。结果为正则提升并继续抛硬币,结果为负则停止.O(logN)

总体上,跳跃表插入操作的时间复杂度为O(logN),而这种数据结构所占用空间市2N,既空间复杂度是O(N)

 

      跳跃表中删除节点的步骤:

1.     自上而下,查找第一个出现节点的索引,并逐层找到每一层对应的节点logN

2.     删除每一层查找到的节点,如果该层只剩下一个节点,删除整个一层,原链表除外O(logN)

跳跃表删除操作的时间复杂度是O(logN)

转载于:https://my.oschina.net/iioschina/blog/1305354

你可能感兴趣的文章
Sqoop架构(四)
查看>>
golang copy函数
查看>>
《你有多少问题要请示》精华集粹
查看>>
打印图片
查看>>
SHOW CREATE DATABASE Syntax
查看>>
rsync常见问题及解决办法
查看>>
MySQL日期 专题
查看>>
C#中禁止程序多开
查看>>
分布式缓存Redis使用以及原理
查看>>
Activity竟然有两个onCreate方法,可别用错了
查看>>
Linux经常使用命令(十六) - whereis
查看>>
Linux五种IO模型
查看>>
Bootstrap技术: 模式对话框的使用
查看>>
小知识,用myeclipes找jar
查看>>
in-list expansion
查看>>
设计原则(四):接口隔离原则
查看>>
基于react的滑动图片验证码组件
查看>>
java单例模式深度解析
查看>>
【学习笔记】阿里云Centos7.4下配置Nginx
查看>>
VuePress手把手一小時快速踩坑
查看>>