跳表的簡單實現(xiàn)

跳表(SkipList)是一種檢索效率非常高的數(shù)據(jù)結構，其檢索效率經(jīng)證明與紅黑樹相當。但是祭隔，輪到實現(xiàn)復雜度比較的時候，跳表可就把紅黑樹路操、AVL樹等結構足足甩出了八條街疾渴，以至于LevelDB、Redis等著名的工程項目當中屯仗，都采取了跳表的實現(xiàn)方案搞坝。
另外，在并發(fā)環(huán)境下魁袜，SkipList相對于經(jīng)典樹形結構還有一點優(yōu)勢桩撮。紅黑樹在插入和刪除的時候可能會有涉及到樹中多節(jié)點的rebalance操作敦第，而SkipList的變化操作則會更加局部性一些，需要被加鎖的節(jié)點更少店量，因此在并發(fā)環(huán)境下理論上性能會更好一些芜果。
本質上，跳表是一種添加了多級“索引”的鏈表融师，采用了空間換時間的方式右钾，通過隨機的方式?jīng)Q定節(jié)點的層級數(shù)，在節(jié)點的層級上均維護該節(jié)點的連接節(jié)點旱爆，即舀射，將連接指針變成了一個數(shù)組。
跳表的簡易實現(xiàn)代碼如下：
  
// 跳表實現(xiàn)
  
#include <stdio.h>  
#include <assert.h>  
#include <stdlib.h>  
#include <time.h>  
  
/* 跳表節(jié)點數(shù)據(jù)結構 
 * 
 */  
template <typename TData>  
struct SkipListNode  
{  
    TData value; // 節(jié)點值  
    SkipListNode<TData>** forward;  // 節(jié)點前向指針數(shù)組  
};  
  
/* 跳表操作的返回碼 
 */  
enum  
{  
    SKIP_LIST_TMPL_INSERT_NODE_SUCCESS = 0,                        // 插入節(jié)點成功  
    SKIP_LIST_TMPL_GET_FREE_SKIP_LIST_NODE_FAILED = 1,     // 獲取空閑節(jié)點失敗  
    SKIP_LIST_TMPL_NODE_EXIST = 2,                         // 節(jié)點已經(jīng)存在  
    SKIP_LIST_TMPL_NODE_NOT_EXIST = 3,                     // 節(jié)點不存在于跳表中  
    SKIP_LIST_TMPL_DELETE_NODE_SUCCESS = 4,                   // 刪除節(jié)點成功  
};  
  
/* 跳表 
 * 
 */  
template <typename TData>  
class SkipListTmpl  
{  
public:  
    /* 初始化跳表 
     */  
    bool InitSkipListTmpl();  
  
    /* 獲取一個空閑的跳表節(jié)點 
     * @param level  跳表節(jié)點的層數(shù) 
     * @return 返回NULL表示創(chuàng)建失敗怀伦，否則返回創(chuàng)建的跳表節(jié)點指針 
     */  
    SkipListNode<TData>* GetFreeSkipListNode(int level);  
  
    /* 增加一個跳表節(jié)點 
     * @param value 節(jié)點值 
     * @return 返回操作碼脆烟，詳情看上面跳表操作返回碼的意義 
     */  
    int InsertSkipListNode(const TData &value);  
  
    /* 刪除一個跳表節(jié)點 
     * @param value 節(jié)點值 
     * @return 返回操作碼，詳情看上面跳表操作返回碼的意義 
     */  
    int DeleteSkipListNode(const TData &value);  
  
    /* 查找跳表節(jié)點 
     * @param value 節(jié)點值 
     * @return 返回NULL表示查找失敗空镜，否則返回找到了跳表節(jié)點指針 
     */  
    SkipListNode<TData>* SearchSkipListNode(const TData &value);  
  
    /* 遍歷處理跳表中所有節(jié)點 
     * @param proc 回調的處理函數(shù) 
     * @return 返回處理的節(jié)點數(shù)目 
     */  
    int ProcessEverySkipListNode(void (*proc)(const TData &value));  
  
private:  
    int level; // 當前跳表的最大層數(shù)  
    SkipListNode<TData>* header;  // 跳表頭節(jié)點  
  
private:  
    const static int MAX_SKIP_LIST_TMPL_LEVEL = 32;  // 跳表的最大層數(shù)  
    const static double SKIP_LIST_TMPL_LEVEL_PROBABILITY;  // i-1層節(jié)點屬于i層的概率  
  
private:  
    /* 獲取一個節(jié)點的層數(shù)浩淘，層數(shù)范圍 
     * @return 節(jié)點的層數(shù) 
     */  
    int GetRandomSkipListNodeLevel();  
};  
  
