跳跃链表

数据结构之跳跃链表

简介

总的来说跳跃链表最大的好处就是提高了检索了的速率,可以说说是大幅度的提高,相对于单链表来说是一种高效率的检索结构

原理

跳跃表的结构是:假如底层有10个节点, 那么底层的上一层理论上就有5个节点,再上一层理论上就有2个或3个节点,再上一层理论上就有1个节点。所以从这里可以看出每一层的节点个数为其下一层的1/2个元素,以此类推。从这里我们可以看到,从插入时我们只要保证上一层的元素个数为下一层元素个数的1/2,我们的跳跃表就能成为理想的跳跃表。那么怎么才能保证我们插入时上层元素个数是下层元素个数的1/2呢,?很简单 抛硬币就可以解决了,假设元素X要插入跳跃表,最底层是肯定要插入X的,那么次低层要不要插入呢,我们希望上层元素个数是下层的1/2,那么我们有1/2的概率要插入到次低层,这样就来抛硬币吧,正面就插入,反面就不插入,次次底层相对于次低层,我们还是有1/2的概率插入,那么就继续抛硬币吧 , 以此类推元,素X插入第n层的概率是(1/2)的n次。这样,我们能在跳跃表中插入一个元素了。基本的样子如下图:

代码实现(java语言)

节点定义

123456789101112131415

