有一个类似跳表的数据结构,跳转表 数据结构

　　虽然二分搜索法在n个元素的有序阵列中的时间复杂度是log(n)，但是在n个有序元素的列表中的时间复杂度是O(n)。为了提高有序列表的搜索性能，可以向所有或某些节点添加额外的指针。搜索时，可以通过这些指针跳过链表中的一些节点，不需要从左到右连续查看所有节点。带有附加前向指针的链表称为跳转表。它使用随机技术来决定链表中的哪些节点应该添加前向指针以及添加多少个指针。基于这种随机技术，查找、插入和删除跳转表的平均时间复杂度为O(logn)。但是，最坏的情况还是O(n)。

　　跳表的特点和优点我们知道，平衡树的搜索效率是log(n)，但是每次插入或删除都可能破坏平衡，所以需要重建平衡，产生额外的旋转操作。但跳表采用概率平衡技术，而不是强制平衡，因此比传统的平衡树算法插入和删除节点的效率更高。

　　跳转表由一个原始的单链表和一些索引链表组成。这些索引列表是在单个列表中插入新元素时随机生成的，插入节点的索引列表节点数称为索引列表的层数。由于随机技术，不同单链表的索引可能有0层或更多层。同级索引节点通过指针从前到后形成有序链表。级别越高，这个有序链表中的节点就越少。

　　以下是一个典型的跳转列表：

　　跳转表的实现跳转表的节点和普通链表一样，跳转表也需要定义一个节点。因为跳转表用于替换平衡树，所以我们还需要定义键值对。另外，由于跳转表中的每个节点都需要指向一个或多个后续节点，所以这里的下一个指针需要定义为一个数组，这个数组的长度由我们随机生成的级别决定。节点定义如下：

　　模板类型名K，类型名V

　　结构节点

　　{

　　k键；

　　v值；

　　int级别；

　　节点* * nexts

　　Node()=默认；

　　Node(const K k，const V v，int lv) : key(k)，value(v)，level(lv)

　　{

　　nexts=新节点K，V *[level 1]；

　　memset(nexts，0，sizeof(sizeof(节点K，V *) *(级别1)))；

　　}

　　~节点()

　　{

　　删除[]个nexts

　　}

　　};这里，让我们把重点放在level和nexts指针上。Level是随机算法生成的层数。如果是0，就像普通的单链表一样，只有一个节点指向后面的节点，否则会有多个节点。至于这些节点指向哪些节点，则需要根据插入节点的级别和寻找插入位置时走过的索引节点来确定。这部分在插入部分也有介绍。

　　随机算法的实现因为每个随机时间的概率是1/2，所以我们只需要一个能生成0和1的随机算法。这里借助c 11推出的随机引擎，可以实现如下：

　　STD:uniform _ int _ distribution int _ int _ distribute(0，1)；

　　std:默认_随机_引擎_默认_随机_引擎；

　　_ default _ random _ engine(_ int _ distribute)；//_default_random_engine每次调用都会以相同的概率返回0或1跳表。假设已经有一个长度为N的链表，如何建立索引？因为我们希望跳转表具有二分搜索法算法的效率，当我们要确定是否在某个节点建立索引时，它的概率是1/2，在那里建立第二个索引的概率是1/4，以此类推。因为链表的长度是N，所以最大层高是log(N)。首先，我们创建一个长度为k=log(N) 1的数组，指向链表中的k个节点。我们称这个数组为头数组。开始时，头数组的所有元素都为空。然后我们开始遍历单链表。当我们插入第一个元素时，我们需要为该元素生成一个级别。因为是随机算法，level可能大于k，所以我们需要限制level的最大值。由于插入第一个元素时，节点的后面是空的，所以实际上level=0，也就是nexts数组的长度是1。我们用一个marker _level来记录当前整个跳表中所有元素的最大级别(除了头)。当我们再次插入新元素时，如果新元素的级别最大值大于_level，我们只能取_level 1。这是为了让等级有序增加，避免不必要的空间浪费。

　　从上面的过程可以看出，我们的跳转表需要一个header数组指向后续的索引，一个level整数表示当前所有节点的最大层数，一个max_level限制最高层并初始化header的个数。另外，因为C的随机引擎是有状态的，所以我们也需要把这部分字段放在跳转表的定义里。为了获得时间复杂度为O(1)的跳转表元素个数，我们用_size字段来表示。为了用O(1)的时间复杂度判断一个元素是否在跳表的区间内，我们还需要用一个尾节点指向跳表的最后一个元素。跳转表还需要最基本的插入、删除和搜索操作，所以我们的跳转表结构暂时如下：

