資源描述：
《0046算法筆記——【隨機化算法】舍伍德隨機化思想解決跳躍表問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、問題描述???如果用有序鏈表來表示一個含有n個元素的有序集S，則在最壞情況下，搜索S中一個元素需要O(n)計算時間。提高有序鏈表效率的一個技巧是在有序鏈表的部分結(jié)點處增設(shè)附加指針以提高其搜索性能。在增設(shè)附加指針的有序鏈表中搜索一個元素時，可借助于附加指針跳過鏈表中若干結(jié)點，加快搜索速度。這種增加了向前附加指針的有序鏈表稱為跳躍表。???應(yīng)在跳躍表的哪些結(jié)點增加附加指針以及在該結(jié)點處應(yīng)增加多少指針完全采用隨機化方法來確定。這使得跳躍表可在O(logn)平均時間內(nèi)支持關(guān)于有序集的搜索、插入和刪除等運算。????例如：如圖，(a)是一個
2、沒有附加指針的有序表，而圖(b)在圖(a)的基礎(chǔ)上增加了跳躍一個節(jié)點的附加指針。圖(c)在圖(b)的基礎(chǔ)上又增加了跳躍3個節(jié)點的附加指針。??在跳躍表中，如果一個節(jié)點有k+1個指針，則稱此節(jié)點為一個k級節(jié)點。以圖(c)中跳躍表為例，看如何在改跳躍表中搜索元素8。從該跳躍表的最高級，即第2級開始搜索。利用2級指針發(fā)現(xiàn)元素8位于節(jié)點7和19之間。此時在節(jié)點7處降至1級指針進行搜索，發(fā)現(xiàn)元素8位于節(jié)點7和13之間。最后，在節(jié)點7降至0級指針進行搜索，發(fā)現(xiàn)元素8位于節(jié)點7和11之間，從而知道元素8不在搜索的集合S中。???相關(guān)原理???在
3、一般情況下，給定一個含有n個元素的有序鏈表，可以將它改造成一個完全跳躍表，使得每一個k級結(jié)點含有k+1個指針，分別跳過2^k-1，2^(k-1)-1，…，2^0-1個中間結(jié)點。第i個k級結(jié)點安排在跳躍表的位置i2^k處，i>=0。這樣就可以在時間O(logn)內(nèi)完成集合成員的搜索運算。在一個完全跳躍表中，最高級的結(jié)點是級結(jié)點。???完全跳躍表與完全二叉搜索樹的情形非常類似。它雖然可以有效地支持成員搜索運算，但不適應(yīng)于集合動態(tài)變化的情況。集合元素的插入和刪除運算會破壞完全跳躍表原有的平衡狀態(tài)，影響后繼元素搜索的效率。???為了在動態(tài)
4、變化中維持跳躍表中附加指針的平衡性，必須使跳躍表中k級結(jié)點數(shù)維持在總結(jié)點數(shù)的一定比例范圍內(nèi)。注意到在一個完全跳躍表中，50%的指針是0級指針；25%的指針是1級指針；…；(100/2^(k+1))%的指針是k級指針。因此，在插入一個元素時，以概率1/2引入一個0級結(jié)點，以概率1/4引入一個1級結(jié)點，…，以概率1/2^(k+1)引入一個k級結(jié)點。另一方面，一個i級結(jié)點指向下一個同級或更高級的結(jié)點，它所跳過的結(jié)點數(shù)不再準確地維持在2^i-1。經(jīng)過這樣的修改，就可以在插入或刪除一個元素時，通過對跳躍表的局部修改來維持其平衡性。????跳
5、躍表中節(jié)點的級別在插入是確定，一旦確定便不再更改。下圖是遵循上述原則的跳躍表的例子。對其進行搜索與對完全跳躍表所作的搜索是一樣的。如果希望在所示跳躍表中插入一個元素8，則應(yīng)現(xiàn)在跳躍表中搜索其插入位置。經(jīng)搜索發(fā)現(xiàn)應(yīng)在節(jié)點7和11之間插入元素8.此時在節(jié)點7和11之間增加1個存儲元素8的新節(jié)點，并以隨機的方式確定新節(jié)點的級別。例如，如果元素8是作為一個2級節(jié)點插入，則應(yīng)對圖中虛線相交的指針進行調(diào)整，如果新插入的節(jié)點是一個1級節(jié)點，則只要修改2個指針，虛線相交的指針是有可能被修改的指針，這些指針可在搜索元素插入位置時動態(tài)地保存起來，以供
6、插入時使用。???在一個完全跳躍表中，具有i級指針的結(jié)點中有一半同時具有i+1級指針。為了維持跳躍表的平衡性，可以事先確定一個實數(shù)0=p。由此產(chǎn)生新結(jié)點級別的過程可知，所產(chǎn)生的新結(jié)點的級別為0的概率為1-p，級別為1的概率為p(1-p)，…，級別為i的概率為p^i(1-p)。如此產(chǎn)生的
7、新結(jié)點的級別有可能是一個很大的數(shù)，甚至遠遠超過表中元素的個數(shù)。為了避免這種情況，用作為新結(jié)點級別的上界。其中n是當(dāng)前跳躍表中結(jié)點個數(shù)。當(dāng)前跳躍表中任一結(jié)點的級別不超過?。???算法具體實現(xiàn)如下：???1、RandomNumber.h[cpp]?viewplain?copy1.#include"time.h"??2.//隨機數(shù)類??3.const?unsigned?long?maxshort?=?65536L;??4.const?unsigned?long?multiplier?=?1194211693L;??5.const?uns
8、igned?long?adder?=?12345L;??6.??7.class?RandomNumber??8.{??9.????private:??10.????????//當(dāng)前種子??11.????????unsigned?long?randS
