首页 > 极客资料 博客日记
跳跃表
2024-09-07 16:00:05极客资料围观26次
这篇文章介绍了跳跃表,分享给大家做个参考,收藏极客之家收获更多编程知识
概述
跳跃表(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();
}
}
}
版权声明:本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:jacktools123@163.com进行投诉反馈,一经查实,立即删除!
标签:
相关文章
最新发布
- Nuxt.js 应用中的 prerender:routes 事件钩子详解
- 【问题解决】Tomcat由低于8版本升级到高版本使用Tomcat自带连接池报错无法找到表空间的问题
- 【FAQ】HarmonyOS SDK 闭源开放能力 —Vision Kit
- 六、Spring Boot集成Spring Security之前后分离认证流程最佳方案
- 《JVM第7课》堆区
- .NET 8 高性能跨平台图像处理库 ImageSharp
- 还在为慢速数据传输苦恼?Linux 零拷贝技术来帮你!
- 刚毕业,去做边缘业务,还有救吗?
- 如何避免 HttpClient 丢失请求头:通过 HttpRequestMessage 解决并优化
- 让性能提升56%的Vue3.5响应式重构之“版本计数”