跳表: 提高链表查询效率的数据结构

class SkipListNode:
    def __init__(self, val, right=None, down=None):
        self.val = val
        self.right = right
        self.down = down


class SkipList:
    def __init__(self):
        self.head = SkipListNode(float('-inf'))
        bottom = self.head

        while bottom:
            bottom.right = SkipListNode(float('inf'))
            bottom.down = bottom.right
            bottom = bottom.down

    def search(self, target):
        node = self.head

        while node:
            while node.right.val != float('inf') and node.right.val <= target:
                node = node.right

            if node.val == target:
                return True

            node = node.down

        return False

    def insert(self, num):
        path = []
        node = self.head

        while node:
            while node.right.val != float('inf') and node.right.val < num:
                node = node.right

            path.append(node)
            node = node.down

        down_node = None

        while path:
            node = path.pop()
            new_node = SkipListNode(num, node.right, down_node)
            node.right = new_node
            down_node = new_node

            if path and not path[-1].right.down:
                break

random.seed(42)
skip_list = SkipList()

for _ in range(10):
    num = random.randint(1, 100)
    skip_list.insert(num)

print(skip_list.search(50))  # True
print(skip_list.search(101))  # False