跳表

12月29日 · 2019年

数据结构:跳表

183 0
本文主要总结下自己学习跳表时的一些笔记,主要包含跳表的由来、时空复杂度、增删改查和具体应用四个方面。二分查找的数据结构是数组,利用数组随机访问查找的时间复杂度是 O(logn)。如果数据结构是链表,可以达到这样的速度吗?答案是可以的,只是需要对链表进行改造,改造之后的结构就是跳表(又名跳跃表),是一种动态数据结构,可以支持快速的插入、删除、查找、按范围查找,功能类似于红黑树,Redis 中的有序集合使用的就是跳表(后文会说)。...