　　模板类型名K，类型名V

　　类别SkipList

　　{

　　公共：

　　skip list(int max _ level)；

　　//插入一个键值对。如果该键已经存在，则更新该值，然后返回false。如果插入成功，则返回true。

　　bool insert(const K k，const V V)；

　　//找出键是否存在，有返回节点的指针。

　　节点K，V * find(const K K)const；

　　bool erase(const K K)；

　　int size()const；

　　私人：

　　int generate _ level()const；

　　私人：

　　int _ max _ level { 0 }；//跳转表允许的最大级别

　　int _ cur _ level { 0 }；//跳转表的当前最大级别

　　int _ size { 0 }；

　　STD:uniform _ int _ distribution int _ int _ distribute(0，1)；

　　可变STD:default _ random _ engine _ default _ random _ engine；

　　节点K，V * _ header { nullptr }；//链表的头节点

　　节点K，V * _ tail { nullptr }；//链表的尾节点

　　};跳表的初始化在初始化跳表时，我们给出一个max_level来指定跳表允许的最大层数。一般我们允许的跳转表最大层数k应该与跳转表的元素数n成对数，即k=log(n) 1。只有这样才能达到log(n)的搜索效率。因此，当我们创建跳转表时，我们需要估计跳转表需要存储多少元素。

　　模板类型名K，类型名V

　　SkipList K，V:skip list(int max _ level):_ max _ level(max _ level)

　　{

　　//初始化标头。标头不存储特定的数据，因此每次插入时都会将其插入到标头的右侧。

　　_header=新节点K，V *[_ max _ level 1]；

　　memset(_header，0，sizeof(sizeof(Node K，V *)*(_ max _ level 1)))；

　　}跳转表的插入跳转表的插入遵循以下原则：

　　如果键值已经存在，只需修改该值并返回false。如果键不存在，找到插入点，创建一个新的跳转表节点，然后插入节点，返回true。插入步骤如下：

　　从node=header开始搜索，从i=_cur_level开始搜索，从前到后搜索，因为_cur_level是目前最高的级别。空指针一直向上是没有意义的。如果nexts[i]- key等于要插入的键，则更新该值并返回false。如果nexts[i]- key小于要插入的键，则node=node- nexts[i]，即把节点指向当前层的下一个节点。如果nexts[i]- key大于要插入的key，在I-之后重复第一步和第二步，即找到下一层，直到i=0，找到比要插入的key大的key，或者找到链表的结尾，退出循环，在节点后面插入要插入的元素，因为按照上面的步骤，节点要么是头节点，要么node- key小于要插入的键，而node- nexts[i]- key大于要插入的键。由于插入了一个新节点，而新节点也有自己的级别，假设其值为k，即有一个长度为k的nexts数组，我们需要像单链表插入一样将前一个元素指向新插入的元素，然后将新元素指向其前任节点原来的下一个节点。那么这些nexts指针指向谁，谁应该指向新节点呢？根据跳表的定义，我们需要将同级的前k个指针指向新节点，然后将新节点的k个nexts指针指向上一个节点的nexts个节点。在这里，我们只需要找到nexts指针的前任节点，因为前任节点存储nexts信息。其实前任节点就是我之前的节点——每次，我们只需要在遍历的时候存储这些节点，然后在创建新节点的时候再连接。应该存储多少个这样的前驱节点？答案是_cur_level 1，因为我们需要从_cur_level开始到0级结束，而_cur_level的最大值是_max_level。因此，为了避免每次都创建一个临时数组来存储这些信息，我们在跳表中维护了一个长度为_max_level 1的_lasts数组，用于存储第一级的最后一个前任节点.

　　为什么node是那个层的前驱节点？

　　假设在开始的时候，node=header，i=_cur_level，它的nexts[i]代表的是header中第I层的节点。如果这个节点的键大于要插入的键，那么_last[i]=node，存储小于要插入的键的I级中的最后一个节点，然后I-，然后开始索引下一级的节点。依此类推，直到i=0。此时，_lasts[i]存储要插入节点的0~_cur_level层的前驱节点。

　　新节点的级别

　　由于新节点级别的取值范围为0~min(_cur_level 1，_max_level)，因此需要根据以下条件改变前一个节点和后一个节点的方向：

