跳錶–怎麼讓一個有序鏈表能夠進行”二分”查找?
對於一個有序數組，如果要查找其中的一個數，我們可以使用二分查找(Binary Search)演算法，將它的時間複雜度降低為O(logn).那查找一個有序鏈表，有沒有辦法將其時間複雜度也降低為O(logn)呢？
跳錶(skip list),全稱為跳躍鏈表，實質上就是一種可以進行二分查找的有序鏈表，它允許快速查詢、插入和刪除有序鏈表。
跳錶使用的前提是鏈表有序，就像二分查找也要求有序數組
怎麼理解跳錶
要查找其中值為20的元素，之前都是採取按順序進行遍歷的方法，但這樣做時間複雜度就變成了O(n).怎樣才能提高效率呢？我們可以通過對鏈表建立一級索引，查找的時候先遍歷索引，通過索引找到原始層繼續遍歷。索引如下圖所示
那麼查找20的過程就變成了先使用索引遍歷 2 -> 7 -> 12 -> 20，然後順著索引鏈表的結點向下找到原始鏈表的結點20.之前需要遍歷7次，現在需要遍歷5次。在數據量小的時候跳錶性能優化並不明顯，但當有序鏈表包含大量數據時，結點的訪問次數大致會減少一半。
現在我們添加兩層索引，基於第一層的索引再添加一層，如下圖所示
要查找20，先在第二層索引上遍歷 2 -> 12 ,然後向下轉到第一層索引遍歷 12 – > 20，最後向下找到原始鏈表的結點20.
這個例子中，原始有序鏈表的結點數量很少，當結點數量很多時，可以抽出更多的索引層級，每一層索引結點的數量都是低層索引的一半。
跳錶複雜度分析
時間複雜度
演算法的執行效率可以通過時間複雜度來衡量，跳錶的時間複雜度是多少呢？我們來分析一下。
前面我們每兩個結點抽一個結點作為上一級索引的結點，那麼假設原始鏈表的長度為n，第一層索引的結點個數為n/2,第二層索引的個數為n/4,第k級的索引結點個數就是n/(2k)。假設索引有 h 級，最高級的索引有 2 個結點。通過上面的公式，我們可以得到 n/(2h)=2，從而求得 h=log2n-1。如果包含原始鏈表這一層，整個跳錶的高度就是 log2n。我們在跳錶中查詢某個數據的時候，如果每一層都要遍歷 m 個結點，那在跳錶中查詢一個數據的時間複雜度就是 O(m*logn)。
m的值怎麼計算呢？在上面的例子中，每一層最多只需要遍歷三個元素，因此m=3，根據
空間複雜度
每兩個結點中抽一個結點作為上級索引，很明顯，它的空間複雜度為O(n).
💁♂這是一個典型的空間換時間操作。原始鏈表中存儲的有可能是很大的對象，而索引結點只需要存儲關鍵值和幾個指針，並不需要存儲對象，所以當對象比索引結點大很多時，索引佔用的額外空間就可以忽略了。
高效的插入和刪除
插入操作
向鏈表插入數據的時間複雜度是O(1),但為了保持鏈表數據有序，需要先找到插入結點的前置結點，然後插入數據到前置結點後面，其時間複雜度為O(logn)。假設我們要插入10，需要先找到前置結點9，然後插入10。
刪除操作
刪除的話也是需要先找到要刪除的結點，如果該結點在索引中也有出現的話，索引中的也需要刪除。因為單鏈表中的刪除操作需要拿到要刪除結點的前驅結點，然後通過指針操作完成刪除。所以在查找要刪除的結點的時候，一定要獲取前驅結點。
動態更新索引
當我們一直往跳錶中插入數據時，兩個索引結點之間的數據可能會變得非常多，在極端情況下，跳錶還會退化成單鏈表，這樣的話跳錶的優勢也就沒有了。
因此我們需要用一些方法來維護索引和原始鏈表之間的平衡，也就是在增加原始鏈表中結點內容的時候適當增加索引的大小。為了維護平衡，跳錶的設計者採用了一種有趣的方法：「拋硬幣」，也就是隨機決定新結點是否建立索引，兩個結點建立一個索引的話，每層的概率為50%。
Java實現跳錶
下面是王爭老師
package skiplist;
/**
* 跳錶的一種實現方法。
* 跳錶中存儲的是正整數，並且存儲的是不重複的。
*
* Author：ZHENG
*/
public class SkipList {
private static final float SKIPLIST_P = 0.5f;
private static final int MAX_LEVEL = 16;
private int levelCount = 1;
private Node head = new Node(); // 帶頭鏈表
public Node find(int value) {
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];
}
}
if (p.forwards[0] != null && p.forwards[0].data == value) {
return p.forwards[0];
} else {
return null;
}
}
public void insert(int value) {
int level = randomLevel();
Node newNode = new Node();
newNode.data = value;
newNode.maxLevel = level;
Node update[] = new Node[level];
for (int i = 0; i < level; ++i) {
update[i] = head;
}
// record every level largest value which smaller than insert value in update[]
Node p = head;
for (int i = level - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
update[i] = p;// use update save node in search path
}
// in search path node next node become new node forwords(next)
for (int i = 0; i < level; ++i) {
newNode.forwards[i] = update[i].forwards[i];
update[i].forwards[i] = newNode;
}
// update node hight
if (levelCount < level) levelCount = level;
}
public void delete(int value) {
Node[] update = 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];
}
update[i] = p;
}
if (p.forwards[0] != null && p.forwards[0].data == value) {
for (int i = levelCount - 1; i >= 0; --i) {
if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {
update[i].forwards[i] = update[i].forwards[i].forwards[i];
}
}
}
while (levelCount>1&&head.forwards[levelCount]==null){
levelCount--;
}
}
// 理論來講，一級索引中元素個數應該占原始數據的 50%，二級索引中元素個數占 25%，三級索引12.5% ，一直到最頂層。
// 因為這裡每一層的晉陞概率是 50%。對於每一個新插入的節點，都需要調用 randomLevel 生成一個合理的層數。
// 該 randomLevel 方法會隨機生成 1~MAX_LEVEL 之間的數，且 ：
// 50%的概率返回 1
// 25%的概率返回 2
// 12.5%的概率返回 3 ...
private int randomLevel() {
int level = 1;
while (Math.random() < SKIPLIST_P && level < MAX_LEVEL)
level += 1;
return level;
}
public void printAll() {
Node p = head;
while (p.forwards[0] != null) {
System.out.print(p.forwards[0] + " ");
p = p.forwards[0];
}
System.out.println();
}
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();
}
}
}總結
