跳表基于單鏈表實作，鏈表查找、插入、洗掉絕大部分時間花在遍歷鏈表上，跳表使用索引來優化鏈表遍歷的程序，使得跳表具有非常優秀的查找、插入、洗掉性能，并且是天然的動態資料結構
-
查找、插入、洗掉時間復雜度都是O(logn)
-
跳表原理的理解
-
二叉搜索通過計算mid的值，使得每一次要遍歷的資料量減半，那么鏈表可不可以實作類似的功能呢
-
如果有一個指標指向鏈表中點，那么在搜索時先與中點比較，根據比較結果決定是從鏈表頭開始遍歷還是從中點開始遍歷，這樣平均每次要遍歷的資料量就減少了一半
-
如果多設定幾個索引，甚至設定多級索引，那么遍歷鏈表所花費的時間將大大降低，而額外付出的空間不過是幾個指標
-
跳表示意圖
-
原鏈表查找4，需要1->2->3->4，而加了索引之后1->3->4；查找5更是只需1->5；在鏈表很大時跳表的查找效率會顯著提高，
-
-
跳表實作上的注意點
-
與紅黑樹相位元表的實作難度要簡單不少，但還是有幾處注意點
-
節點設定
-
資料(data)：存盤該節點資料
-
索引陣列(forward[])：存盤該節點各層的索引（每個索引也是一個節點），索引指是指向下一節點的指標
-
查找結點（值設為value）
-
-
實際上跳表實作的核心就是結點的查找
-
查找時從頭節點、最上層索引開始
-
1.找到該層索引中data小于value的最大節點（這個節點后面的節點值要么等于value要么大于value）
-
2.若本層已經是第0層索引（也就是到了原鏈表）則此時的節點就是值小于等于value的最后一個節點，這個節點后面一個就是我們要找的值
-
3.若本層不是第0層索引，則去下一層，重復1-2-3程序
-
-
跳表的隨機函式
-
資料不斷的插入程序中，如果索引一直沒有更新，考慮極端情況：所有資料都在兩個索引之間，跳表退化為了鏈表
-
使用隨機函式解決上述退化問題：在插入值新值時，不僅將新節點插入原鏈表，并且插入n層對應的索引
-
n是一個隨機值，理論上要使得一級索引的數目為鏈表長度的n/2，二級索引的數目為n/4……
-
-
跳表Java實作（insert優化）
/**
* 跳表是在單鏈表的基礎上加入索引，使查找效率大大提高的一種各方面性能都很優秀的資料結構
* 跳表存盤正整數，且不重復
* @author hzk
*/
public class mySkipList {
private final int MAX_LEVEL = 16;//最大索引層數（0~原鏈表 15~最高一級索引）
private int levelCount = 1;//跳表當前索引層數
public Node head = new Node();//跳表頭
/**
* 查找跳表中值為value的節點
*
* @param value 要查找的值
* @return 找到回傳對應節點，否則回傳null
*/
public Node find(int value) {
Node p = head;
//找到該層索引中小于value的最大節點
for (int i = levelCount - 1; i >= 0; i--) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
}
if (p.forwards[0] != null && p.forwards[0].data == value)
return p.forwards[0];
else
return null;
}
/**
* 將value插入跳表中
*
* @param value 待加入資料
*/
public void insert(int value) {
int level = randomLevel();
if (levelCount < level) levelCount = level;
Node p = head;
Node newNode = new Node();
newNode.data = value;
newNode.maxLevel = level;
Node path[] = new Node[level];//存盤查找value時經過各層的索引
for (int i = level - 1; i >= 0; i--) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
path[i] = p;
}
//將value插入各層索引中
for (int i = level - 1; i >= 0; i--) {
newNode.forwards[i] = path[i].forwards[i];
path[i].forwards[i] = newNode;
}
}
/**
* insert的優化版本，去掉了path[]
* @param value 待加入資料
*/
public void insert_optimized(int value) {
int level = randomLevel();
if (levelCount < level) levelCount = level;
Node p = head;
Node newNode = new Node();
newNode.data = value;
newNode.maxLevel = level;
for (int i = level - 1; i >= 0; i--) {
while (p.forwards[i] != null && p.forwards[i].data < value)
p = p.forwards[i];
//這層索引是最后一個則直接插入
if (p.forwards[i] == null) {
p.forwards[i] = newNode;
}
//否則插在中間
else {
newNode.forwards[i] = p.forwards[i];
p.forwards[i] = newNode;
}
}
}
/**
* 洗掉跳表中值為value的節點及索引
*
* @param value 待洗掉結點的值
*/
public void delete(int value) {
Node path[] = new Node[levelCount];
Node p = head;
for (int i = levelCount - 1; i >= 0; i--) {
while (p.forwards[i] != null && p.forwards[i].data < value)
p = p.forwards[i];
path[i] = p;
}
//找到
if (p.forwards[0] != null && p.forwards[0].data == value) {
//洗掉節點所有索引
for (int i = levelCount - 1; i >= 0; i--) {
if (p.forwards[i] != null && p.forwards[i].data == value) {
p.forwards[i] = p.forwards[i].forwards[i];
}
}
}
}
/**
* 隨機生成索引層數，索引層數和生成概率負相關
* 盡量使一級索引占全部索引的50%，二級索引占25%，三級索引占12.5%……
* 隨機函式能防止鏈表資料全部集中在某兩個索引之間
*
* @return
*/
private int randomLevel() {
int level = 1;
while (Math.random() < 0.5 && level < MAX_LEVEL)
level++;
return level;
}
public void printAll() {
Node p = head;
while (p.forwards[0] != null) {
System.out.print(p.forwards[0].data + " ");
p = p.forwards[0];
}
System.out.println();
}
public void skipListText() {
mySkipList list = new mySkipList();
list.insert(1);
list.insert(2);
list.insert(3);
list.printAll();
System.out.println(list.find(2));
list.delete(2);
list.printAll();
list.insert_optimized(2);
list.printAll();
}
public class Node {
private int data = -1;//節點資料
private Node forwards[] = new Node[MAX_LEVEL];//存盤節點上層索引
private int maxLevel = 0;//最大索引層數
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("{ data: ");
builder.append(data);
builder.append("; levels: ");
builder.append(maxLevel);
builder.append(" }");
return builder.toString();
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/27709.html
標籤：其他
上一篇：0367. Valid Perfect Square (E)
下一篇：空間直線與球面相交演算法