Skip list層次的選擇以及刪除算法

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

2、決策模塊。直到第i次，模塊要求執(zhí)行的是B操作， 我們結(jié)束決策，并向跳躍表中插入一個(gè)高度為i的列。性質(zhì)1：根據(jù)上述決策方法，該列的高度大于等于k的概率為plk-1)。此處有一個(gè)地方需要注意，如果得到的i比當(dāng)前跳躍表的高度h還要大的話，則需要增加新 的鏈，使得跳躍表仍滿足先前所提到的條件。randomLevel()Ivl := IrandofnQ that returns a random value in 0.1)while randonfi() p and llvl MaxLevel doIvl :二 M + 1return Ivl自：數(shù)據(jù)結(jié)構(gòu)與算法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;假設(shè)最高層次maxLevel=4.則15個(gè)元素，在第一層需要8個(gè)節(jié)點(diǎn)，第二層需要4個(gè)，第三層需 要2個(gè)，第四層需要1個(gè)。每插入一個(gè)節(jié)點(diǎn)時(shí)，就生成一個(gè)1到15之間的隨機(jī)數(shù)r(r=Math. abs(rd .nextInt()%power

4、s maxLevel -1+1;)，如果 r9 則節(jié)點(diǎn)在第一層，如果 r13，那么節(jié)點(diǎn)插在第二層，如果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實(shí)現(xiàn)：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