数据结构与算法(13)-跳表

  1. 1. 概念
  2. 2. 如何理解跳表
  3. 3. 高效的动态插入和删除操作
    1. 4. 跳表索引动态更新

1. 概念

  • 跳表
    • 动态数据结构
    • 可以支持快速的插入,删除,查找操作
    • 写起来也不会很复杂

Redis当中的有序集合就是用跳表来实现的。

2. 如何理解跳表

对于一个单链表来说,即便链表当中存储的数据是有序的,如果我们想要从中查找某个数据,也只能从头到尾遍历链表,这样查找效率就会非常低,时间复杂度比较高,O(n)

为了解决这个问题,我们可以对链表建立一级索引,每几个结点就提取一个结点到上一级当中,抽出来的那一级我们就可以将其叫做索引或者索引层了。

通过增加索引的层级,来加快寻找节点的速度,这就是跳表 – 链表加上多级索引的结构

  • 时间复杂度非常理想 O(logn)
  • 但是相对来说会更需要内存一些 空间复杂度为O(n)

3. 高效的动态插入和删除操作

其动态的插入和删除操作的时间复杂度为O(logn)

fig1.jpg

删除操作,还是需要拿到删除节点的前驱节点,然后通过指针操作完成删除。

4. 跳表索引动态更新

fig2.jpg

跳表是需要不断更新的,因为当我们不断向跳表里面插入数据的时候,如果我们不更新索引,就有可能出现两个索引节点之间数据非常多的情况。极端情况下,跳表就会退化成单链表。

  • 我们需要某种方式来维护索引与原始链表大小之间的平衡
    • 跳表是通过随机函数来维护平衡性的
    • 当我们往跳表里面插入数据的时候,可以选择同时将这个数据插入到部分索引层当中。
    • 根据随机函数来决定这个结点插入到哪几级索引当中。

fig3.jpg


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 stone2paul@gmail.com

文章标题:数据结构与算法(13)-跳表

文章字数:508

本文作者:Leilei Chen

发布时间:2020-02-09, 10:11:25

最后更新:2020-02-09, 10:12:09

原始链接:https://www.llchen60.com/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95-13-%E8%B7%B3%E8%A1%A8/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