<font size = 2>

Skip Lists 跳表
===
* [name=資管一 葉又銘 學號：B10705052]

動機 Motivation
---
首先，我們要討論Skip Lists這個資料結構的由來、產生動機，就必須先談到較基本的資料結構 Linked Lists 與 Array。
### 一、鍊表 Let's talk about Linked List
1. Linked Lists 是一個動態資料結構Dynamic Data Structure，可以有效率的進行update$^{註1}$操作，複雜度為$O(1)$，是他的優點。
2. 然而，在處理一個有序的資料中，他不能有效率的訪問元素，複雜度為$O(n)$，這是他的缺點。

### 二、陣列 Let's talk about Array
1. Array 在處理一個有序的資料中，他能使用二元搜尋法Binary Search$^{註2}$快速的訪問元素，複雜度為$O(logn)$，這是他的優點。
2. 然而，他並不能有效率的進行update，複雜度為$O(n)$，這是他的缺點。

| | Update | Find |
| -------- | -------- | -------- |
| Linked Lists | $O(1)$ ***勝*** | $O(n)$ |
| Array | $O(n)$ | $O(logn)$ ***勝*** |

> **是否能找到一個兼具兩者優勢的資料結構呢？**

##### 註解
1. update: 意指進行插入insert、刪除delete這類型操作
2. Binary Search: 是一種在有序陣列中搜尋某一特定元素的搜尋演算法，複雜度為$O(logn)$

<p style="page-break-after:auto"></p>

簡介 Introduction
---
Skip Lists可以完美的兼具兩者優勢，我們接下來開始介紹Skip Lists。
### 一、特點 Features of Skip Lists
1. Skip Lists如同Linked List，是一個動態資料結構Dynamic Data Structure，可以有效率的進行update操作，複雜度為$O(1)$。
2. 如同Array。，使用Binary Search訪問元素，複雜度為$O(logn)$。
3. 是處理有序資料的資料結構。
4. 建構方式隨機，為Randomized Data Structure。

>### 範例：
>
>##### 圖一 ⌃
>###### 註：每一層都是一個List，Sentinel是每一層List的頭
>###### 說明：利用Linked List為原型建構，每一層可視為一個List，透過機率的方式決定結構。

### 二、如何訪問目標？
搜尋時，由最上層開始搜尋，透過比較目標值與右方的數值大小，決定方向，若小於或走到盡頭則往下，大於則往右，最終找到目標。

>### 範例：
>
>###### 說明：首先，$13 > 8 > 2$，先走向節點8，因後方無節點，所以往下走一格，$13 < 15$，所以往下走一格，接著往後走兩格即可找到節點13。可以發現，Skip Lists取名由來正是因為這個資料結構讓使用者搜尋時，可以跳過一些元素。

<p style="page-break-after:auto"></p>

建構 Contruction
---
### 一、討論如何將Sorted Linked List轉換成Skip List。
1. 增長List節點，每個節點將隨機增長
2. 透過改變機率或限制高度，可改變結構長相、高度。
3. 在這個範例中，我們將機率設為1/2，高度為3層。

請參考圖三～六。
>討論是否增長2，我們可以想像成躑一硬幣，若為正面，則增長。
>
>##### 圖三 ⌃
>###### 說明：這是一個尚未增長節點的List，即將討論節點2是否增長。
>若為正面，增長節點2，接著討論節點5。
>
>##### 圖四 ⌃
>###### 說明：即將討論節點5是否增長。
>若為反面，不增長，又若節點7正面，增長，則節點2跳過節點5，指向節點7。
>
>##### 圖五 ⌃
>###### 說明：節點5被跳過，直接指向節點7。
>使用相同方法，我們可以將所有節點增長完。
>
>##### 圖六 ⌃
>###### 說明：完整結構。

<p style="page-break-after:auto"></p>

### 二、資料結構大小 How large is a Skip List?
令增長機率為 $r$，List長度為 $n$。
在長期情況下，第 $l$ 層約有 $n\times r^{-l}$ 個元素，總共有$log_{r^{-1}}n$層（圖六）：
<!-- $$
\sum_{l=0}^{log_{r^{-1}}n-1}n\times r^{l}=n\sum_{l=0}^{log_{r^{-1}}n-1}r^{l}\to n\times \frac{(r^{log_{r^{-1}}n}-1)}{(r^{}-1)}
$$ -->

