跳表

作者: 我帅不 | 来源:发表于2019-12-25 00:03 被阅读0次

    跳表的定义

    跳表(SkipList):增加了向前指针的链表叫做跳表。跳表全称叫做跳跃表,简称跳表。跳表是一个随机化的数据结构,实质是一种可以进行近似二分查找有序链表。跳表在原有的有序链表上增加了多级索引,通过索引来实现快速查询。跳表不仅能提高搜索性能,同时也可以提高插入和删除操作的性能。

    跳表的详解

    有序原始链表

    对于一个单链表来说,即使链表中的数据是有序的,如果我们想要查找某个数据,也必须从头到尾的遍历链表,很显然这种查找效率是十分低效的,时间复杂度为O(n)

    那么我们如何提高查找效率呢?我们可以对链表建立一级“索引”,每两个结点提取一个结点到上一级,我们把抽取出来的那一级叫做索引或者索引层,如下图所示,我建立了两级索引,down表示down指针。

    image.png

    假设我们现在要查找值为16的这个结点。我们可以先在索引层遍历,当遍历索引层中值为13的时候,通过值为13的结点的指针域发现下一个结点值为17,因为链表本身有序,所以值为16的结点肯定在13和17这两个结点之间。然后我们通过索引层结点的down指针,下降到原始链表这一层,继续往后遍历查找。这个时候我们只需要遍历2个结点(值为13和16的结点),就可以找到值等于16的这个结点了。如果使用原来的链表方式进行查找值为16的结点,则需要遍历10个结点才能找到,而现在只需要遍历7个结点即可,从而提高了查找效率。

    那么我们可以由此得到启发,和上面建立第一级索引的方式相似,在第一级索引的基础上,每两个一级索引结点就抽到一个结点到第二级索引中。再来查找值为16的结点,只需要遍历6个结点即可,从而进一步提高了查找效率。

    跳表的时间复杂度

    单链表的查找时间复杂度为:O(n),

    下面分析下跳表这种数据结构的查找时间复杂度:

    我们首先考虑这样一个问题,如果链表里有n个结点,那么会有多少级索引呢?按照上面讲的,每两个结点都会抽出一个结点作为上一级索引的结点。那么第一级索引的个数大约就是n/2,第二级的索引大约就是n/4,第三级的索引就是n/8,依次类推,也就是说,第k级索引的结点个数是第k-1级索引的结点个数的1/2,那么第k级的索引结点个数为n/(2k)。

    、】

    `

    假设索引有h级,最高级的索引有2个结点,通过上面的公式,我们可以得到,从而可得:h =log2n-1。如果包含原始链表这一层,整个跳表的高度就是。我们在跳表中查找某个数据的时候,如果每一层都要遍历m个结点,那么在跳表中查询一个数据的时间复杂度就为O(m*logn)。

    其实根据前面的分析,我们不难得出m=3,即每一级索引都最多只需要遍历3个结点,分析如下:

    时间复杂度分析

    如上图所示,假如我们要查找的数据是x,在第k级索引中,我们遍历到y结点之后,发现x大于y,小于y后面的结点z。所以我们通过y的down指针,从第k级索引下降到第k-1级索引。在第k-1级索引中,y和z之间只有3个结点(包含y和z)。所以,我们在k-1级索引中最多需要遍历3个结点,以此类推,每一级索引都最多只需要遍历3个结点。

    因此,m=3,所以跳表查找任意数据的时间复杂度为O(logn),这个查找的时间复杂度和二分查找是一样的,但是我们却是基于单链表这种数据结构实现的。不过,天下没有免费的午餐,这种查找效率的提升是建立在很多级索引之上的,即空间换时间的思想。其具体空间复杂度见下文详解。

    跳表的空间复杂度

    比起单纯的单链表,跳表就需要额外的存储空间去存储多级索引。假设原始链表的大小为n,那么第一级索引大约有n/2个结点,第二级索引大约有4/n个结点,依次类推,每上升一级索引结点的个数就减少一半,直到剩下最后2个结点,如下图所示,其实就是一个等比数列。

    空间复杂度

    这几级索引结点总和为:n/2 + n/4 + n/8 + ... + 8 + 4 + 2 = n - 2。所以跳表的空间复杂度为O(n)。也就是说如果将包含n个结点的单链表构造成跳表,我们需要额外再用接近n个结点的存储空间。

    其实从上面的分析,我们利用空间换时间的思想,已经把时间压缩到了极致,因为每一级每两个索引结点就有一个会被抽到上一级的索引结点中,所以此时跳表所需要的额外内存空间最多,即空间复杂度最高。其实我们可以通过改变抽取结点的间距来降低跳表的空间复杂度,在其时间复杂度和空间复杂度方面取一个综合性能,当然也要看具体情况,如果内存空间足够,那就可以选择最小的结点间距,即每两个索引结点抽取一个结点到上一级索引中。如果想降低跳表的空间复杂度,则可以选择每三个或者每五个结点,抽取一个结点到上级索引中。

    image.png

    如上图所示,每三个结点抽取一个结点到上一级索引中,则第一级需要大约n/3个结点,第二级索引大约需要n/9个结点。每往上一级,索引的结点个数就除以3,为了方便计算,我们假设最高一级的索引结点个数为1,则可以得到一个等比数列,去下图所示:

    image.png

    通过等比数列的求和公式,总的索引结点大约是:n/3 + n /9 + n/27 + ... + 9 + 3 + 1 = n/2。尽管空间复杂度还是O(n),但是比之前的每两个结点抽一个结点的索引构建方法,可以减少了一半的索引结点存储空间。

    实际上,在软件开发中,我们不必太在意索引占用的额外空间。在讲数据结构的时候,我们习惯性地把要处理的数据看成整数,但是在实际的软件开发中,原始链表中存储的有可能是很大的对象,而索引结点只需要存储关键值和几个指针,并不需要存储对象,所以当对象比索引结点大很多时,那索引占用的额外空间就可以忽略了。

    5、跳表的插入

    跳表插入的时间复杂度为:O(logn),支持高效的动态插入。

    在单链表中,一旦定位好要插入的位置,插入结点的时间复杂度是很低的,就是O(1)。但是为了保证原始链表中数据的有序性,我们需要先找到要插入的位置,这个查找的操作就会比较耗时。

    对于纯粹的单链表,需要遍历每个结点,来找到插入的位置。但是对于跳表来说,查找的时间复杂度为O(logn),所以这里查找某个数据应该插入的位置的时间复杂度也是O(logn),如下图所示:

    image.png

    6、跳表的删除

    跳表的删除操作时间复杂度为:O(logn),支持动态的删除。

    在跳表中删除某个结点时,如果这个结点在索引中也出现了,我们除了要删除原始链表中的结点,还要删除索引中的。因为单链表中的删除操作需要拿到删除结点的前驱结点,然后再通过指针操作完成删除。所以在查找要删除的结点的时候,一定要获取前驱结点(双向链表除外)。因此跳表的删除操作时间复杂度即为O(logn)。

    7、跳表索引动态更新

    当我们不断地往跳表中插入数据时,我们如果不更新索引,就有可能出现某2个索引节点之间的数据非常多的情况,在极端情况下,跳表还会退化成单链表,如下图所示:

    image.png

    作为一种动态数据结构,我们需要某种手段来维护索引与原始链表大小之间的平衡,也就是说,如果链表中的结点多了,索引结点就相应地增加一些,避免复杂度退化,以及查找、插入和删除操作性能的下降。

    如果你了解红黑树、AVL树这样的平衡二叉树,你就会知道它们是通过左右旋的方式保持左右子树的大小平衡,而跳表是通过随机函数来维护“平衡性”。

    当我们往跳表中插入数据的时候,我们可以通过一个随机函数,来决定这个结点插入到哪几级索引层中,比如随机函数生成了值K,那我们就将这个结点添加到第一级到第K级这个K级索引中。如下图中要插入数据为6,K=2的例子:

    image.png

    随机函数的选择是非常有讲究的,从概率上讲,能够保证跳表的索引大小和数据大小平衡性,不至于性能的过度退化。至于随机函数的选择,见下面的代码实现过程,而且实现过程并不是重点,掌握思想即可。

    8、跳表的性质

    (1) 由很多层结构组成,level是通过一定的概率随机产生的;

    (2) 每一层都是一个有序的链表,默认是升序 ;

    (3) 最底层(Level 1)的链表包含所有元素;

    (4) 如果一个元素出现在Level i 的链表中,则它在Level i 之下的链表也都会出现;

    (5) 每个节点包含两个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素。

    平民版跳表实现,若果你对跳表实现完全没概念,可一观

    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{// 只有一个索引,没有什么意义break}sl.indexList=append(sl.indexList,tmpList)fmt.Println(tmpList)iftmpList.length==2{//最顶层只有三个索引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("左节点%v -->> 右节点%v\n",nodeL,nodeR)ifnodeR==nil{// 当前层, nodeL 就是最后一个点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("原始节点%v\n",tNode)for{iftNode==nil||tNode.value>v{fmt.Println("找不到对应的node")returnnil}iftNode.value==v{fmt.Println("找到了node",tNode)returntNode}fmt.Println("继续查找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("左节点%v -->> 右节点%v\n",nodeL,nodeR)ifnodeR==nil{// 当前层, nodeL 就是最后一个点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("原始节点%v\n",tNode)for{iftNode.next==nil{fmt.Println("找到了要插入的节点",tNode)returntNode}iftNode.next.value>=v{fmt.Println("找到了要插入的节点",tNode)returntNode}fmt.Println("继续查找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("随机索引层为: ",level)insertNode:=NewNode(v)forl:=level;l>=0;l--{// 确认插入位置的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}}//在某个节点后面插入节点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}//在某个节点前面插入节点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}//在链表头部插入节点func(this*LinkedList)InsertToHead(vint)*Node{returnthis.InsertAfter(this.head,v)}//在链表尾部插入节点func(this*LinkedList)InsertToTail(vint)*Node{cur:=this.headfornil!=cur.next{cur=cur.next}returnthis.InsertAfter(cur,v)}//通过索引查找节点func(this*LinkedList)FindByIndex(indexint)*Node{ifindex>=this.length{returnnil}cur:=this.head.nextvariint=0for;i<index;i++{cur=cur.next}returncur}//删除传入的节点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)}/*

    单链表反转

    时间复杂度: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}/*

    判断单链表是否有环

    */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}/*

    删除倒数第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}/*

    获取中间节点

    */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人点赞

    数据结构与算法

    作者:尼桑麻

    链接:https://www.jianshu.com/p/6855c228d2f2

    来源:简书

    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    相关文章

      网友评论

          本文标题:跳表

          本文链接:https://www.haomeiwen.com/subject/kfeqoctx.html