[ 文章收集 ] Skip List 的介绍以及查找插入删除等操作

參考自 這裡 
Preface: 
什麼是 Skip List？要說清楚這個問題，我們就要先從普通的 Linked List 說起. 考慮我們有一個 Sorted Linked List 如下: 
 

上面鍊表的元素依小到大排序 (ascending), 如果要插入一個元素, 範例代碼如下: 

view plaincopy to clipboardprint?

1. public boolean insert(int data)  
2. {  
3.     if(head==null)  
4.     {  
5.         head = new Node(data);            
6.     }  
7.     else  
8.     {  
9.         Node tmp = head;  
10.         if(tmp.data
11.         {  
12.             while(tmp.next!=null && tmp.next.data
13.             if(tmp.next!=null && tmp.next.data==data||tmp.data==data) return false;  
14.             else  
15.             {  
16.                 Node newNode = new Node(data);  
17.                 newNode.next = tmp.next;  
18.                 tmp.next = newNode;           
19.             }  
20.         }  
21.         else  
22.         {  
23.             Node newNode = new Node(data);  
24.             newNode.next = head;  
25.             head = newNode;  
26.         }  
27.     }     
28.     return true;  
29. }  

如果要查找一個元素的範例代碼: 

view plaincopy to clipboardprint?

1. public Node find(int data)  
2. {  
3.     if(head!=null)  
4.     {  
5.         Node tmp = head;  
6.         while(tmp!=null)  
7.         {  
8.             if(tmp.data==data) return tmp;  
9.             else if(tmp.data
10.             else break;  
11.         }  
12.     }  
13.     return null;  
14. }  

最後如果是要刪除一個元素: 

view plaincopy to clipboardprint?

1. public boolean delete(int data)  
2. {  
3.     if(head!=null)  
4.     {  
5.         Node tmp = head, prv = null;  
6.         while(tmp!=null)  
7.         {  
8.             if(tmp.data == data)  
9.             {  
10.                 if(prv==null) head = tmp.next;  
11.                 else  
12.                 {  
13.                     prv.next = tmp.next;  
14.                 }  
15.                 return true;  
16.             }  
17.             prv = tmp;  
18.             tmp = tmp.next;  
19.         }  
20.     }  
21.     return false;  
22. }  

不難發現這些操作的複雜度都是 O(n) , n 是鏈表中的元素數量. (完整代碼下載 LinkedList.java) 

Skip List 簡介: 
好，下面我們正式開始介紹 Skip List (跳表)。 Skip List 是個概率性數據結構，可以被看作是 BST(二元搜尋數) 的一個變種。跳表是由William Pugh在1990年發明的。它是一種用戶維護有序元素的數據結構. 跳表的構造過程是: 

1. 給定一個有序的鏈表。
2. 避開鏈表中最大和最小的元素，然後從其他元素中按照一定算法隨機選出一些元素，將這些元素組成有序鏈表形成新鏈表。這個新的鏈表稱為一層，原鏈表稱為其下一層。
3. 為剛選出的每個元素添加一個指針域，這個指針指向下一層中值同自己相等的元素。Top指針指向該層首元素
4. 重複2、3步，直到不再能選擇出除最大最小元素以外的元素

一個跳表，應該具有以下特徵: 

1. 一個跳表應該有幾個層（level）組成；
2. 跳表的第一層包含所有的元素；
3. 每一層都是一個有序的鍊錶；
4. 如果元素 x 出現在第 i 層，則所有比 i 小的層都包含x；
5. 第 i 層的元素通過一個 down 指針指向下一層擁有相同值的元素.
6. 因為跳表是隨機生成, 故即使元素相同的鏈表, 最終的生成的跳表有可能不一樣.

接著讓我們用一個跳表來重新構建文章開頭的有序鏈表 (底下是其中一種可能的跳表): 
 

上面的跳表中的 head 是一個陣列, 分別指向各個 Level 的鍊表中第一個元素, 而我們可以透過它在不同 Level 的鍊表中移動; 而相同元素在不同 Level 間也有一個類似的陣列以方便搜尋時在不同 Level 上下移動. 接著假設我們要搜尋數字 "117", 則會按照下面的規則進行搜尋: 

1. 由最上層開始搜尋 (該層需最少有一個元素)
2. 在當前層搜尋並停留在當層比搜尋值小但是最大的 pointer 上. (即該層所有比 "搜尋值" 小的值中最大的值)
3. 檢查下一個位置上是否為 "搜尋值":
3.1 如果是則搜尋成功.
3.2 如果不是, 則往下一層 (層數須大於等於 0). 如果下一層小於 0 則搜尋失敗.
4. 重複步驟 2, 3.

搜尋 "117" 過程如下: 
 

搜尋 "21" 過程如下: 
 

底下是搜尋過程的範例代碼: 

view plaincopy to clipboardprint?

1. public SNode find(E searchValue)  
2. {  
3.     int curLevel = level;  
4.     SNode x = header;        
5.     while(curLevel>=0 && x!=null)  
6.     {  
7.         while (x.forward[curLevel] != null &&   
8.                x.forward[curLevel].value.compareTo(searchValue) < 0)   
9.                 x = x.forward[curLevel];  
10.             System.out.printf("\t[Test] Hold in %s in level(%d)...\n", x.value!=null?x.value:"header", curLevel);  
11.             if(x.forward[curLevel]!=null &&   
12.                x.forward[curLevel].value.equals(searchValue)) return x.forward[curLevel];  
13.             else  
14.             {                     
15.                 if(curLevel>0) // 還有下一層, 往下一層移動. 此時 x 會停留當前層在小於 的最大 pointer 上.  
16.                 {                         
17.                     curLevel--; // 往下層移動  
18.                 }  
19.                 else return null;                 
20.             }  
21.           
22.     }         
23.     return null;  
24. }  

根據數學的推導, 這樣的時間複雜度會是 O(log n), n 是元素的數量. 底下是 Skip List (跳表) 的各項操作的時間複雜度: 
 

From Linked List to Skip List: 
現在問題來了, 假設我有一個 ascending order sorted 的 Linked List, 但我想把它轉成 Skip List (跳表) 的話, 該怎麼進行呢? 這個部分我分兩個部分來說明. 首先我們知道 Level 0 層需包含所有元素, 所以不假思索就硬幹了: 

view plaincopy to clipboardprint?

1. Random rdm = new Random(); // Random 物件稍後會用到  
2. Iterator iter = sortedList.iterator(); // 為來源 sorted ascending order Linked List  
3. SNode zeroLevel = header.forward[0]; // header 為每層的入口陣列, 使用 index 說明第幾層.         
4. HashMap> nodeMap = new HashMap>(); // 記載某個 Node 與其值的 mapping  
5. while(iter.hasNext())  
6. {  
7.     E data = iter.next();  
8.     SNode x = new SNode(MAX_LEVEL, (E)data); // 建立 Skip List 的 SNode.  
9.     nodeMap.put(data, x); // 紀錄 SNode mapping, 方便後續取出.  
10.       
11.     if(zeroLevel==null)  
12.     {  
13.         // 為 null 說明 為 Level 0 的第一個元素.  
14.         header.forward[0] = x;  
15.         zeroLevel = header.forward[0];  
16.     }  
17.     else {  
18.         // 串接 下一個元素為 後將 指向    
19.         zeroLevel.forward[0] = x;  
20.         zeroLevel = zeroLevel.forward[0];  
21.     }  
22.       
23. }  

因為會遍歷 Linked List 的所有元素, 故其時間複雜度為 O(n), 接著便是要處理上一層的部分了, 因為上一層是從 Level 1 起跳, 故我們下面代碼的 for loop 的變數 level 是從 1 開始; 另外在處理每一層的過程, 會從上一層隨機挑元素出來 (去頭去尾後) 當作此層的元素. 如此一直到再也沒有辦法從上一層取出元素為止. 範例代碼如下: 

view plaincopy to clipboardprint?

1. for(int level=1; level<=MAX_LEVEL; level++)  
2. {  
3.     SNode nextLevel = null;  
4.     SNode prevSN = header.forward[level-1]; // 去頭            
5.     if(prevSN==null||prevSN.forward[level-1]==null) continue;  
6.     do  
7.     {  
8.         E data = prevSN.value;  
9.         if(rdm.nextFloat()>P)  
10.         {  
11.             System.out.printf("\t[Test] Level%d: %d\n", level, data);  
12.             if(nextLevel == null)  
13.             {  
14.                 // 為 null 說明處理此層的第一個元素.  
15.                 header.forward[level] = nodeMap.get(data);                        
16.                 nextLevel = header.forward[level];  
17.             }  
18.             else  
19.             {  
20.                 nextLevel.forward[level] = nodeMap.get(data);                         
21.                 nextLevel = nextLevel.forward[level];  
22.             }  
23.         }  
24.         prevSN = prevSN.forward[level-1];  
25.         if(prevSN==null) break;  
26.     }while(prevSN.forward[level-1]!=null); // 去尾  
27.     // 設定目前最高層的 level 為當前處理的 level.  
28.     if(nextLevel!=null) // nextLevel 不為 null 說明當前層至少有一個元素.  
29.     {  
30.         this.level = level;  
31.         nextLevel = null;  
32.     }  
33. }  

上面的過程, 在走訪下一層的每一個元素時(去頭去尾:P), 我們設定一個常數變數 P=0.5, 當使用 Random 物件隨機產生一個浮點數 (0.0<=x<=1.0) 大於 P 時, 我們便將該元素加到當前這一層. 另外我們也設定另一個常數變數 MAX_LEVEL 來限定最高的層數, 通常該值會是 Linked List 的元素數量取 log (類似 Complete Binary Tree 的 Height). 而這邊的外層 for loop 會執行 log(n) 次, 而內部的 while loop 會執行最多 n 次 (走訪上一層元素), 故我們的時間複雜度會是 O(n log n)! 

至於 Skip List 的其他操作如 delete, insert 等, 有興趣的可以去下載 SkipList.java. 裡面有完整的實作代碼. 而該範例代碼是改寫自 這裡 的 SkipSet.java