面试题：如何基于Redis跳跃表设计实现一个支持范围查询且高效删除的有序集合？

设计思路

节点结构：
- 借鉴Redis跳跃表的节点结构，每个节点除了存储成员（member）和分数（score）外，还需要额外的指针。
- 节点结构定义如下：

class SkipListNode:
    def __init__(self, member, score, level):
        self.member = member
        self.score = score
        self.forward = [None] * (level + 1)

member 是有序集合中的成员（例如字符串等），score 是该成员对应的分数，forward 数组用于存储不同层次的指针，指向下一个节点。

层次构建方式：
- 与Redis跳跃表类似，在插入新节点时，通过随机函数决定新节点的层数。
- 假设最大层数为 MAX_LEVEL，初始层数为1。每次插入新节点时，以一定概率（例如1/2）决定是否增加节点的层数，直到达到 MAX_LEVEL。
- 例如在Python中实现随机层数生成：

import random

MAX_LEVEL = 16

def random_level():
    level = 1
    while random.random() < 0.5 and level < MAX_LEVEL:
        level += 1
    return level

范围查询算法：
- 从跳跃表的顶层开始，沿着指针查找。
- 对于查询分数在 [min_score, max_score] 区间内的成员：
  - 从顶层的头节点开始，在每一层，当遇到节点的分数大于 max_score 时，下降到下一层继续查找；当遇到节点的分数大于等于 min_score 时，记录该节点，并继续沿着该层的指针查找，直到分数大于 max_score。
- 例如Python代码实现：

def range_query(skip_list, min_score, max_score):
    current = skip_list.header
    result = []
    for i in range(skip_list.level, 0, -1):
        while current.forward[i] and current.forward[i].score < min_score:
            current = current.forward[i]
    current = current.forward[0]
    while current and current.score <= max_score:
        if current.score >= min_score:
            result.append(current.member)
        current = current.forward[0]
    return result

删除操作的实现逻辑：
- 首先，像查询一样，从顶层开始找到要删除节点的位置。
- 记录每一层指向要删除节点的前驱节点。
- 然后，从底层到顶层，依次调整指针，跳过要删除的节点。
- 例如Python代码实现：

def delete(skip_list, member, score):
    update = [None] * (skip_list.level + 1)
    current = skip_list.header
    for i in range(skip_list.level, 0, -1):
        while current.forward[i] and (current.forward[i].score < score or 
                                      (current.forward[i].score == score and current.forward[i].member < member)):
            current = current.forward[i]
        update[i] = current
    current = current.forward[0]
    if current and current.score == score and current.member == member:
        for i in range(skip_list.level + 1):
            if update[i].forward[i] != current:
                break
            update[i].forward[i] = current.forward[i]
        while skip_list.level > 1 and skip_list.header.forward[skip_list.level] is None:
            skip_list.level -= 1
        return True
    return False

时间和空间复杂度分析

时间复杂度：
- 插入操作：平均情况下，插入操作的时间复杂度为 $O(\log n)$，因为随机生成的层数期望是 $O(\log n)$，最坏情况下为 $O(n)$，当每次生成的层数都为最大层数时。
- 范围查询：平均情况下，范围查询的时间复杂度也是 $O(\log n + k)$，其中 $k$ 是范围内节点的数量。因为查找范围起始节点的时间复杂度为 $O(\log n)$，然后遍历范围内节点的时间复杂度为 $O(k)$。最坏情况下为 $O(n)$，当所有节点都在查询范围内时。
- 删除操作：平均情况下，删除操作的时间复杂度为 $O(\log n)$，因为查找要删除节点的时间复杂度为 $O(\log n)$，调整指针的时间复杂度也是 $O(\log n)$。最坏情况下为 $O(n)$，当要删除的节点在最底层且前面有很多节点时。
空间复杂度：
- 跳跃表的空间复杂度为 $O(n)$，因为平均情况下，每个节点有 $O(1)$ 个指针，总共有 $n$ 个节点。但是在最坏情况下，空间复杂度为 $O(n \log n)$，当所有节点的层数都达到最大层数时。

星途面试题库

面试题：如何基于Redis跳跃表设计实现一个支持范围查询且高效删除的有序集合？

知识考点

面试题答案

设计思路

时间和空间复杂度分析