未分类
未读
跳表 SkipList
摘要：
跳表是一种有序数据结构，通过多层索引链表加速查找过程。底层链表包含所有元素并保证有序，而高层链表包含较少的随机选择元素。构建跳表时，每隔一定数量元素会选取一个元素构建上层链表。查找时，从高层开始逐步缩小范围至底层。插入和删除操作的时间复杂度也为O(log N)。跳表适用于需要频繁查询和动态更新数据的场景，如Redis的Sorted Set。