package skip;public class Node{ public Integer value; //插入的数据 public Node left; //分别对应的四个方向的指针 public Node down; public Node right; public Node up; public Node(Integer value) //构造函数 { this.value=value; down=up=right=left=null; }}

表的实现

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199

package skip;import java.util.Random;public class SkipList { private Node head; //最上面一侧的头结点,这里使用的是双链表 private Node tail; //最上面一层的尾节点,这里的头尾节点是不存储数据的,数据域全是null private int level; //表中的最高的层数,就是总共的层数 private int size; //插入节点的个数,头尾节点除外 private Random random; //用来判断是否需要增加高度的随机函数 public SkipList() { level = 0; //level默认是0层,就是只有最下面的一层 head = new Node(null); tail = new Node(null); head.right = tail; //这里初始化成一个只有一层的双链表 tail.left = head; size = 0; //size初始化为0 random = new Random(); } //这个函数的作用是找到插入节点的前面一个节点,这里默认的是将表升序存储 public Node findFirst(Integer value) { Node p = head; while (true) { //判断要插入的位置,当没有查到尾节点并且要插入的数据还是比前面的大的话,就将节点右移,知道找到合适的位置 //这里需要注意的是这里的head代表不一定是最底层的,因此这里的查找都是从最高层进行查找的,如果满足条件就要向下移动 //直到最底层 while (p.right.value != null && p.right.value <= value) { p = p.right; } //向下移动,直到到达最后一层 if (p.down != null) { p = p.down; } else { //到达最底层跳出即可 break; } } return p; //此时这里的p就是要插入节点的前面一个节点 } //这是插入函数,这里先执行插入,然后判断是否需要增加高度 public void insert(int value) { Node curr = findFirst(value); //先找到插入位置的前面一个节点 Node q = new Node(value); //新建一个插入的节点 //下面执行插入步骤,这个和双链表是一样的步骤 q.right = curr.right; q.left = curr; curr.right.left = q; curr.right = q; int i = 0; //表示当前节点所在的层数,开始插入的是在下面插入的,所以开始的时候是在0层 //这里判断是否需要增加高度,每一层相对域下面来说都有二分之一的概率,也就是说每一层增加的概率是(1/2)^n //通俗的说就是每一层的节点是将会保证是下面一层的1/2 while (random.nextDouble() < 0.5) { if (i >= level) { //如果当前插入的节点所处的层数大于等于最大的层数,那么就需要增加高度了,因为这里要保证头尾节点的高度是最高的 //下面的代码就是在头尾节点的上插入新的节点,以此来增加高度 Node p1 = new Node(null); Node p2 = new Node(null); p1.right = p2; p1.down = head; p2.left = p1; p2.down = tail; head.up = p1; //将头尾节点上移,成为最顶层的节点,这就是为什么每次插入和查询的时候都是最上面开始查询的,因为这里的head默认的就是从最上面开始的 tail.up = p2; head = p1; tail = p2; level++; //最高层数加一 } while (curr.up == null) { //当然增加高度就是在插入节点上面新插入一个节点,然后将之与插入的节点相连 //既然这里新插入节点增高了,那么就需要找到与新插入节点上面的那个节点相连接,这里我们将新插入节点的前面的同等高度的节点与之相连 curr = curr.left; } curr = curr.up; //通过前面的一个节点找到与之相连的节点 //下面就是创建一个节点插入到插入节点的头上以此来增加高度,并且这个节点与前面一样高的节点相连 Node e = new Node(value); e.left = curr; e.right = curr.right; curr.right.left = e; //此时的curr就是与之同等高度的节点 curr.right = e; e.down = q; q.up = e; q = e; //将新插入的节点上移到最上面,因为后面可能还要在这里增加高度,就是在最上面插入新的一模一样的节点 i++; //增加当前所处的高度,这里一定能要记得写上,如果还要继续增加的话,需要判读是否需要增加头尾节的高度 } size++; //节点加一 } //下面是打印每一层节点的情况 public void display() { while (level >= 0) { Node p = head; while (p != null) { System.out.print(p.value + "-------->"); p = p.right; } System.out.println(); System.out.println("*****************************"); level--; head = head.down; } } /*在链表中查找某个值是否存在,如果存在找到的节点,当然先从最高层开始查找,如果找到了在比这个值小的最后一个值,那么就顺着这个值的下面开始寻找,按照上面的步骤 再次寻找,如过这个值正好等于要找的值,就返回true,形象的来说就是形成一个梯度的感觉。注意这里返回的节点一定是最底层的节点,利于下面的删除操作 * */ public Node search(int value) { Node p = head; while (true) { /*这里一定要写成p.right.value!=null,如果写成p.right!=null运行可能有错误, 因为这里的尾节点的值为null,但是它的节点不是空的,如果成这样的话,那么节点可能会找到尾节点都没有找到,此时在判断value的值就出现错误 相当与判断tail.right.value<=value,这个肯定是不行的,因为这个节点不存在,是空的更别说值了 */ //从最高层开始判断找到比这个小的最后一个值,就是找到一个节点的前面比value小的,后面的节点的值比value大的 while (p.right.value != null && p.right.value <= value) { p = p.right; //如果没有找到就后移直到找到这个节点 } //如果找到的这个节点不是最底层的话,就向下移动一层,然后循环再次寻找,总之就是从最高层开始,一层一层的寻找 if (p.down != null) { //这个表示上面的循环没有找到的相等的,那么就向下移动一层 p = p.down; } else { //如果到了最底层了,这里的值仍然没有找到这个值,那么就表示不存在这个值 if (p.value == value) { //判断是否存在value相等的值// System.out.println(p.value + "----->"); return p; //返回节点 } return null; //仍然没有找到返回null } } } /* 这里是利用上面的查找函数,找到当前需要删除的节点,当然这个节点是最底层的节点,然后循环从最底层开始删除所有的节点 * */ public void delete(int value) { Node temp = search(value); //这里返回的必须是最底层的节点,因为要从最下面的往上面全部删除所有层的节点,否则的话可能在某一层上仍然存在这个节点 while (temp != null) { temp.left.right = temp.right; temp.right.left = temp.left; temp = temp.up; //节点上移,继续删除上一层的节点 } } public static void main(String args[]) { SkipList skipList = new SkipList(); Random random = new Random(); skipList.insert(33); skipList.insert(44); skipList.insert(11); skipList.insert(10); skipList.insert(22); skipList.insert(22); for (int i = 0; i < 500; i++) { int value = (int) (random.nextDouble() * 1000); skipList.insert(value);// System.out.println(value); } Node p = skipList.search(22); if (p != null) { System.out.println(p.value); } else System.out.println("没有找到"); skipList.delete(33); skipList.display(); }}

源码地址

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员互动联盟

【编程基础】C语言循环语句解析

循环语句是一种很重要的结构,这种结构的特点就是在某种条件下,会重复循环执行某一段代码,直到条件不成立为止。这里的条件称为循环条件,重复执行的那段代码称为循环体。...

3745
来自专栏小樱的经验随笔

Codeforces Round #410 (Div. 2)(A,字符串,水坑,B,暴力枚举,C,思维题,D,区间贪心)

A. Mike and palindrome time limit per test:2 seconds memory limit per test:256 m...

4844
来自专栏和蔼的张星的图像处理专栏

156. 合并区间先排序再处理

给出若干闭合区间,合并所有重叠的部分。 样例 给出的区间列表 => 合并后的区间列表:

1773
来自专栏chenjx85的技术专栏

leetcode-166-分数到小数(用余数判断有没有出现小数的循环体)

给定两个整数,分别表示分数的分子 numerator 和分母 denominator,以字符串形式返回小数。

6165
来自专栏magicsoar

Effective Modern C++翻译(2)-条款1:明白模板类型推导

第一章 类型推导 C++98有一套单一的类型推导的规则:用来推导函数模板,C++11轻微的修改了这些规则并且增加了两个,一个用于auto,一个用于decltyp...

19010
来自专栏程序员互动联盟

八大排序算法

排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说...

3908
来自专栏小文博客

蓝桥杯C语言知识点补充——快速排序详解

2182
来自专栏顶级程序员

各大排序算法性能比较及演示实例

所谓排序,即将原来无序的一个序列重新排列成有序的序列。 排序方法中涉及到稳定性,所谓稳定性,是指待排序的序列中有两个或两个以上相同的项,在排序前和排序后看这些相...

36110
来自专栏Java帮帮-微信公众号-技术文章全总结

八大排序算法详解_面试+提升

八大排序算法详解_面试+提升 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排...

3959
来自专栏算法修养

PAT 1012 数字分类 (20)

给定一系列正整数,请按要求对数字进行分类,并输出以下5个数字: A1 = 能被5整除的数字中所有偶数的和; A2 = 将被5除后余1的数字按给出顺序进行交错...

2665

扫码关注云+社区

领取腾讯云代金券