　　如果级别小于等于_cur_level，那么直接设置新节点的nexts[i]=_lasts[i]- nexts[i]就足够了，即把I级的节点指向I级的后续节点，然后point _lasts[i]- nexts[i]指向新节点。如果level大于_cur_level，那么level只能取_cur_level 1，然后除了第一步，还需要将header[_cur_level 1]指向新节点。指向新节点的nullptr的_cur_level 1层的插入代码引入_lasts如下：

　　模板类型名K，类型名V

　　bool SkipList K，V :insert(const K k，const V v)

　　{

　　节点K，V * cur _ node=_ header

　　int i=_ cur _ level

　　memset(_lasts，0，sizeof(sizeof(Node K，V *)*(_ max _ level 1)))；

　　while (i=0)

　　{

　　while (cur_node- nexts[i]！=nullptr)

　　{

　　if (cur_node- nexts[i]- key k)

　　{

　　cur _ node=cur _ node-nexts[I]；

　　}

　　else if(cur _ node-nexts[I]-key==k)

　　{

　　cur _ node-nexts[I]-value=v；

　　返回false

　　}

　　}

　　_ lasts[I]=cur _ node；//保存第I层小于k的最后一个元素

　　I-；

　　}

　　int node _ level=generate _ level()；

　　//如果生成节点的级别大于当前级别，则只增加一层。

　　//这里我们将其保存在_lasts中，以便后续统一处理。

　　if(节点级别当前级别)

　　{

　　node _ level=_ cur _ level

　　_ lasts[node _ level]=_ header；

　　}

　　节点K，V *node=新节点K，V (k，V，Node _ level)；

　　//在_lasts[i]之后插入节点

　　for(int I=0；i=节点级别；我)

　　{

　　node-nexts[I]=_ lasts[I]-nexts[I]；//将新创建节点的前向节点指向前一个节点的后续节点。

　　_ lasts[I]-nexts[I]=node；

　　}

　　//更新尾巴节点

　　if (node- nexts[0]==nullptr)

　　{

　　_tail=节点；

　　}

　　_大小

　　返回真实的

　　}生成水平的代码：

　　模板类型名k，类型名V

　　int SkipList K，V :generate_level() const