// i-1層節(jié)點屬于i層的概率  
template <typename TData>  
const double SkipListTmpl<TData>::SKIP_LIST_TMPL_LEVEL_PROBABILITY = 0.5;  
  
/* 創(chuàng)建一個空的跳表節(jié)點 
 * @param level  跳表節(jié)點的層數(shù) 
 * @return 返回NULL表示創(chuàng)建失敗，否則返回創(chuàng)建的跳表節(jié)點指針 
 */  
template <typename TData>  
SkipListNode<TData>* SkipListTmpl<TData>::GetFreeSkipListNode(int level)  
{  
    // 節(jié)點層數(shù)范圍0  
    assert(level >= 0 && level < MAX_SKIP_LIST_TMPL_LEVEL);  
  
    SkipListNode<TData>* newNode = (SkipListNode<TData>*)malloc(sizeof(SkipListNode<TData>));  
    if (NULL == newNode)  
    {  
        return NULL;  
    }  
      
    // 前向節(jié)點初始化為NULL  
    newNode->forward = (SkipListNode<TData> **)malloc(sizeof(SkipListNode<TData>*) * (level+1));  
    if (NULL == newNode->forward)  
    {  
  
        // 申請內存失敗那么就歸還之前申請的內存  
        free(newNode);  
        return NULL;  
    }  
      
    for (int i = 0; i <= level; ++i)  
    {  
        newNode->forward[i] = NULL;  
    }  
  
    // 創(chuàng)建好的跳表節(jié)點  
    return newNode;  
}  
  
/* 初始化跳表 
 */  
template <typename TData>  
bool SkipListTmpl<TData>::InitSkipListTmpl()  
{  
    level = 0; // 當前最大層初始為0  
      
    // 頭結點的層數(shù)為跳表最大層數(shù)吴攒，這個節(jié)點是個冗余節(jié)點张抄，增加它是為了方便鏈表操作  
    header = GetFreeSkipListNode(MAX_SKIP_LIST_TMPL_LEVEL-1);  
  
    // 初始化成功  
    if (header)  
    {  
        return true;  
    }  
  
    // 初始化失敗  
    return false;  
}  
  
/* 增加一個跳表節(jié)點 
 * @param value 節(jié)點值 
 * @return 返回操作碼，詳情看上面跳表操作返回碼的意義 
 */  
template <typename TData>  
int SkipListTmpl<TData>::InsertSkipListNode(const TData &value)  
{  
    // 保證跳表已經(jīng)初始化  
    assert(NULL != header);  
  
    // 首先查找節(jié)點的插入位置  
    SkipListNode<TData>* update[MAX_SKIP_LIST_TMPL_LEVEL];  // 插入節(jié)點的前驅節(jié)點數(shù)組  
  
    SkipListNode<TData>* p = header;  
    SkipListNode<TData>* q = NULL;  
  
    // 找到跳表中插入節(jié)點的前驅節(jié)點  
    for (int k = level; k >= 0; --k)  
    {  
        q = p->forward[k];  
        while(q && q->value < value)  
        {  
            p = q;  
            q = q->forward[k];  
        }  
        update[k] = p;  
    }  
  
    // 說明節(jié)點已經(jīng)存在  
    if (q && value == q->value)  
    {  
        return SKIP_LIST_TMPL_NODE_EXIST;  
    }  
  
    // 隨機獲取到插入節(jié)點的層數(shù)  
    int nodelevel = GetRandomSkipListNodeLevel();  
  
    // 如果插入節(jié)點層數(shù)大于當前跳表的最大層數(shù)洼怔，需要更新插入節(jié)點的前驅節(jié)點數(shù)組  
    while(nodelevel > level)  
    {  
        ++level;  
        update[level] = header;  
    }  
  
    // 獲取一個空閑的跳表節(jié)點  
    SkipListNode<TData>* freeNode = GetFreeSkipListNode(nodelevel);  
    if (NULL == freeNode)  
    {  
        // 獲取空閑節(jié)點失敗  
        return SKIP_LIST_TMPL_GET_FREE_SKIP_LIST_NODE_FAILED;  
    }  
  
    // 初始化該節(jié)點  
    freeNode->value = value;  
  
    // 將節(jié)點插入到跳表中署惯，update數(shù)組中保存了節(jié)點的不同層的前驅節(jié)點數(shù)組  
    for (int k = 0; k <= nodelevel; ++k)  
    {  
        freeNode->forward[k] = update[k]->forward[k];  
        update[k]->forward[k] = freeNode;  
    }  
  
    return SKIP_LIST_TMPL_INSERT_NODE_SUCCESS;  
}  
  
/* 刪除一個跳表節(jié)點 
 * @param value 節(jié)點值 
 * @return 返回操作碼，詳情看上面跳表操作返回碼的意義 
 */  
