舍伍德算法之跳躍表問題

問題描述

如果用有序連結清單來表示一個含有n個元素的有序集S，則在最壞情況下，搜尋S中一個元素需要O(n)計算時間。提高有序連結清單效率的一個技巧是在有序連結清單的部分結點處增設附加指針以提高其搜尋性能。在增設附加指針的有序連結清單中搜尋一個元素時，可借助于附加指針跳過連結清單中若幹結點，加快搜尋速度。這種增加了向前附加指針的有序連結清單稱為跳躍表。

應在跳躍表的哪些結點增加附加指針以及在該結點處應增加多少指針完全采用随機化方法來确定。這使得跳躍表可在O(logn)平均時間内支援關于有序集的搜尋、插入和删除等運算。

例如：如圖，(a)是一個沒有附加指針的有序表，而圖(b)在圖(a)的基礎上增加了跳躍一個節點的附加指針。圖(c)在圖(b)的基礎上又增加了跳躍3個節點的附加指針。

在跳躍表中，如果一個節點有k+1個指針，則稱此節點為一個k級節點。以圖(c)中跳躍表為例，看如何在改跳躍表中搜尋元素8。從該跳躍表的最進階，即第2級開始搜尋。利用2級指針發現元素8位于節點7和19之間。此時在節點7處降至1級指針進行搜尋，發現元素8位于節點7和13之間。最後，在節點7降至0級指針進行搜尋，發現元素8位于節點7和11之間，進而知道元素8不在搜尋的集合S中。

相關原理

在一般情況下，給定一個含有n個元素的有序連結清單，可以将它改造成一個完全跳躍表，使得每一個k級結點含有k+1個指針，分别跳過2^k-1，2^(k-1)-1，…，2^0-1個中間結點。第i個k級結點安排在跳躍表的位置i^(2^k)處，i>=0。這樣就可以在時間O(logn)内完成集合成員的搜尋運算。在一個完全跳躍表中，最進階的結點是

級結點。

完全跳躍表與完全二叉搜尋樹的情形非常類似。它雖然可以有效地支援成員搜尋運算，但不适應于集合動态變化的情況。集合元素的插入和删除運算會破壞完全跳躍表原有的平衡狀态，影響後繼元素搜尋的效率。

為了在動态變化中維持跳躍表中附加指針的平衡性，必須使跳躍表中k級結點數維持在總結點數的一定比例範圍内。注意到在一個完全跳躍表中，50%的指針是0級指針；25%的指針是1級指針；…；(100/2^(k+1))%的指針是k級指針。是以，在插入一個元素時，以機率1/2引入一個0級結點，以機率1/4引入一個1級結點，…，以機率1/2^(k+1)引入一個k級結點。另一方面，一個i級結點指向下一個同級或更進階的結點，它所跳過的結點數不再準确地維持在2^i-1。經過這樣的修改，就可以在插入或删除一個元素時，通過對跳躍表的局部修改來維持其平衡性。

跳躍表中節點的級别在插入是确定，一旦确定便不再更改。下圖是遵循上述原則的跳躍表的例子。對其進行搜尋與對完全跳躍表所作的搜尋是一樣的。如果希望在所示跳躍表中插入一個元素8，則應現在跳躍表中搜尋其插入位置。經搜尋發現應在節點7和11之間插入元素8.此時在節點7和11之間增加1個存儲元素8的新節點，并以随機的方式确定新節點的級别。例如，如果元素8是作為一個2級節點插入，則應對圖中虛線相交的指針進行調整，如果新插入的節點是一個1級節點，則隻要修改2個指針，虛線相交的指針是有可能被修改的指針，這些指針可在搜尋元素插入位置時動态地儲存起來，以供插入時使用。

在一個完全跳躍表中，具有i級指針的結點中有一半同時具有i+1級指針。為了維持跳躍表的平衡性，可以事先确定一個實數0<p<1，并要求在跳躍表中維持在具有i級指針的結點中同時具有i+1級指針的結點所占比例約為p。為此目的，在插入一個新結點時，先将其結點級别初始化為0，然後用随機數生成器反複地産生一個[0，1]間的随機實數q。如果q<p，則使新結點級别增加1，直至q>=p。由此産生新結點級别的過程可知，所産生的新結點的級别為0的機率為1-p，級别為1的機率為p(1-p)，…，級别為i的機率為p^i(1-p)。如此産生的新結點的級别有可能是一個很大的數，甚至遠遠超過表中元素的個數。為了避免這種情況，用

