数据结构第二季 Day22 跳表

一、跳表的前传

1、一个有序链表搜索、添加、删除的平均时间复杂度是多少（重要，竟然理解还是不到位）？

• O(n)

image.png

2、能否利用二分搜索优化有序链表，将搜索、添加、删除的平均时间复杂度降低至O(logn)？

• 不行
• 链表没有想数据那样的高效随机访问（O(1)时间复杂度），所以不能像有序数组那样直接进行二分搜索优化

3、那有没有其他办法让有序链表搜素、添加、删除的平均时间复杂度降低至 O(logn)？

• 有 ，使用跳表（SkipList）

image.png

二、跳表介绍

1、跳表的英文名是什么？在 xxx 基础上，增加了 xxx 功能？

• 跳表(SkipList)：在有序链表的基础上增加了“跳跃”的功能

2、跳表的设计初衷是什么？对比平衡树有什么优点吗？

• 初衷：为了取代平衡树（比如红黑树）
• 对比平衡树优点：①跳表的实现和维护会更加简单②跳表的搜索、删除、添加的平均时间复杂度是 O(logn)

image.png

3、使用跳表优化链表的思想？

image.png

• 如上图所示，如果要访问 25 要怎么走？
• 如上图所示，如果要访问 18 要怎么走？

4、跳表的添加和删除思路（把下面这张图记牢了，跳表的精髓也就掌握了）？

image.png