所以，以此為例，the size of the skip list

<!-- $$= {n\times \frac{(\frac1 2)^{log_{2}n}-1}{(\frac1 2)-1}}|_{n=8}\approx 14
$$ -->

</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>

>
>##### 圖六 ⌃

### 三、Perfect Skip Lists
如果每一層List本身都包含他下一層的1/2個元素，我們稱它為Perfect Skip Lists，也可以說，我們決定他的增長機率為1/2，如同躑一枚硬幣，以正反面決定是否讓節點增長。

>
>##### 圖七 ⌃

### 四、類別成員 What’s the members of this class?
1. 指標``*head``指向節點物件 Sentinel，而 Sentinel 儲存節點指標``*forward[]``，``forward[i]``指向第 $i$ 層List，而每個節點都會儲存一個節點指標``*forward[i]``，來決定下一步。
2. Level儲存當前的層數。

>
>##### 圖八 ⌃
>###### 說明：可以看到Sentinel儲存節點指標``*forward[]``，可以決定下一步，而節點7也儲存指標``*forward[]``，指向下一步節點8。

### 五、程式碼範例 Code

struct SNode
{
    int val;
    SNode **forward; //指向各層List
    SNode(int level, int &value)
    {
        forward = new SNode * [level + 1];//給予共level層
        memset(forward, NULL, sizeof(SNode*) * (level + 1));//初始化，將每一層先指向NULL
        this->val = value;
    }
};

class SkipList
{
    friend SNode;
private:
    SNode *head;//pointer to the sentinel
    int value; //for init
    int level; //current level of the Skip List
public:
    SkipList()
    {
        head = new SNode(MAX_LEVEL, value);//產生一個SNode，讓head指向他
        level = 0;//當前層數為0
    }
    SkipList(std::list<int>& list)//將linked list轉換成skip list
    {
        head = new SNode(MAX_LEVEL, value);
        level = 0;
        while(!list.empty())
        {
            Insert(list.front());//直接插入值，此方法為O(nlogn)
            list.pop_front();
            //如果是sorted linked list，直接讓linked list作為基底增長
            //可以直接產生Skip list，可以限制在O(n)，此法將在書面報告呈現
        }
    }
    void Show();
    bool Find(int &);
    void Insert(int &);
    void Delete(int &);
};




查找 Find
---

### 一、複雜度問題 Complexity
1. 我們透過比較目標數值來決定向右走或向下走，我們可以把他看做是一個特別的Binary Search Tree（圖十）。

