一问一答之数据结构
说说跳表
跳表 = 链表 + 多级索引(空间换时间,复杂度为klogn,k为每个几个节点简历一次索引,常数项忽略,那就是logn)
允许快速查询,给链表增加索引,查找数据首先在索引层进行遍历,相当于在一个范围内查找,索引层可以多层
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 柠檬大师的空间站!
评论
跳表 = 链表 + 多级索引(空间换时间,复杂度为klogn,k为每个几个节点简历一次索引,常数项忽略,那就是logn)
允许快速查询,给链表增加索引,查找数据首先在索引层进行遍历,相当于在一个范围内查找,索引层可以多层