作為新結點級别的上界。其中n是目前跳躍表中結點個數。目前跳躍表中任一結點的級别不超過

。

代碼實作：

舍伍德算法之跳躍表問題

//随機化算法 跳躍表
#include "stdafx.h"
#include "RandomNumber.h"
#include 
#include 
using namespace std;
 
template class SkipList;
template
class SkipNode
{
    friend SkipList;
    private:
        SkipNode(int size)
        {
            next = new SkipNode*[size];
        }
        ~SkipNode()
        {
            delete []next;
        }
        EType data;//集合中的元素
        SkipNode **next;//指針數組 next[i]是第i級指針
};
 
template
class SkipList
{
    public:
        SkipList(KType Large,int MaxE = 10000,float p = 0.5);
        ~SkipList();
        bool Search(const KType& k,EType& e) const;
        SkipList& Insert(const EType& e);
        SkipList& Delete(const KType& k,EType& e);
        void Output();
    private:
        int Level();
        SkipNode *SaveSearch(const KType& k);
        int MaxLevel;                    //跳躍表級别上界
        int Levels;                        //目前最大級别
        RandomNumber rnd;                //随機數産生器
        float Prob;                        //用于配置設定節點級别
        KType TailKey;                    //元素鍵值上界
        SkipNode *head;    //頭結點指針
        SkipNode *NIL;        //尾節點指針
        SkipNode **last;    //指針數組
};
 
//構造函數
template
SkipList::SkipList(KType Large,int MaxE,float p)
{
    Prob = p;
    MaxLevel = ceil(log(float(MaxE))/log(1/p))-1;        //初始化跳躍表級别上界
    TailKey = Large;                            //元素鍵值上界
    Levels = 0;                                    //初始化目前最大級别
 
    //建立頭、尾節點和數組 last
    head = new SkipNode(MaxLevel+1);
    NIL = new SkipNode(0);
    last = new SkipNode *[MaxLevel+1];
    NIL->data = Large;
 
    //将跳躍表初始化為空表
    for(int i=0; i<=MaxLevel; i++)
    {
        head->next[i] = NIL;
    }
}
 
//析構函數
template
SkipList::~SkipList()
{
    SkipNode *next;
 
    //删除所有節點
    while(head!=NIL)
    {
        next = head->next[0];
        delete head;
        head = next;
    }
 
    delete NIL;
    delete []last;
}
 
class element
{
    friend int main(void);
    public:
        operator long() const 
        {
            return key;
        }
        element& operator = (long y)
        {
            key = y;
            return *this;
        }
    private:
        int data;
        long key;
};
 