>### 範例：
>![](https://i.imgur.com/yTv1SLu.png =90%x)
>##### 圖九 ⌃
>###### 回顧先前展示過的查找範例，從最上層開始，比較目標值與右方值，若目標較大則往右走，否則往下走，很像是BST的查找模式。
>![](https://i.imgur.com/qUtI9Ld.png =90%x)
>##### 圖十 ⌃
>###### 在每一層做比較時，都可以拆分成兩個部分再繼續做比較，總共會做 $log_2n$ 次（層數）比較，然後找到目標，可以說複雜度為 $O(logn)$。
    
2. 第二個方法是從後方檢查，在最底層L$_0$時，因爲上方層已經將最下方層拆分，我們可以說每一層向左走的次數應為常數，所以每一層向左走的複雜度為 $O(1)$，而向上走的複雜度與層數相同，複雜度為$O(logn)$（圖十一）。

>### 範例：
>![](https://i.imgur.com/ZtiJDUF.png =90%x)
>##### 圖十一 ⌃
>###### 這個範例中，每層最多往左走回 $2$ 次，往上走剛好是 $logn$ 次，合併來看複雜度 $O(logn)$。
    
    
### 二、程式碼範例 Code

bool SkipList::Find(int &target)
{
SNode *curr = head;
for (int i = level;i >= 0;i--)//i-- 指往下一層走
{
while (curr->forward[i] != NULL && curr->forward[i]->val < target)
{
curr = curr->forward[i];//往右走
}
}
curr = curr->forward[0];//走到盡頭或找到目標位置
return curr != NULL && curr->val == target;
}

插入 Insert
---

### 一、複雜度問題 Complexity
1. 從查找的操作來說，我們知道想找到特定位置的複雜度為 $O(logn)$ ，而因為Skip Lists 是一個Dynamic Data Structure，進行任一update操作的複雜度為 $O(1)$，Skip List的插入操作複雜度為 $O(logn)$（圖十二）。

    
>### 範例：
>![](https://i.imgur.com/yukd1bS.png =90%x)
>##### 圖十二 ⌃
>###### 說明：先找到插入位置 $O(logn)$，再進行串接 $O(1)$，然後討論是否增長（取決於增長機率）。

    
### 二、程式碼範例 Code

void SkipList::Insert(int &value)
{
SNode *curr = head;
SNode *entryBefore[MAX_LEVEL + 1];//儲存要插入的前一個entry
memset(entryBefore, NULL, sizeof(SNode*) * (MAX_LEVEL + 1));//先將其初始化指向NULL
for (int i = level;i >= 0;i--)
{
while (curr->forward[i] != NULL && curr->forward[i]->val < value)
{
curr = curr->forward[i];
}
entryBefore[i] = curr;
}
//如果插入的是新的entry
if (curr->forward[0] == NULL || curr->forward[0]->val != value)
{
int lvl = random_level();//為新的entry產生一個隨機的高度

if (lvl > level)//如果比原本層數還高
{
for (int i = level + 1;i <= lvl;i++)
{

entryBefore[i] = head;//將比原本層數還高的層，作為即將插入的entry的前一個entry
}
level = lvl;//更新高度
}

curr = new SNode(lvl, value);//創建新的entry
for (int i = 0;i <= lvl;i++)
{
curr->forward[i] = entryBefore[i]->forward[i]; //將新的entry指向下一個entry（已被entryBefore紀錄）
entryBefore[i]->forward[i] = curr;//entryBefore指向新的entry，將整個List連起來
}
}
}

刪除 Insert
---

### 一、複雜度問題 Complexity
1. 與插入類似，想找到特定位置的複雜度為 $O(logn)$ ，進行任一update操作的複雜度為 $O(1)$，Skip List的刪除操作複雜度為 $O(logn)$（圖十三）。

>### 範例：
>![](https://i.imgur.com/HIFdvOF.png =90%x)
>##### 圖十三 ⌃
>###### 說明：找到節點13並刪除，再進行串接，複雜度共$O(logn)$。
    
### 二、程式碼範例 Code

void SkipList::Delete(int &value)
{
SNode *curr = head;
SNode *entryBefore[MAX_LEVEL + 1];//同Insert
memset (entryBefore, NULL, sizeof(SNode*) * (MAX_LEVEL + 1));//同Insert
for (int i = level;i >= 0;i--)
{
while (curr->forward[i] != NULL && curr->forward[i]->val < value)
{
curr = curr->forward[i];
}
entryBefore[i] = curr;
}

curr = curr->forward[0];//將curr移動到儲存val的entry(如果有
//如果確實如此
if (curr->val == value)
{
for (int i = 0;i <= level;i++)
{
if (entryBefore[i]->forward[i] != curr)
break;
entryBefore[i]->forward[i] = curr->forward[i];//串接
}
delete curr;
while (level > 0 && head->forward[level] == NULL)//如果刪除後高度下降
{
level--;
}
}
}

<p style="page-break-after:always"></p>

結語 Epilogue
---

#### Skip Lists 是一個兼具Dynamic性質與Binary Search性質的資料結構，他能帶來快速的查找、刪除、插入。
#### 但同時，我們反觀他的缺點，其實他相較於一般的Linked List與Array，他有花費比較多的空間，複雜度為$O(\text{log} n)$，所以他在獲得速度的同時，捨棄了空間，在討論複雜度的層面上，他是一個「空間換取時間」的範例。

### 感謝閱讀。
* [name=資管一 葉又銘 學號：B10705052]
* view in HackMD:https://hackmd.io/NVTUDWaZTUSs62TazHdN5Q
    
參考文獻
--- 
1. Skip list - Wikipedia: https://en.wikipedia.org/wiki/
2. Skip Lists - Geometry Lab: https://youtu.be/NDGpsfwAaqo
3. C++ Program To Implement Skip List - Sanfoundry: 
https://www.sanfoundry.com/cpp-program-implement-skip-list/
4. 程式扎記: http://puremonkey2010.blogspot.com/2013/04/skip-list.html
5. Thomas A. Anastasio:
https://www.csee.umbc.edu/courses/undergraduate/341/fall01/Lectures/SkipLists/skip_lists/skip_lists.html

</font>