前言
本文主要介紹跳表的特點，以及如何自己實作一個跳表，
跳表（SkipList）
跳表是一個典型的空間換時間模型，底層資料結構是一個有序的單鏈表，通過構建多層索引，實作了二分查找方式來查詢資料，多層索引不僅提高了查詢效率，同時也使得插入和洗掉的時間復雜度為O（logn），此外，多層索引的空間復雜度為O（n），
跳表是一個隨機化的動態資料結構，它引入了多層索引，所以在運行期間需要維護索引和原始資料的平衡性，不像紅黑樹、AVL樹通過左右旋的方式保持左右子樹的平衡，跳表通過隨機函式來隨機需要構建的索引層數，從而維護平衡性，
跳表在性能上和紅黑樹、AVL樹不相上下，但是跳表的實作比較簡單，目前在Redis、LevelDB上都有使用，
以上介紹了跳表的特點，下面貼上具體代碼實作：
package main.java.skiplist;
import java.util.Random;
/**
* 傳統跳表
* 1. 元素不能重復
* 2. 索引層數隨機
*/
public class SkipList {
// 隨機工具，用于隨機索引層數
private final Random random;
public final int MAX_LEVEL = 16;
// 當前層數
public int level;
public SkipNode head;
public SkipList() {
random = new Random();
head = new SkipNode(Integer.MIN_VALUE, MAX_LEVEL);
level = 1;
}
/**
* 回傳隨機建造索引層數
* @return [1, MAX_LEVEL]
*/
private int randomLevel() {
int n = 1;
for (int i = 1; i < MAX_LEVEL; i++) {
if (random.nextInt(2) == 1)
n++;
}
return n;
}
/**
* 根據 val 查詢結點
* @param val 結點值
* @return 如果值不存在，回傳 null；否則回傳查詢的結點
*/
public SkipNode find(int val) {
SkipNode p = head;
for (int i=level-1; i>=0; i--) {
while (p.next[i] != null && p.next[i].value < val) {
p = p.next[i];
}
}
return p.next[0] != null && p.next[0].value =https://www.cnblogs.com/flowers-bloom/archive/2021/09/13/= val ? p.next[0] : null;
}
/**
* 根據 val 洗掉節點
* @param val 結點值
* @return 如果值不存在，回傳 null；否則回傳洗掉的結點
*/
public SkipNode delete(int val) {
SkipNode[] prev = new SkipNode[MAX_LEVEL];
SkipNode p = head;
for (int i=level-1; i>=0; i--) {
while (p.next[i] != null && p.next[i].value < val) {
p = p.next[i];
}
prev[i] = p;
}
if (p.next[0] != null && p.next[0].value == val) {
SkipNode res = p.next[0];
for (int i = 0; i < res.level; i++) {
prev[i].next[i] = prev[i].next[i].next[i];
}
return res;
}
return null;
}
/**
* 插入節點
* @param val 結點值
*/
public void insert(int val) {
int newLevel = randomLevel();
SkipNode newNode = new SkipNode(val, newLevel);
SkipNode[] prev = new SkipNode[newLevel];
SkipNode p = head;
for (int i=newLevel-1; i>=0; i--) {
while (p.next[i] != null && p.next[i].value < val) {
p = p.next[i];
}
prev[i] = p;
}
for (int i=0; i level)
level = newLevel;
}
public void show() {
StringBuffer sb = new StringBuffer();
int col = 0;
SkipNode p = head.next[0];
while (p != null) {
p.setSpan(col);
col++;
p = p.next[0];
}
SkipNode[] arr = head.next;
for (int i=level-1; i>=0; i--) {
sb.append(String.format("第%2d層: ", i));
p = arr[i];
for (int j = 0; j < col; j++) {
if (p != null && p.span == j) {
sb.append(p.value);
p = p.next[i];
}else {
sb.append(" ");
}
if (j != col-1)
sb.append(" -> ");
}
sb.append("\n");
}
System.out.println(sb.toString());
}
public static final class SkipNode {
int level;
int value;
int span; // 輔助列印
SkipNode[] next;
public SkipNode(int v, int level) {
value = https://www.cnblogs.com/flowers-bloom/archive/2021/09/13/v;
this.level = level;
next = new SkipNode[level];
}
@Override
public String toString() {
return"SkipNode{" +
"level=" + level +
", value="https://www.cnblogs.com/flowers-bloom/archive/2021/09/13/+ value +", span=" + span +
'}';
}
public void setSpan(int span) {
this.span = span;
}
}
}
效果截圖
原始資料：
查詢和洗掉：
參考
- [1] 【資料結構與演算法】之跳表
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/299800.html
標籤：其他