设计跳表

标签: 设计 链表

难度: Hard

不使用任何库函数，设计一个 跳表 。

跳表 是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。

例如，一个跳表包含 [30, 40, 50, 60, 70, 90] ，然后增加 80、45 到跳表中，以下图的方式操作：

跳表中有很多层，每一层是一个短的链表。在第一层的作用下，增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n))，空间复杂度是 O(n)。

了解更多 : https://oi-wiki.org/ds/skiplist/

在本题中，你的设计应该要包含这些函数：

  • bool search(int target) : 返回target是否存在于跳表中。
  • void add(int num): 插入一个元素到跳表。
  • bool erase(int num): 在跳表中删除一个值，如果 num 不存在，直接返回false. 如果存在多个 num ，删除其中任意一个即可。

注意，跳表中可能存在多个相同的值，你的代码需要处理这种情况。

示例 1:

输入
["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"]
[[], [1], [2], [3], [0], [4], [1], [0], [1], [1]]
输出
[null, null, null, null, false, null, true, false, true, false]

解释
Skiplist skiplist = new Skiplist();
skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0);   // 返回 false
skiplist.add(4);
skiplist.search(1);   // 返回 true
skiplist.erase(0);    // 返回 false，0 不在跳表中
skiplist.erase(1);    // 返回 true
skiplist.search(1);   // 返回 false，1 已被擦除

提示:

  • 0 <= num, target <= 2 * 104
  • 调用search, add,  erase操作次数不大于 5 * 104 

Submission

运行时间: 364 ms

内存: 24.2 MB

import random


level = 10


class Node:

    def __init__(self, val):
        self.val = val
        self.ne = [None for _ in range(level)]


class Skiplist:

    def __init__(self):
        self.head = Node(-1)

    def find(self, target, ns):
        cur = self.head
        for i in range(level-1, -1, -1):
            while cur.ne[i] and cur.ne[i].val < target:
                cur = cur.ne[i]
            ns[i] = cur

    def search(self, target: int) -> bool:
        ns = [None for _ in range(level)]
        self.find(target, ns)
        if ns[0].ne[0] and ns[0].ne[0].val == target:
            return True
        return False

    def add(self, num: int) -> None:
        ns = [None for _ in range(level)]
        self.find(num, ns)
        node = Node(num)
        for i in range(level):
            node.ne[i] = ns[i].ne[i]
            ns[i].ne[i] = node
            if random.randint(0, 1) == 0:
                break

    def erase(self, num: int) -> bool:
        ns = [None for _ in range(level)]
        self.find(num, ns)
        if ns[0].ne[0] is None or ns[0].ne[0].val != num:
            return False
        for i in range(level):
            if ns[i].ne[i] and ns[i].ne[i].val == num:
                ns[i].ne[i] = ns[i].ne[i].ne[i]
        return True

# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)

Explain

跳表是一种可以在对数时间复杂度内进行搜索、添加和删除操作的数据结构。它通过多层链表组织数据，每一层是上一层的子集。在顶层，查找、添加或删除元素时可以跳过大量元素，从而加快速度。代码中实现了一个跳表，包括搜索、添加和删除功能。每个节点存储值和一个列表，列表中的每个元素都指向下一个节点。节点的层数是随机确定的，以确保跳表的效率。

时间复杂度: O(log n)

空间复杂度: O(n)

import random


level = 10  # 层级数设定为10，这是一个经验值


class Node:
    def __init__(self, val):
        self.val = val  # 节点存储的值
        self.ne = [None for _ in range(level)]  # 指向不同层下一个节点的指针


class Skiplist:
    def __init__(self):
        self.head = Node(-1)  # 初始化头节点，值为-1

    def find(self, target, ns):
        cur = self.head
        for i in range(level-1, -1, -1):
            while cur.ne[i] and cur.ne[i].val < target:
                cur = cur.ne[i]
            ns[i] = cur  # 记录每层最接近target的节点

    def search(self, target: int) -> bool:
        ns = [None for _ in range(level)]
        self.find(target, ns)
        if ns[0].ne[0] and ns[0].ne[0].val == target:
            return True
        return False

    def add(self, num: int) -> None:
        ns = [None for _ in range(level)]
        self.find(num, ns)
        node = Node(num)
        for i in range(level):
            node.ne[i] = ns[i].ne[i]
            ns[i].ne[i] = node
            if random.randint(0, 1) == 0:  # 随机决定是否继续向上层添加
                break

    def erase(self, num: int) -> bool:
        ns = [None for _ in range(level)]
        self.find(num, ns)
        if ns[0].ne[0] is None or ns[0].ne[0].val != num:
            return False
        for i in range(level):
            if ns[i].ne[i] and ns[i].ne[i].val == num:
                ns[i].ne[i] = ns[i].ne[i].ne[i]  # 删除节点
        return True

# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)

Explore

在跳表中，节点的层数是通过一个随机过程决定的，通常是一个几何分布。例如，每一层都有一半的概率继续到下一层。这种随机化层数有助于维持跳表的平衡性和效率。随机层数可以确保跳表不会退化成普通链表，从而保持各项操作的对数时间复杂度。

从最高层开始搜索是为了最大化搜索效率。在顶层，每一步可以跳过更多的节点，快速逼近目标值的位置。如果从底层或中间某层开始，将无法利用高层的跳过效果，可能导致搜索效率降低，接近线性时间复杂度。

在添加节点时，首先找到每层最接近目标值的节点，然后将新节点插入到适当的位置。通过随机层数决定新节点应存在于多少层，这种方式可以在保证跳表结构平衡的同时，维护其对数时间复杂度的特性。层级更新采用随机决策，有助于防止结构的偏斜和性能退化。

在删除操作中，首先找到每一层中该节点的前驱节点。然后，从最低层开始，如果该层的下一个节点是目标节点，则将其从链表中移除，继续到更高层检查并移除。这样可以确保节点从所有层中被正确地删除，而不会破坏跳表的结构和性能。