//搜尋指定元素k
template
bool SkipList::Search(const KType& k,EType& e) const
{
    if(k>=TailKey)
    {
        return false;
    }
    //位置p恰好位于指定元素k之前
    SkipNode *p = head;
    for(int i=Levels; i>=0; i--)//逐漸向下搜尋
    {
        while(p->next[i]->data        {
            p = p->next[i];//每次搜尋盡可能滴接近要搜尋的元素
        }
    }
    e = p->next[0]->data;
    return (e==k);
}
 
//搜尋指定元素k,并将每一級中遇到的上一個節點存放在數組last中
template
SkipNode *SkipList::SaveSearch(const KType& k)
{
    //位置p恰好位于指定元素k之前
    SkipNode *p = head;
    for(int i = Levels; i>=0; i--)
    {
        while(p->next[i]->data        {
            p = p->next[i];
        }
        last[i] = p;    //上一個第i級結點
    }
    return (p->next[0]);
}
 
//産生不超過MaxLevel 的随機級别
template
int SkipList::Level()
{
    int lev = 0;
    while(rnd.fRandom()
    {
        lev++;
    }
    return (lev<=MaxLevel)?lev:MaxLevel;
}
 
//插入指定元素e
template
SkipList& SkipList::Insert(const EType& e)
{
    KType k = e;//取得元素鍵值
    if(k>=TailKey)
    {
        cout<<"元素鍵值超界!"<        return *this;
    }
    //檢查元素是否已存在
    SkipNode *p = SaveSearch(k);
    if(p->data == e)
    {
        cout<<"元素已存在!"<        return *this;
    }
 
    //元素不存在，确定新節點級别
    int lev = Level();
    //調整個級别指針
    if(lev>Levels)
    {
        for(int i=Levels+1; i<=lev; i++)
        {
            last[i] = head;
        }
        Levels = lev;
    }
 
    //産生新節點，并将新節點插入p之後
    SkipNode *y = new SkipNode(lev+1);
    y->data = e;
 
    for(int i=0; i<=lev; i++)
    {
        //插入第i級鍊
        y->next[i] = last[i]->next[i];
        last[i]->next[i] = y;
    }
    return *this;
}
 
//删除鍵值為k的元素，并将所删除的元素存入e
template
SkipList& SkipList::Delete(const KType& k,EType& e)
{
    if(k>=TailKey)
    {
        cout<<"元素鍵值超界!"<    }
    //搜尋待删除元素
    SkipNode *p = SaveSearch(k);
    if(p->data!=k)
    {
        cout<<"未找到待删除元素!"<    }
    //從跳躍表中删除節點
    for(int i=0; i<=Levels && last[i]->next[i] == p; i++)
    {
        last[i]->next[i] = p->next[i];
    }
    //更新目前級别
    while(Levels>0 && head->next[Levels] == NIL)
    {
        Levels--;
    }
    e = p->data;
    delete p;
    return *this;
}
 
//輸出集合中的元素
template
void SkipList::Output()
{
    SkipNode *y = head->next[0];
    for(;y!=NIL; y=y->next[0])
    {
        cout<data<<' ';
    }
    cout<}
 
int main()
{
    SkipList *s = new SkipList(100,10,0.5);
 
    //建立
    cout<<"=========建立==========="< 
    int a[] = {5,3,2,11,7,13,19,17,23};
 
    for(int i=0; i<9; i++)
    {
        s->Insert(a[i]);
    }
    s->Output();
 
    //搜尋
    cout<<"=========搜尋==========="<    int k=17,e;
    cout<<"搜尋元素k="<    if(s->Search(17,e))
    {
        cout<<"位置搜尋結果為：k="<    }
    cout< 
    //删除
    cout<<"=========删除==========="<    cout<<"删除跳躍表元素k="<    s->Delete(k,e);
    s->Output();
 
    delete s;
    return 0;
}

View Code

舍伍德算法之跳躍表問題

#include"time.h"
//随機數類
const unsigned long maxshort = 65536L;
const unsigned long multiplier = 1194211693L;
const unsigned long adder = 12345L;
 
class RandomNumber
{
    private:
        //目前種子
        unsigned long randSeed;
    public:
        RandomNumber(unsigned long s = 0);//構造函數，預設值0表示由系統自動産生種子
        unsigned short Random(unsigned long n);//産生0：n-1之間的随機整數
        double fRandom(void);//産生[0,1)之間的随機實數
};
 
RandomNumber::RandomNumber(unsigned long s)//産生種子
{
    if(s == 0)
    {
        randSeed = time(0);//用系統時間産生種子
    }
    else
    {
        randSeed = s;//由使用者提供種子
    }
}
 
unsigned short RandomNumber::Random(unsigned long n)//産生0：n-1之間的随機整數
{
    randSeed = multiplier * randSeed + adder;//線性同餘式
    return (unsigned short)((randSeed>>16)%n);
}
 
double RandomNumber::fRandom(void)//産生[0,1)之間的随機實數
{
    return Random(maxshort)/double(maxshort);
}

View Code

運作結果：

效率分析：

當跳躍表中有n個元素時，在最壞情況下，對跳躍表進行搜尋，插入和删除運算所需的計算時間均為O(n+maxLevel).在最壞情況下，可能隻有一個1個maxLevel級的元素，其餘元素均在0級鍊上。此時跳躍表退化為有序連結清單。由于跳躍表采用了随機化技術，它的每一種運算在最壞情況下的期望時間均為O（logn）

在一般情況下，跳躍表的一級鍊上大約有n*p個元素，二級鍊上大約有n*p^2個元素，......i級鍊上有n*p^i個元素。是以跳躍表所占用的空間為O(n），特别的，當p=0.5時，約需要2n個指針空間。

舍伍德算法之跳躍表問題

繼續閱讀

Codeforces 1417 D. Make Them Equal(思維+構造)

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希