　　{

　　int level=0；

　　while(level _ max _ level _ default _ random _ engine(_ int _ distribute)//使用0、1随机生成器，为一则增加水平

　　{

　　水平；

　　}

　　回报水平；

　　}跳表的查找操作由于已经建立好跳表，要查找一个键则只需要先从_当前级别层开始查找，步骤如下：

　　从ndoe=header，i=_cur_level层开始往后查找，如果nexts[_i]- key==key，返回nexts[i]即可如果nexts[i]- key key，则我，开始找下一层如果i==0，并且nexts[i]==nullptr或者nexts[i]- key key，则表示跳表中不存在该钥匙代码如下：

　　模板类型名k，类型名V

　　节点K，V *SkipList K，V :find(const K k)const

　　{

　　if (size()==0)

　　{

　　返回指针

　　}

　　//如果要找的元素小于第一个元素，或者大于最后一个元素，则超出范围，直接返回错误的

　　if(k _ header-nexts[0]-key k _ tail-nexts[0]-key)

　　{

　　返回错误的

　　}

　　int i=_ cur _ level

　　节点k，V * node=_ header

　　while (i=0)

　　{

　　while (node- nexts[i]！=nullptr)

　　{

　　if (node- nexts[i]- key k)

　　{

　　node=node-nexts[I]；

　　}

　　else if (node- nexts[i]- key==k)

　　{

　　返回节点；

　　}

　　else if(I==0 node-nexts[I]-key k)//已经找到最底层，但是下一个元素已经大于要找的键了，说明不存在

　　{

　　返回指针

　　}

　　}

　　I-；

　　}

　　返回指针

　　}跳表的删除操作跳表的删除需要先找到要删除的节点，然后使用查找过程中的前驱节点将要删除节点的后续节点链接起来，实现和插入操作大致相同，代码如下：

　　模板类型名k，类型名V

　　bool SkipList K，V :erase(const K k)

　　{

　　if (size()==0)

　　{

　　返回错误的

　　}

　　//如果要找的元素小于第一个元素，或者大于最后一个元素，则超出范围，直接返回错误的

　　if(k _ header-nexts[0]-key k _ tail-nexts[0]-key)

　　{

　　返回错误的

　　}

　　int i=_ cur _ level

　　节点k，V * node=_ header

　　memset(_lasts，0，sizeof(Node K，V *)*(_ max _ level 1))；

　　while (i=0)

　　{

　　while (node- nexts[i]！=nullptr)

　　{

　　if (node- nexts[i]- key k)

　　{

　　node=node-nexts[I]；

　　}

　　else if (node- nexts[i]- key==k)

　　{

　　打破；

　　}

　　else if(I==0 node-nexts[I]-key k)//已经找到最底层，但是下一个元素已经大于要找的键了，说明不存在

　　{

　　返回错误的

　　}

　　}

　　_ lasts[I]=node；

　　I-；

　　}

　　//按照逻辑，永远不会走这个分支。在进入正在…循环前k一定是在现有区间中的

　　断言(I=0)；

　　assert(node- nexts[i]！=nullptr)；

　　Node K，V * to _ delete=node-nexts[I]；

　　//将要删除节点的前驱节点的向前[我]指向要删除的后继节点，只需要处理至_删除级别层

　　for(int I=0；I=to _ delete-level；我)

　　{

　　_ lasts[I]-nexts[I]=to _ delete-nexts[I]；

　　}

　　//如果要删除的节点是尾巴节点

　　if (to_delete- nexts[0]==nullptr)

　　{

　　_ tail=_ lasts[0]；

　　}

　　_ size-；

　　删除收件人_删除

　　返回真实的

　　}完整代码说明：这里的代码是个人为了学习跳表结构写的练习代码，不保证代码没有逻辑上的错误，如果使用该代码造成的不良后果和本人没有任何关系。

　　#杂注一次

　　#包括随机

　　#包括卡塞特

　　#包括字符串

　　模板类型名k，类型名V

　　结构节点

　　{

　　k键；

　　v值；

　　（同Internationalorganizations）国际组织级别；

　　节点* *下一步

　　Node()=默认；

　　Node(const K k，const V v，int lv) : key(k)，value(v)，level(lv)

　　{

　　nexts=新节点k，V *[一级]；

　　memset(nexts，0，sizeof(sizeof(节点k，V *) *(级别1)));

　　}

　　~节点()

　　{

　　删除[]个下一步

　　}

　　};

　　模板类型名k，类型名V

　　类别跳跃表

　　{

　　公共：

　　跳过列表(int max _ level)；

　　//插入一个键值对，如果已经存在该键更新价值然后返回假的，插入成功返回真实的

　　bool insert(const K k，const V V)；

　　//查找键是否存在，存在返回该节点指针

　　节点K，V * find(const K K)const；

　　bool erase(const K K)；

　　int size()const；

　　私人：

　　int generate _ level()const；

　　私人：

　　int _ max _ level { 20 }；//跳表允许的最大水平

　　int _ cur _ level { 0 }；//跳表的当前最大水平

　　int _ size { 0 }；

　　STD:uniform _ int _ distribution int _ int _ distribute(0，1)；

　　可变STD:默认_随机_引擎_默认_随机_引擎；

　　节点k，V * _ header { nullptr }；//链表的头节点

　　节点k，V * _ tail { nullptr }；//链表的尾节点

　　节点k，V * _ lasts { nullptr }；//用于遍历链表的时候存放每一层的最后一个节点

　　};

　　模板类型名k，类型名V

　　bool SkipList K，V :erase(const K k)

　　{

　　if (size()==0)

　　{

　　返回错误的

　　}

　　//如果要找的元素小于第一个元素，或者大于最后一个元素，则超出范围，直接返回错误的

　　if(k _ header-nexts[0]-key k _ tail-nexts[0]-key)

　　{

　　返回错误的

　　}

　　int i=_ cur _ level

　　节点k，V * node=_ header

　　memset(_lasts，0，sizeof(Node K，V *)*(_ max _ level 1))；

　　while (i=0)

　　{

　　while (node- nexts[i]！=nullptr)

　　{

　　if (node- nexts[i]- key k)

　　{

　　node=node-nexts[I]；

　　}

　　else if (node- nexts[i]- key==k)

　　{

　　打破；

　　}

　　else if(I==0 node-nexts[I]-key k)//已经找到最底层，但是下一个元素已经大于要找的键了，说明不存在

　　{

　　返回错误的

　　}

　　}

　　_ lasts[I]=node；

　　I-；

　　}

　　//按照逻辑，永远不会走这个分支。在进入正在…循环前k一定是在现有区间中的

　　断言(I=0)；

　　assert(node- nexts[i]！=nullptr)；

　　Node K，V * to _ delete=node-nexts[I]；

　　//将要删除节点的前驱节点的向前[我]指向要删除的后继节点，只需要处理至_删除级别层

　　for(int I=0；I=to _ delete-level；我)

　　{

　　_ lasts[I]-nexts[I]=to _ delete-nexts[I]；

　　}

　　//如果要删除的节点是尾巴节点

　　if (to_delete- nexts[0]==nullptr)

　　{

　　_ tail=_ lasts[0]；

　　}

　　_ size-；

　　删除收件人_删除

　　返回真实的

　　}

　　模板类型名k，类型名V

　　节点K，V *SkipList K，V :find(const K k)const

　　{

　　if (size()==0)

　　{

　　返回指针

　　}

　　//如果要找的元素小于第一个元素，或者大于最后一个元素，则超出范围，直接返回错误的

　　if(k _ header-nexts[0]-key k _ tail-nexts[0]-key)

　　{

　　返回错误的

　　}

　　int i=_ cur _ level

　　节点k，V * node=_ header

　　while (i=0)

　　{

　　while (node- nexts[i]！=nullptr)

　　{

　　if (node- nexts[i]- key k)

　　{

　　node=node-nexts[I]；

　　}

　　else if (node- nexts[i]- key==k)

　　{

　　返回节点；

　　}

　　else if(I==0 node-nexts[I]-key k)//已经找到最底层，但是下一个元素已经大于要找的键了，说明不存在

　　{

　　返回指针

　　}

　　}

　　I-；

　　}

　　返回指针

　　}

　　模板类型名k，类型名V

　　SkipList K，V:skip list(int max _ level):_ max _ level(max _ level)

　　{

　　//初始化标题，标题不存放具体的数据，保证每次插入的时候都插入在页眉的右侧

　　_header=新节点k，V * p[_ max _ level 1]；

　　memset(_header，0，sizeof(sizeof(Node K，V *)*(_ max _ level 1)))；

　　//初始化持续，持续也不存放具体的数据，用于每次遍历的时候存放当前层的最后一个节点

　　_lasts=新节点k，V * p[_ max _ level 1]；

　　memset(_lasts，0，sizeof(sizeof(Node K，V *)*(_ max _ level 1)))；

　　}

　　模板类型名k，类型名V

　　bool SkipList K，V :insert(const K k，const V v)

　　{

　　节点k，V * cur _ node=_ header

　　int i=_ cur _ level

　　memset(_lasts，0，sizeof(sizeof(Node K，V *)*(_ max _ level 1)))；

　　while (i=0)

　　{

　　while (cur_node- nexts[i]！=nullptr)

　　{

　　if (cur_node- nexts[i]- key k)

　　{

　　cur _ node=cur _ node-nexts[I]；

　　}

　　else if(cur _ node-nexts[I]-key==k)

　　{

　　cur _ node-nexts[I]-value=v；

　　返回错误的

　　}

　　}

　　_ lasts[I]=cur _ node；//保存第我层的最后一个比k小的元素

　　I-；

　　}

　　int node _ level=generate _ level()；

　　//如果生成的节点的水平大于当前的水平，只新增一层

　　//这里我们把它保存在_持续时间中后续统一处理

　　如果(节点级别当前级别)

　　{

　　节点级别=_当前级别

　　_ lasts[node _ level]=_ header；

　　}

　　节点k，V *节点=新节点k，V (k，V，Node _ level)；

　　//将结节插入到_lasts[i]后面

　　for(int I=0；我=节点级别；我)

　　{

　　node-nexts[I]=_ lasts[I]-nexts[I]；//将新建节点的向前节点指向前驱节点的后续节点

　　_ lasts[I]-nexts[I]=node；

　　}

　　//更新尾巴节点

　　if (node- nexts[0]==nullptr)

　　{

　　_tail=节点；

　　}

　　_大小

　　返回真实的

　　}

　　模板类型名k，类型名V

　　int SkipList K，V :generate_level() const

　　{

　　int level=0；

　　while(level _ max _ level _ default _ random _ engine(_ int _ distribute)//使用0、1随机生成器，为一则增加水平

　　{

　　水平；

　　}

　　回报水平；

　　}

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。