跳表及其实现
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