好玩的网站列表

1. 概念

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

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

2. 如何理解跳表

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

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

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

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

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

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

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

4. 跳表索引动态更新

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

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

---

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