当前位置:网站首页>写一下跳表
写一下跳表
2022-07-07 18:24:00 【kyhoon】
class Skiplist {
// 1.定义跳表中的节点
class Node{
// 值
int val;
// 节点的右节点和下节点
Node right, down;
public Node(int val, Node right, Node down){
this.val = val;
this.right = right;
this.down = down;
}
public Node(int val){
this(val, null, null);
}
}
//2. 定义跳表相关属性
// 定义头节点默认值
final int DEFAULT_VALUE = -1;
// 定义默认头结点
final Node HEAD = new Node(DEFAULT_VALUE);
// 跳表对应的层级
int levels;
// 跳表中原链表的节点数
int length;
Node head;
// 3.初始化,默认层级为1,长度为1,, 默认头结点
public Skiplist() {
this.levels = 1;
this.length = 1;
this.head = HEAD;
}
// 4. 定义获取从某个节点开始搜索目标值对应的节点的前一个节点(因为节点之间并没有指向前节点的属性,且操作跳表中的节点
// 都是需要从目标节点的前一个节点开始, 所以我们取目标节点的前节点)
private Node get(int num, Node from){
// 1.从哪个节点开始搜索
Node node = from;
// 2.循环的逻辑就是先从左向右,然后从上到下进行查找
while(node!=null){
// 2.1 如果当前节点的右节点不为空而且右节点的值还小于目标值,那么继续向右搜索
while(node.right!=null && node.right.val<num){
node = node.right;
}
// 2.2 当右节点不为空时跳出循环,那么只有可能是右节点的值大于或等于目标值了
// 如果是等于,那么就是找到了,直接返回目标节点的前节点
Node right = node.right;
if(right!=null && right.val == num){
return node;
}
// 2.3如果不是相等情况,则继续向下查找
node = node.down;
}
return null;
}
// 5.查询是否存在
public boolean search(int target) {
// 直接调用上面的查询方法,从表头开始查找,如果返回不为空,代表找到
Node node = get(target, head);
return node != null;
}
// 6.插入节点,大体思路是先找到原链表中插入节点要插入的位置然后进行插入,
// 接着通过抛硬币来决定是否建索引节点
public void add(int num) {
// 6.1 定义临时数组用于存放插入的节点在每一层需要插入的位置的前节点
Node[] nodes = new Node[this.levels];
// 6.2 定义临时数组的下标变量
int i = 0;
// 6.3 定义搜索的开始节点
Node node = head;
// 6.4 和get方法的原理一样
while(node!=null){
// 6.4.1 先从左向右
while(node.right!=null &&node.right.val < num){
node = node.right;
}
// 6.4.2 跳出循环, 无论如何(不管右节点空了,或者是右节点的值已经大于或等于目标值了),
// 此时当前层的这个节点就是插入节点的前节点,所以我们进行记录
nodes[i++] = node;
//6.4.3 继续向下查找
node = node.down;
}
// 6.5 循环完毕,此时临时数组的最后一个节点就是原链表中目标节点的前节点
Node pre = nodes[--i];
// 6.6 定义目标值的节点
Node newNode =new Node(num, pre.right, null);
// 6.7 插入
pre.right = newNode;
// 6.8 长度加一
this.length++;
// 6.9 抛硬币决定是否要建索引节点
coinsFlip(nodes, newNode, i);
}
// 抛硬币决定是否建索引节点的大致逻辑是:通过 0,1随机数及层级数是否小于基准值决定是否建索引
// 如果要建,那么首先得看下需要建索引的当前层是否是在原有层级内,
// 如果是,则进行插入,并继续抛硬币决定上一层是否要建
// 如果不是则,新建头结点,接入新索引节点来新建新的一层
private void coinsFlip(Node[] nodes, Node newNode, int i) {
// 1.定义0,1的随机数生成
Random random = new Random();
int coins = random.nextInt(2);
// 2.定义索引节点的下节点
Node downNode = newNode;
// 3.抛硬币决定是否建索引
while(coins == 1 && this.levels<(this.length>>6)) {
// 3.1 当抛的硬币是1且当前层级数小于基准值时,进行索引节点的创建
if (i > 0) {
//3.2 如果是当前需要插入索引节点在当前层级范围内,则拿到
// 插入索引节点的前节点
Node pre = nodes[--i];
// 定义新索引节点
Node newIndex = new Node(newNode.val, pre.right, downNode);
// 将前节点的右节点设置为新的索引节点
pre.right = newIndex;
// 将新索引节点设置为接下来上一层的要建的新索引节点的下节点
downNode = newIndex;
// 继续抛硬币
coins = random.nextInt(2);
} else {
// 如果已经超出当前层,则新建索引节点
Node newIndex = new Node(newNode.val, null, downNode);
// 新建头结点并将右节点设置为新的索引节点
Node newHead = new Node(DEFAULT_VALUE, newIndex, head);
// 将跳表的头节点指向新的头结点
this.head = newHead;
// 层级数加一
this.levels++;
}
}
}
// 7.删除节点,大体思路就是找到每一层目标节点要删除节点的前节点,并进行删除
public boolean erase(int num) {
// 7.1 定义结果变量,默认是false没找到可以删除的节点
boolean result = false;
// 7.2 从头结点查找下目标节点的前节点
Node node = get(num, head);
// 7.3 如果有,则进行删除,并进行下一层节点的删除
while(node != null){
// 7.3.1 获取删除节点
Node right = node.right;
// 7.3.2 将删除节点的前节点的右节点指向要删除的节点的右节点
node.right = right.right;
// 7.3.3 将删除节点的右节点指向空,触发gc
right.right = null;
// 7.3.4 将结果值赋值为true
result = true;
// 7.3.5 继续查下一层需要删除的目标节点的前节点
node = get(num, node.down);
}
// 7.4 如果删除成功了,则长度减一
if(result){
this.length--;
}
return result;
}
}
边栏推荐
- TS快速入门-泛型
- Chapter 9 Yunji datacanvas company won the highest honor of the "fifth digital finance innovation competition"!
- 【Auto.js】自动化脚本
- CodeSonar通过创新型静态分析增强软件可靠性
- OneSpin | 解决IC设计中的硬件木马和安全信任问题
- You want to kill a port process, but you can't find it in the service list. You can find this process and kill it through the command line to reduce restarting the computer and find the root cause of
- [philosophy and practice] the way of program design
- 整型int的拼接和拆分
- Oracle 存储过程之遍历
- 微服务远程Debug,Nocalhost + Rainbond微服务开发第二弹
猜你喜欢
The boundary of Bi: what is bi not suitable for? Master data, Martech? How to expand?
H3C S7000/S7500E/10500系列堆叠后BFD检测配置方法
数据孤岛是企业数字化转型遇到的第一道险关
[philosophy and practice] the way of program design
Network principle (1) - overview of basic principles
智能软件分析平台Embold
Airiot helps the urban pipe gallery project, and smart IOT guards the lifeline of the city
【哲思与实战】程序设计之道
Opencv学习笔记 高动态范围 (HDR) 成像
How to test CIS chip?
随机推荐
I Basic concepts
Splicing and splitting of integer ints
With st7008, the Bluetooth test is completely grasped
解决/bin/sh进去的容器运行可执行文件报not found的问题
CUDA versions are inconsistent, and errors are reported when compiling apex
MIT science and technology review article: AgI hype around Gato and other models may make people ignore the really important issues
机械臂速成小指南(十一):坐标系的标准命名
【mysql篇-基础篇】事务
ERROR: 1064 (42000): You have an error in your SQL syntax; check the manual that corresponds to your
Force buckle 1037 Effective boomerang
华为CE交换机下载文件FTP步骤
如何满足医疗设备对安全性和保密性的双重需求?
PHP method of obtaining image information
Cuda版本不一致,编译apex报错
The boundary of Bi: what is bi not suitable for? Master data, Martech? How to expand?
Chapter 20 using work queue manager (3)
School 1 of vulnhub
深度学习模型压缩与加速技术(七):混合方式
ASP. Net learning & ASP's one word
Update iteration summary of target detection based on deep learning (continuous update ing)