1、Skip list層次的選擇：插入列的“高度”較前者來說顯得更加重要，也更加難以確定。由于它的不確定性，使得不 同的決策可能會導致截然不同的算法效率。為了使插入數據之后，保持該數據結構進行各種 操作均為O(logn)復雜度的性質，我們引入隨機化算法(Randomized Algorithms)。我們定義一個隨機決策模塊，它的大致內容如下：產生一個0到1的隨機數rr random()如果r小于一個常數p，則執行方案A，if rp then do A否則，執行方案Belse do B初始時列高為1。插入元素時，不停地執行隨機決策模塊。如果要求執行的題 操作，則將 列的高度加1，并且繼續反復執行隨機

2、決策模塊。直到第i次，模塊要求執行的是B操作， 我們結束決策，并向跳躍表中插入一個高度為i的列。性質1：根據上述決策方法，該列的高度大于等于k的概率為plk-1)。此處有一個地方需要注意，如果得到的i比當前跳躍表的高度h還要大的話，則需要增加新 的鏈，使得跳躍表仍滿足先前所提到的條件。randomLevel()Ivl := IrandofnQ that returns a random value in 0.1)while randonfi() p and llvl MaxLevel doIvl :二 M + 1return Ivl自：數據結構與算法public void choosePowe

3、rs()powersmaxLevel-1=(2=0;i-,j+)powersi=powersi+1-(2j);public int chooseLevel()int i,r=Math.abs(rd.nextInt()%powersmaxLevel-1+1;for(i=1;imaxLevel;i+)if(rpowersi)return i-1;return i-1;假設最高層次maxLevel=4.則15個元素，在第一層需要8個節點，第二層需要4個，第三層需 要2個，第四層需要1個。每插入一個節點時，就生成一個1到15之間的隨機數r(r=Math. abs(rd .nextInt()%power

4、s maxLevel -1+1;)，如果 r9 則節點在第一層，如果 r13，那么節點插在第二層，如果rtieaderfor i := list-level down to 1 dowhile xforwardi-key forwardi- searchKjsy forward lif XTKey = search Key then x- value := newValjeelseIvl := randomLevelOif Ivl list-level thenfor i := list-level + 1 to M doupdatei := list-lieaderlistlevel:二 I

5、vlx := make Node(Ivl, search Keyr value)for i := 1 to level doxforwardi := updatei-orwardiupchteiTforwandi := xDeletefl ist: search Key)local update1 MaxLevelx :二 list-lieaderfor i := list-level down to 1 dowhile x-forwardi-key forwardiupdate i - xx := x*fbrward lit XTKey = search Key thenfor i := 1

6、 to list-level doiff updatei-forwardi # x then breakupdatep-*fbrwardi := x-*fonvandiIriee(x)while listlevel 1 andlist-header-forwardlist-level| = NIL dolist-level := list-level - 1Java實現：class SkipNodeE extends Comparable public final E value;public final SkipNode forward; / array of pointersSuppres

7、sWarnings(unchecked)public SkipNode(int level, E value)forward = new SkipNodelevel + 1;this.value = value;public class SkipSetE extends Comparablepublic static final double P = 0.5;public static final int MAX_LEVEL = 6;public static int randomLevel() int lvl = (int)(Math.log(1.-Math.random()/Math.lo

8、g(1.-P); return Math.min(lvl, MAX_LEVEL);public final SkipNode header = new SkipNode(MAX_LEVEL, null);public int level = 0;public String toString()StringBuilder sb = new StringBuilder();sb.append );SkipNode x =header.forward0;while (x != null) sb.append(xvalue);x = xforward0;if (x != null)sb.append,

9、);sb.append );return sb.toString();public boolean contains(E searchvalue) SkipNode x = header;for (int i = level; i = 0; i-) while (x.forwardi != null & x.forwardi.pareTo(searchValue) 0) x = x.forwardi; x = x.forward0;return x != null & x.value.equals(searchValue); SuppressWarnings(unchecked) public

10、 void insert(E value) SkipNode x = header; SkipNode update = new SkipNodeMAX_LEVEL + 1;for (int i = level; i = 0; i-) while (x.forwardi != null & x.forwardi.pareTo(value) level) for (int i = level + 1; i = lvl; i+) updatei =header; level = lvl;x =new SkipNode(lvl, value); for (int i = 0; i = lvl; i+

11、) x.forwardi = updatei.forwardi; updatei .forwardi = x; SuppressWarnings(unchecked)public void delete(E value) SkipNode x = header;SkipNode update = new SkipNodeMAX_LEVEL + 1;for (int i = level; i = 0; i-) while (x.forwardi != null & x.forwardi.pareTo(value) 0) x = x.forwardi;updatei = x;x = x.forwa

12、rd0;if (x.value.equals(value) for (int i = 0; i 0 & header.forwardlevel = null) level-; public static void main(String args) SkipSet ss = new SkipSet();System out.println(ss);ss.insert(5);ss.insert(10);ss.insert(7);ss.insert(7);ss.insert(6);if (ss.contains(7) Systemout.println(7 is in the list); System out.pr