数据结构-跳表
跳表是一种基于链表实现的类似二分查找的数据结构,本文介绍跳表的结构性能、复杂度分析及索引的更新方式等

# 数据结构-跳表

# 跳表概念

  1. 二分查找法依赖于数组的随机访问特性,只能用数组实现

    跳表是基于链表实现类似于二分查找的算法

  2. 查找、插入、删除各方面性能都不错的动态数据结构,甚至可以替代红黑树

  3. Redis 中的有序集合(Sorted Set)就是用跳表来实现的

# 跳表结构

  1. 对于一个有序的单链表,想在其中查找某个数据,只能从头到尾遍历链表。效率很低
  2. 对链表建立一级索引,每两个结点提取一个结点到上一级,抽出来的一级称为索引层
  3. 索引层结点有指针指向下一级结点
  4. 在查找结点时,先在索引层遍历,再下降到原始链表,就能减少遍历次数
  5. 当链表很长,使用多级索引结构可以大大提高查找效率

# 跳表性能

# 跳表的高度

  1. 第 k 级索引的结点个数是第 k-1 级索引的结点个数的 $\frac{1}{2}$,那么第 k 级索引 结点的个数就是 $\frac{n}{2^k}$
  2. 假设索引有 h 级,最高级的索引有 2 个结点。通过上面的公式,可以得到求得 $h=log_2n-1$
  3. 如果包含原始链表这一层,整个跳表的高度就是 $log_2n$

# 查找时间复杂度

  1. 上级索引通过指针下降到下级索引

  2. 当每级索引都是两个结点抽出一个结点作为上一级索引的结点时,每一层最多遍历3个结点

    时间复杂度为 $O(2*logn)$,即 $O(logn)$

  3. 如果每一层最多要遍历 m 个结点,那么时间复杂度为 $O(m*logn)$

# 插入时间复杂度

  1. 在单链表中,如果知道要插入的位置,插入结点的时间复杂度是 $O(1)$

    为了保证原始链表中数据的有序性,需要先找到要插入的位置,这个查找操作比较耗时

  2. 查找某个结点的的时间复杂度是 $O(logn)$,查找某个数据应该插入的位置,时间复杂度也是 $O(logn)$

# 删除时间复杂度

  1. 如果这个结点在索引中也有出现,我们除了要删除原始链表中的结点,还要删除索引中的结点
  2. 删除一个结点要找到其前驱结点,如果是双向链表则可以通过指针获得
  3. 时间复杂度为 $O(logn)$

# 内存消耗

  1. 比起单链表,跳表需要存储多级索引,要消耗更多的存储空间

  2. 如果将包含 n 个结点的单链表构造成跳表,需要额外再用接近 n 个结点的存储空间

  3. 每隔三个结点抽出一个结点比每隔两个会节省索引存储空间,但性能会下降

  4. 在实际的软件开发中,原始链表中存储的可能是很大的对象

    而索引结点只需要存储关键值和几个指针,并不需要存储对象

    所以当对象比索引结点大很多时,索引占用的额外空间可以忽略

# 索引动态更新

  1. 跳表中插入数据,如果不更新索引,某 2 个索引结点之间数据过多,性能退化

  2. 跳表是通过随机函数来维护索引与原始链表大小之间的平衡

  3. 通过随机函数,来决定将这个结点插入到哪几级索引中

比如随机函数生成了值 K,就将这个结点添加到第一级到第 K 级索引中

随机函数的选取很重要,从概率上来讲,能够保证跳表的索引大小和数据大小平衡性,避免性能过度退化

Comment here, be cool~

Copyright © 2020 CadeCode

Theme 2zh powered by VuePress

本页访问次数 0

Loading