template <typename TData>  
int SkipListTmpl<TData>::DeleteSkipListNode(const TData &value)  
{  
    // 保證跳表已經(jīng)初始化  
    assert(NULL != header);  
      
    // 首先查找節(jié)點的前驅節(jié)點數(shù)組  
    SkipListNode<TData>* update[MAX_SKIP_LIST_TMPL_LEVEL];  // 刪除節(jié)點的前驅節(jié)點數(shù)組  
      
    SkipListNode<TData>* p = header;  
    SkipListNode<TData>* q = NULL;  
  
    // 找到跳表中刪除節(jié)點的前驅節(jié)點  
    for (int k = level; k >= 0; --k)  
    {  
        q = p->forward[k];  
        while(q && q->value < value)  
        {  
            p = q;  
            q = q->forward[k];  
        }  
        update[k] = p;  
    }  
  
    // 說明刪除節(jié)點存在  
    if (q && q->value == value)  
    {  
        for (int k = 0; k <= level && update[k]->forward[k] == q; ++k)  
        {  
            update[k]->forward[k] = q->forward[k];  
        }  
        free(q->forward);  
        free(q);  
  
        // 如果q節(jié)點剛好是跳表中的最大層節(jié)點镣隶，需要更新當前跳表的最大層  
        while(NULL == header->forward[level] && level > 0)  
        {  
            --level;  
        }  
  
        // 刪除節(jié)點成功  
        return SKIP_LIST_TMPL_INSERT_NODE_SUCCESS;  
    }  
    else  
    {  
        // 說明刪除節(jié)點不存在  
        return SKIP_LIST_TMPL_NODE_NOT_EXIST;  
    }  
}  
  
/* 查找跳表節(jié)點 
 * @param value 節(jié)點值 
 * @return 返回NULL表示查找失敗极谊，否則返回找到了跳表節(jié)點指針 
 */  
template <typename TData>  
SkipListNode<TData>* SkipListTmpl<TData>::SearchSkipListNode(const TData &value)  
{  
    // 確保跳表已經(jīng)初始化  
    assert(NULL != header);  
  
    SkipListNode<TData>* p = header;  
    SkipListNode<TData>* q = NULL;  
      
    for (int k = level; k >= 0; --k)  
    {  
        q = p->forward[k];  
        while(q && q->value < value)  
        {  
            p = q;  
            q = q->forward[k];  
        }  
    }  
  
    // 說明找到節(jié)點了  
    if (q && q->value == value)  
    {  
        return q;  
    }  
    else  
    {  
        // 說明沒有找到節(jié)點  
        return NULL;  
    }  
}  
  
/* 遍歷處理跳表中所有節(jié)點 
 * @param proc 回調的處理函數(shù) 
 * @return 返回處理的節(jié)點數(shù)目 
 */  
template <typename TData>  
int SkipListTmpl<TData>::ProcessEverySkipListNode(void (*proc)(const TData &value))  
{  
    // 確保跳表已經(jīng)初始化  
    assert(NULL != header);  
      
    int cnt = 0;  
    SkipListNode<TData>* p = header->forward[0];  
    while(p)  
    {  
        proc(p->value);  
        cnt++;  
        p = p->forward[0];  
    }  
    return cnt;  
}  
  
  
/* 隨機獲取一個節(jié)點的層數(shù)，層數(shù)范圍0 - (MAX_SKIP_LIST_TMPL_LEVEL-1) 
 * @return 節(jié)點的層數(shù) 
 */  
template <typename TData>  
int SkipListTmpl<TData>::GetRandomSkipListNodeLevel()  
{  
    // 選擇一個種子值  
    static bool seedInit = false;  
    if (!seedInit)  
    {  
        srand(time(NULL));  
        seedInit = true;  
    }  
      
    // 根據(jù)概率計算出節(jié)點的層數(shù)  
    int newLevel = 0;  
    while(1)  
    {  
        double curP = (double)(rand() % 100) / 100.0;  
        if (curP < SKIP_LIST_TMPL_LEVEL_PROBABILITY)  
        {  
            newLevel++;  
        }  
        else  
        {  
            break;  
        }  
  
        // 最大層數(shù)是MAX_SKIP_LIST_TMPL_LEVEL-1  
        if ( (MAX_SKIP_LIST_TMPL_LEVEL-1) <= newLevel)  
        {  
            break;  
        }  
    }  
      
    // 最大層數(shù)是MAX_SKIP_LIST_TMPL_LEVEL-1  
    if (newLevel >= MAX_SKIP_LIST_TMPL_LEVEL)  
    {  
        newLevel = MAX_SKIP_LIST_TMPL_LEVEL - 1;  
    }  
  
    return newLevel;  
}