用Python深入理解跳跃表原理及实现

最近看 Redis 的实现原理,其中讲到 Redis 中的有序数据结构是通过跳跃表来进行实现的。第一次听说跳跃表的概念,感到比较新奇,所以查了不少资料。其中,网上有部分文章是按照如下方式描述跳跃表的:

这种描述便于理解,很容易让人理解到跳跃表是建立了类似索引的东西,从而提高效率的。但是,这样描述给人的感觉是,数据有多份存储,每份数据有两个指针,指向下层数据的指针和指向右面数据的指针。然而实际并不是这样的,实际的数据结构如下:

即:并非由多份数据,而是每份数据有多层指针。

那么,什么是跳跃表,跳跃表有什么特点呢?

Skip lists are data structures that use probabilistic balancing rather than strictly enforced balancing. As a result, the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

从定义中可以看出,跳跃表是为了解决平衡树插入或者删除操作过于复杂而进行设计的。的确,平衡树在插入或者删除时,需要维持平衡而进行过多的操作,学过数据结构的同学想到平衡树、红黑树等都不寒而栗吧。而跳跃表则没有这种问题,采用了随机的思想简化了维持平衡的过程,而保持查找的时间复杂度依旧是O(log N)。

跳跃表有如下特点:

(1) 每个跳跃表由很多层结构组成;

(2) 每一层都是一个有序链表,且第一个节点是头节点;

(3) 最底层的有序链表包含所有节点;

(4) 每个节点可能有多个指针,这与节点所包含的层数有关;

(5) 跳跃表的查找、插入、删除的时间复杂度均为O(log N)。

从上面的结构也可以看出,跳跃表的核心思想就是,每一个节点既包含指向下一个节点的指针,也可能包含很多个指向后续节点的指针,这样在查找、插入、删除某个节点的过程中,可以避免一些不必要的节点,从而提高效率。

所以,每个节点的数据结构设计如下:

跳跃表的设计如下:

那么,如何进行查找呢?

假设查找5,那么在查找的过程中,需要从最高层开始查找(毕竟,越高层越表示索引嘛,很可能一下子就找到数据了),如果元素小于5,则一直向右查找。若遇到大于5的,则降低一层,在下一层继续查找。查找的流程如下图所示:

查找的代码如下:

插入的过程是怎么样的呢?

插入的过程包括如下4个步骤:

1、首先,需要找到每一层要插入节点的位置,并保存(用于后续调整指针);

2、确定该节点包含的层数,初始化要插入的节点;

3、相关的指针的调整;

4、若跳跃表层数增加,需要调整Header节点。

如下图,若要插入key 为4.5的节点,先要找到需要插入的位置,如图中黄线所示,然后随机生成一个层数(范围是1层到当前跳跃表层数+1,随机数生成器可以自行设计),初始化该节点,然后进行调整指针。

假设随机生成的层数为3,那么插入后为:

是不是比平衡树简单多了?当然,如果随机生成的层数为 当前跳跃表层数+1,那么跳跃表层数增加一层,header节点需要增加一层。

Python实现如下:

删除操作呢?跟插入操作类似,但是更为简单,只需要如下3个步骤:

1、首先,需要找到每一层要删除节点的位置,并保存(用于后续调整指针);

2、相关的指针的调整;

3、若层数减少,需要调整跳跃表层数和Header节点。

如果删除6这个节点,找到相应的位置,然后调整指针即可:

删除后的结果为:

Python代码实现为:

这里需要注意,如果删除元素后导致层数发生变化,那么需要对header节点进行调整的,即降低一层。

跳跃表的原理及实现你是否深入理解了?

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20190121A0P7HB00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券