跳表的定義
跳表(SkipList)：增加了向前指針的鏈表叫做跳表。跳表全稱(chēng)叫做跳躍表，簡(jiǎn)稱(chēng)跳表。跳表是一個(gè)隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)，實(shí)質(zhì)是一種可以進(jìn)行近似二分查找的有序鏈表。跳表在原有的有序鏈表上增加了多級(jí)索引，通過(guò)索引來(lái)實(shí)現(xiàn)快速查詢(xún)。跳表不僅能提高搜索性能，同時(shí)也可以提高插入和刪除操作的性能。
跳表的詳解
有序原始鏈表
對(duì)于一個(gè)單鏈表來(lái)說(shuō)，即使鏈表中的數(shù)據(jù)是有序的，如果我們想要查找某個(gè)數(shù)據(jù)，也必須從頭到尾的遍歷鏈表，很顯然這種查找效率是十分低效的，時(shí)間復(fù)雜度為O(n)。
那么我們?nèi)绾翁岣卟檎倚誓?？我們可以?duì)鏈表建立一級(jí)“索引”，每?jī)蓚€(gè)結(jié)點(diǎn)提取一個(gè)結(jié)點(diǎn)到上一級(jí)，我們把抽取出來(lái)的那一級(jí)叫做索引或者索引層，如下圖所示，我建立了兩級(jí)索引，down表示down指針。
image.png
假設(shè)我們現(xiàn)在要查找值為16的這個(gè)結(jié)點(diǎn)。我們可以先在索引層遍歷，當(dāng)遍歷索引層中值為13的時(shí)候，通過(guò)值為13的結(jié)點(diǎn)的指針域發(fā)現(xiàn)下一個(gè)結(jié)點(diǎn)值為17，因?yàn)殒湵肀旧碛行?，所以值?6的結(jié)點(diǎn)肯定在13和17這兩個(gè)結(jié)點(diǎn)之間。然后我們通過(guò)索引層結(jié)點(diǎn)的down指針，下降到原始鏈表這一層，繼續(xù)往后遍歷查找。這個(gè)時(shí)候我們只需要遍歷2個(gè)結(jié)點(diǎn)（值為13和16的結(jié)點(diǎn)），就可以找到值等于16的這個(gè)結(jié)點(diǎn)了。如果使用原來(lái)的鏈表方式進(jìn)行查找值為16的結(jié)點(diǎn)，則需要遍歷10個(gè)結(jié)點(diǎn)才能找到，而現(xiàn)在只需要遍歷7個(gè)結(jié)點(diǎn)即可，從而提高了查找效率。
那么我們可以由此得到啟發(fā)，和上面建立第一級(jí)索引的方式相似，在第一級(jí)索引的基礎(chǔ)上，每?jī)蓚€(gè)一級(jí)索引結(jié)點(diǎn)就抽到一個(gè)結(jié)點(diǎn)到第二級(jí)索引中。再來(lái)查找值為16的結(jié)點(diǎn)，只需要遍歷6個(gè)結(jié)點(diǎn)即可，從而進(jìn)一步提高了查找效率。
跳表的時(shí)間復(fù)雜度
單鏈表的查找時(shí)間復(fù)雜度為：O(n)，
下面分析下跳表這種數(shù)據(jù)結(jié)構(gòu)的查找時(shí)間復(fù)雜度：
我們首先考慮這樣一個(gè)問(wèn)題，如果鏈表里有n個(gè)結(jié)點(diǎn)，那么會(huì)有多少級(jí)索引呢？按照上面講的，每?jī)蓚€(gè)結(jié)點(diǎn)都會(huì)抽出一個(gè)結(jié)點(diǎn)作為上一級(jí)索引的結(jié)點(diǎn)。那么第一級(jí)索引的個(gè)數(shù)大約就是n/2，第二級(jí)的索引大約就是n/4，第三級(jí)的索引就是n/8，依次類(lèi)推，也就是說(shuō)，第k級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)是第k-1級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)的1/2，那么第k級(jí)的索引結(jié)點(diǎn)個(gè)數(shù)為n/(2k)。
、】
`
假設(shè)索引有h級(jí)，最高級(jí)的索引有2個(gè)結(jié)點(diǎn)，通過(guò)上面的公式，我們可以得到，從而可得：h =log2n-1。如果包含原始鏈表這一層，整個(gè)跳表的高度就是。我們?cè)谔碇胁檎夷硞€(gè)數(shù)據(jù)的時(shí)候，如果每一層都要遍歷m個(gè)結(jié)點(diǎn)，那么在跳表中查詢(xún)一個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度就為O(m*logn)。
其實(shí)根據(jù)前面的分析，我們不難得出m=3，即每一級(jí)索引都最多只需要遍歷3個(gè)結(jié)點(diǎn)，分析如下：
時(shí)間復(fù)雜度分析
如上圖所示，假如我們要查找的數(shù)據(jù)是x，在第k級(jí)索引中，我們遍歷到y(tǒng)結(jié)點(diǎn)之后，發(fā)現(xiàn)x大于y，小于y后面的結(jié)點(diǎn)z。所以我們通過(guò)y的down指針，從第k級(jí)索引下降到第k-1級(jí)索引。在第k-1級(jí)索引中，y和z之間只有3個(gè)結(jié)點(diǎn)(包含y和z)。所以，我們?cè)趉-1級(jí)索引中最多需要遍歷3個(gè)結(jié)點(diǎn)，以此類(lèi)推，每一級(jí)索引都最多只需要遍歷3個(gè)結(jié)點(diǎn)。
因此，m=3，所以跳表查找任意數(shù)據(jù)的時(shí)間復(fù)雜度為O(logn)，這個(gè)查找的時(shí)間復(fù)雜度和二分查找是一樣的，但是我們卻是基于單鏈表這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的。不過(guò)，天下沒(méi)有免費(fèi)的午餐，這種查找效率的提升是建立在很多級(jí)索引之上的，即空間換時(shí)間的思想。其具體空間復(fù)雜度見(jiàn)下文詳解。
跳表的空間復(fù)雜度
比起單純的單鏈表，跳表就需要額外的存儲(chǔ)空間去存儲(chǔ)多級(jí)索引。假設(shè)原始鏈表的大小為n，那么第一級(jí)索引大約有n/2個(gè)結(jié)點(diǎn)，第二級(jí)索引大約有4/n個(gè)結(jié)點(diǎn)，依次類(lèi)推，每上升一級(jí)索引結(jié)點(diǎn)的個(gè)數(shù)就減少一半，直到剩下最后2個(gè)結(jié)點(diǎn)，如下圖所示，其實(shí)就是一個(gè)等比數(shù)列。
空間復(fù)雜度
這幾級(jí)索引結(jié)點(diǎn)總和為：n/2 + n/4 + n/8 + ... + 8 + 4 + 2 = n - 2。所以跳表的空間復(fù)雜度為O(n)。也就是說(shuō)如果將包含n個(gè)結(jié)點(diǎn)的單鏈表構(gòu)造成跳表，我們需要額外再用接近n個(gè)結(jié)點(diǎn)的存儲(chǔ)空間。
其實(shí)從上面的分析，我們利用空間換時(shí)間的思想，已經(jīng)把時(shí)間壓縮到了極致，因?yàn)槊恳患?jí)每?jī)蓚€(gè)索引結(jié)點(diǎn)就有一個(gè)會(huì)被抽到上一級(jí)的索引結(jié)點(diǎn)中，所以此時(shí)跳表所需要的額外內(nèi)存空間最多，即空間復(fù)雜度最高。其實(shí)我們可以通過(guò)改變抽取結(jié)點(diǎn)的間距來(lái)降低跳表的空間復(fù)雜度，在其時(shí)間復(fù)雜度和空間復(fù)雜度方面取一個(gè)綜合性能，當(dāng)然也要看具體情況，如果內(nèi)存空間足夠，那就可以選擇最小的結(jié)點(diǎn)間距，即每?jī)蓚€(gè)索引結(jié)點(diǎn)抽取一個(gè)結(jié)點(diǎn)到上一級(jí)索引中。如果想降低跳表的空間復(fù)雜度，則可以選擇每三個(gè)或者每五個(gè)結(jié)點(diǎn)，抽取一個(gè)結(jié)點(diǎn)到上級(jí)索引中。
image.png
如上圖所示，每三個(gè)結(jié)點(diǎn)抽取一個(gè)結(jié)點(diǎn)到上一級(jí)索引中，則第一級(jí)需要大約n/3個(gè)結(jié)點(diǎn)，第二級(jí)索引大約需要n/9個(gè)結(jié)點(diǎn)。每往上一級(jí)，索引的結(jié)點(diǎn)個(gè)數(shù)就除以3，為了方便計(jì)算，我們假設(shè)最高一級(jí)的索引結(jié)點(diǎn)個(gè)數(shù)為1，則可以得到一個(gè)等比數(shù)列，去下圖所示：
image.png
通過(guò)等比數(shù)列的求和公式，總的索引結(jié)點(diǎn)大約是：n/3 + n /9 + n/27 + ... + 9 + 3 + 1 = n/2。盡管空間復(fù)雜度還是O(n)，但是比之前的每?jī)蓚€(gè)結(jié)點(diǎn)抽一個(gè)結(jié)點(diǎn)的索引構(gòu)建方法，可以減少了一半的索引結(jié)點(diǎn)存儲(chǔ)空間。
實(shí)際上，在軟件開(kāi)發(fā)中，我們不必太在意索引占用的額外空間。在講數(shù)據(jù)結(jié)構(gòu)的時(shí)候，我們習(xí)慣性地把要處理的數(shù)據(jù)看成整數(shù)，但是在實(shí)際的軟件開(kāi)發(fā)中，原始鏈表中存儲(chǔ)的有可能是很大的對(duì)象，而索引結(jié)點(diǎn)只需要存儲(chǔ)關(guān)鍵值和幾個(gè)指針，并不需要存儲(chǔ)對(duì)象，所以當(dāng)對(duì)象比索引結(jié)點(diǎn)大很多時(shí)，那索引占用的額外空間就可以忽略了。
5、跳表的插入
跳表插入的時(shí)間復(fù)雜度為：O(logn)，支持高效的動(dòng)態(tài)插入。
在單鏈表中，一旦定位好要插入的位置，插入結(jié)點(diǎn)的時(shí)間復(fù)雜度是很低的，就是O(1)。但是為了保證原始鏈表中數(shù)據(jù)的有序性，我們需要先找到要插入的位置，這個(gè)查找的操作就會(huì)比較耗時(shí)。
對(duì)于純粹的單鏈表，需要遍歷每個(gè)結(jié)點(diǎn)，來(lái)找到插入的位置。但是對(duì)于跳表來(lái)說(shuō)，查找的時(shí)間復(fù)雜度為O(logn)，所以這里查找某個(gè)數(shù)據(jù)應(yīng)該插入的位置的時(shí)間復(fù)雜度也是O(logn)，如下圖所示：
image.png
6、跳表的刪除
跳表的刪除操作時(shí)間復(fù)雜度為：O(logn)，支持動(dòng)態(tài)的刪除。
在跳表中刪除某個(gè)結(jié)點(diǎn)時(shí)，如果這個(gè)結(jié)點(diǎn)在索引中也出現(xiàn)了，我們除了要?jiǎng)h除原始鏈表中的結(jié)點(diǎn)，還要?jiǎng)h除索引中的。因?yàn)閱捂湵碇械膭h除操作需要拿到刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，然后再通過(guò)指針操作完成刪除。所以在查找要?jiǎng)h除的結(jié)點(diǎn)的時(shí)候，一定要獲取前驅(qū)結(jié)點(diǎn)（雙向鏈表除外）。因此跳表的刪除操作時(shí)間復(fù)雜度即為O(logn)。
7、跳表索引動(dòng)態(tài)更新
當(dāng)我們不斷地往跳表中插入數(shù)據(jù)時(shí)，我們?nèi)绻桓滤饕?，就有可能出現(xiàn)某2個(gè)索引節(jié)點(diǎn)之間的數(shù)據(jù)非常多的情況，在極端情況下，跳表還會(huì)退化成單鏈表，如下圖所示：
image.png
作為一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，我們需要某種手段來(lái)維護(hù)索引與原始鏈表大小之間的平衡，也就是說(shuō)，如果鏈表中的結(jié)點(diǎn)多了，索引結(jié)點(diǎn)就相應(yīng)地增加一些，避免復(fù)雜度退化，以及查找、插入和刪除操作性能的下降。
如果你了解紅黑樹(shù)、AVL樹(shù)這樣的平衡二叉樹(shù)，你就會(huì)知道它們是通過(guò)左右旋的方式保持左右子樹(shù)的大小平衡，而跳表是通過(guò)隨機(jī)函數(shù)來(lái)維護(hù)“平衡性”。
當(dāng)我們往跳表中插入數(shù)據(jù)的時(shí)候，我們可以通過(guò)一個(gè)隨機(jī)函數(shù)，來(lái)決定這個(gè)結(jié)點(diǎn)插入到哪幾級(jí)索引層中，比如隨機(jī)函數(shù)生成了值K，那我們就將這個(gè)結(jié)點(diǎn)添加到第一級(jí)到第K級(jí)這個(gè)K級(jí)索引中。如下圖中要插入數(shù)據(jù)為6，K=2的例子：
image.png
隨機(jī)函數(shù)的選擇是非常有講究的，從概率上講，能夠保證跳表的索引大小和數(shù)據(jù)大小平衡性，不至于性能的過(guò)度退化。至于隨機(jī)函數(shù)的選擇，見(jiàn)下面的代碼實(shí)現(xiàn)過(guò)程，而且實(shí)現(xiàn)過(guò)程并不是重點(diǎn)，掌握思想即可。
8、跳表的性質(zhì)
(1) 由很多層結(jié)構(gòu)組成，level是通過(guò)一定的概率隨機(jī)產(chǎn)生的；
(2) 每一層都是一個(gè)有序的鏈表，默認(rèn)是升序 ；
(3) 最底層(Level 1)的鏈表包含所有元素；
(4) 如果一個(gè)元素出現(xiàn)在Level i 的鏈表中，則它在Level i 之下的鏈表也都會(huì)出現(xiàn)；
(5) 每個(gè)節(jié)點(diǎn)包含兩個(gè)指針，一個(gè)指向同一鏈表中的下一個(gè)元素，一個(gè)指向下面一層的元素。
平民版跳表實(shí)現(xiàn)，若果你對(duì)跳表實(shí)現(xiàn)完全沒(méi)概念，可一觀
skip_list_test.go
packageskip_list_2import("testing")funcTestNewSkipList(t*testing.T){root:=NewLinkedList()data:=[]int{1,3,4,5,7,8,9,10,13,16,17,18}fori:=rangedata{root.InsertToTail(data[i])}skipList:=NewSkipList(4,root)skipList.Dump()skipList.search(1)skipList.insert(6)skipList.Dump()skipList.search(6)}
skip_list.go
packageskip_list_2import("fmt""math/rand")typeSkipListstruct{maxHeightintroot*LinkedList? ? indexList[]*LinkedList? ? stepint}funcNewSkipList(stepint,root*LinkedList)*SkipList{skipList:=&SkipList{root:root,step:step}skipList.createIndexList()returnskipList}func(sl*SkipList)isEmpty()bool{returnsl.root.length==0}func(sl*SkipList)createIndexList(){sl.indexList=make([]*LinkedList,0,0)varcurrentList*LinkedListfor{ifcurrentList==nil{currentList=sl.root}tmpList:=NewLinkedList()fori:=0;i<currentList.length;i+=sl.step{ifi==0{node:=currentList.FindByIndex(i)newNode:=tmpList.InsertToTail(node.value)newNode.down=node}else{node:=currentList.FindByIndex(i)newNode:=tmpList.InsertToTail(node.value)newNode.down=node}}iftmpList.length==1{// 只有一個(gè)索引，沒(méi)有什么意義break}sl.indexList=append(sl.indexList,tmpList)fmt.Println(tmpList)iftmpList.length==2{//最頂層只有三個(gè)索引break}else{currentList=tmpList}}}func(sl*SkipList)search(vint)*Node{fmt.Println("----- search start-----",v)list:=sl.indexList[len(sl.indexList)-1]vartNode*Node? ? tNode=list.FindByIndex(0)fmt.Println(tNode)for{varnodeL,nodeR*Node? ? ? ? nodeL=tNode? ? ? ? nodeR=tNode.next? ? ? ? fmt.Printf("左節(jié)點(diǎn)%v -->> 右節(jié)點(diǎn)%v\n",nodeL,nodeR)ifnodeR==nil{// 當(dāng)前層， nodeL 就是最后一個(gè)點(diǎn)tNode=nodeL.down}elseifv>=nodeL.value&&v<nodeR.value{tNode=nodeL.down}elseifv>=nodeR.value{tNode=nodeR.down}iftNode.down==nil{break}iftNode.next==nil{tNode=tNode.down}}fmt.Printf("原始節(jié)點(diǎn)%v\n",tNode)for{iftNode==nil||tNode.value>v{fmt.Println("找不到對(duì)應(yīng)的node")returnnil}iftNode.value==v{fmt.Println("找到了node",tNode)returntNode}fmt.Println("繼續(xù)查找node")tNode=tNode.next}}func(sl*SkipList)searchPer(vint)*Node{fmt.Println("----- searchPer start-----",v)list:=sl.indexList[len(sl.indexList)-1]vartNode*Node? ? tNode=list.FindByIndex(0)fmt.Println(tNode)for{varnodeL,nodeR*Node? ? ? ? nodeL=tNode? ? ? ? nodeR=tNode.next? ? ? ? fmt.Printf("左節(jié)點(diǎn)%v -->> 右節(jié)點(diǎn)%v\n",nodeL,nodeR)ifnodeR==nil{// 當(dāng)前層， nodeL 就是最后一個(gè)點(diǎn)tNode=nodeL.down}elseifv>=nodeL.value&&v<nodeR.value{tNode=nodeL.down}elseifv>=nodeR.value{tNode=nodeR.down}iftNode.down==nil{break}iftNode.next==nil{tNode=tNode.down}}fmt.Printf("原始節(jié)點(diǎn)%v\n",tNode)for{iftNode.next==nil{fmt.Println("找到了要插入的節(jié)點(diǎn)",tNode)returntNode}iftNode.next.value>=v{fmt.Println("找到了要插入的節(jié)點(diǎn)",tNode)returntNode}fmt.Println("繼續(xù)查找node")tNode=tNode.next}}func(sl*SkipList)insert(vint)bool{fmt.Println("----- insert start-----",v)node:=sl.searchPer(v)tmp:=node.next? ? node.next=NewNode(v)node.next.next=tmp//插入完成后 更新索引level:=rand.Intn(len(sl.indexList))fmt.Println("隨機(jī)索引層為: ",level)insertNode:=NewNode(v)forl:=level;l>=0;l--{// 確認(rèn)插入位置的node:=sl.indexList[l].FindByIndex(0)vartarget*Nodefor{nodeL:=node? ? ? ? ? ? nodeR:=node.nextifnodeR==nil{target=nodeLbreak}elseifv>=nodeL.value&&v<nodeR.value{target=nodeLbreak}elseifv>=nodeR.value{target=nodeRbreak}node=node.next}tmp:=target.next? ? ? ? target.next=insertNode? ? ? ? insertNode.next=tmp? ? ? ? newInsertNode:=NewNode(v)insertNode.down=newInsertNode? ? ? ? insertNode=newInsertNode}returntrue}func(sl*SkipList)Dump(){fmt.Println("----- dump start-----")fori:=len(sl.indexList)-1;i>=0;i--{sl.indexList[i].Print()}sl.root.Print()fmt.Println("----- dump end-----")}
linked_list.go
packageskip_list_2import"fmt"typeNodestruct{next*Node? ? valueintdown*Node}typeLinkedListstruct{head*Node? ? lengthint}funcNewNode(vint)*Node{return&Node{nil,v,nil}}func(this*Node)GetNext()*Node{returnthis.next}func(this*Node)GetValue()int{returnthis.value}funcNewLinkedList()*LinkedList{return&LinkedList{NewNode(0),0}}//在某個(gè)節(jié)點(diǎn)后面插入節(jié)點(diǎn)func(this*LinkedList)InsertAfter(p*Node,vint)*Node{ifnil==p{returnnil}newNode:=NewNode(v)oldNext:=p.next? ? p.next=newNode? ? newNode.next=oldNext? ? this.length++returnnewNode}//在某個(gè)節(jié)點(diǎn)前面插入節(jié)點(diǎn)func(this*LinkedList)InsertBefore(p*Node,vint)bool{ifnil==p||p==this.head{returnfalse}cur:=this.head.next? ? pre:=this.headfornil!=cur{ifcur==p{break}pre=cur? ? ? ? cur=cur.next}ifnil==cur{returnfalse}newNode:=NewNode(v)pre.next=newNode? ? newNode.next=cur? ? this.length++returntrue}//在鏈表頭部插入節(jié)點(diǎn)func(this*LinkedList)InsertToHead(vint)*Node{returnthis.InsertAfter(this.head,v)}//在鏈表尾部插入節(jié)點(diǎn)func(this*LinkedList)InsertToTail(vint)*Node{cur:=this.headfornil!=cur.next{cur=cur.next}returnthis.InsertAfter(cur,v)}//通過(guò)索引查找節(jié)點(diǎn)func(this*LinkedList)FindByIndex(indexint)*Node{ifindex>=this.length{returnnil}cur:=this.head.nextvariint=0for;i<index;i++{cur=cur.next}returncur}//刪除傳入的節(jié)點(diǎn)func(this*LinkedList)DeleteNode(p*Node)bool{ifnil==p{returnfalse}cur:=this.head.next? ? pre:=this.headfornil!=cur{ifcur==p{break}pre=cur? ? ? ? cur=cur.next}ifnil==cur{returnfalse}pre.next=p.next? ? p=nilthis.length--returntrue}//打印鏈表func(this*LinkedList)Print(){cur:=this.head.next? ? format:=""fornil!=cur{format+=fmt.Sprintf("%+v",cur.GetValue())cur=cur.nextifnil!=cur{format+="->"}}fmt.Println(format)}/*
單鏈表反轉(zhuǎn)
時(shí)間復(fù)雜度：O(N)
*/func(this*LinkedList)Reverse(){ifnil==this.head||nil==this.head.next||nil==this.head.next.next{return}varpre*Node=nilcur:=this.head.nextfornil!=cur{tmp:=cur.next? ? ? ? cur.next=pre? ? ? ? pre=cur? ? ? ? cur=tmp}this.head.next=pre}/*
判斷單鏈表是否有環(huán)
*/func(this*LinkedList)HasCycle()bool{ifnil!=this.head{slow:=this.head? ? ? ? fast:=this.headfornil!=fast&&nil!=fast.next{slow=slow.next? ? ? ? ? ? fast=fast.next.nextifslow==fast{returntrue}}}returnfalse}/*
刪除倒數(shù)第N個(gè)節(jié)點(diǎn)
*/func(this*LinkedList)DeleteBottomN(nint){ifn<=0||nil==this.head||nil==this.head.next{return}fast:=this.headfori:=1;i<=n&&fast!=nil;i++{fast=fast.next}ifnil==fast{return}slow:=this.headfornil!=fast.next{slow=slow.next? ? ? ? fast=fast.next}slow.next=slow.next.next}/*
獲取中間節(jié)點(diǎn)
*/func(this*LinkedList)FindMiddleNode()*Node{ifnil==this.head||nil==this.head.next{returnnil}ifnil==this.head.next.next{returnthis.head.next}slow,fast:=this.head,this.headfornil!=fast&&nil!=fast.next{slow=slow.next? ? ? ? fast=fast.next.next}returnslow}funcmain(){list:=NewLinkedList()list.InsertToTail(2)list.InsertToHead(1)list.InsertToTail(3)list.InsertToTail(4)list.Reverse()list.Print()iflist.HasCycle(){fmt.Println("has cycle")}}
1人點(diǎn)贊
作者：尼桑麻
鏈接：http://www.itdecent.cn/p/6855c228d2f2
來(lái)源：簡(jiǎn)書(shū)
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
