跳跃表python实践

redis的zset常用场景：
统计日活；打赏排行榜；天梯榜等
zset底层基于跳跃表实现

跳跃表代码实现,练习版

import random
random.seed(1)
MAX_LEVEL = 4


def randomLevel():
    """
    跳表的节点高度计算函数
    """
    k = 0
    while random.randint(0, 1):
        k += 1
    k = k if k < MAX_LEVEL else MAX_LEVEL
    return k


def travel(skiplist):
    """
    遍历跳表,当成二维数组来思考
    :param skiplist:
    :return:
    """
    head = skiplist.head # head负责往下走
    print ("遍历跳表开始")
    while head:
        level_str = 'header'
        current = head # current负责往右走
        while current.right:
            current = current.right
            level_str += " -> %s" % (current.key)
        print (level_str)
        head = head.down
    print ("遍历跳表结束")


class Node(object):
    def __init__(self, key, value=None, extra_data={}, level=0):
        self.key = key
        self.value = value
        self.extra_data = extra_data
        self.level = level
        self.right = None
        self.down = None


class SkipList(object):

    def __init__(self):
        self.head = Node(float('-inf'))
        self.head.right = Node(float('inf'))

    def search(self, target):
        """未验证"""
        current = self.head
        while current:
            if current.key < target <= current.right.key:
                if current.right.key == target:
                    print ("找到节点:", current.key, current.value)
                    return True
                current = current.down
            else:
                current = current.right
        return False

    def find_node(self, target):
        """递归的写法"""
        return self.searchNode(self.head, target)

    def searchNode(self, node, key):
        while key >= node.right.key:
            node = node.right
        if key == node.key:
            print ("找到节点:", node.key, node.extra_data, "层:", node.level)
            return True
        if node.down == None:
            return False
        return self.searchNode(node.down, key)

    def insertNode(self, current, key, value):
        while key >= current.right.key:
            current = current.right
        # 为什么return None,因为跳表的key是唯一的,redis的zset中,如果key已经存在,则根据该元素的score更新排名
        if key == current.key:
            return None
        # 已经走到了level 0层时的逻辑
        if current.down == None:
            node = Node(key, value) # node是插入的节点
            # eg: 在5 --> 15 之间插入Node(10),此时current是Node(5)
            node.right = current.right
            current.right = node
            node.level = current.level
            return node
        downnode = self.insertNode(current.down, key, value)
        if downnode: # 这里处理的是上一层
            node = Node(key)
            node.right = current.right
            current.right = node
            node.down = downnode
            node.level = current.level
            return node
        return None

    def insert(self, key, value):
        k = randomLevel()
        # 如果k和self.head.level都是0时,说明不用建高速,直接在0层添加即可
        # 如果k=1,self.head.level是0时,就需要一层一层网上找,找到最高层,for循环是为了把这几层的边界弄出来
        for l in range(self.head.level+1, k+1):
        #   这个地方画图想象,先获取上一层的左右,最左.right指向最右；
        #   最左.down指向下一层的head(刚好是self.head)，然后让self.head爬楼升1
            headleft, headright = Node(float("-inf"), level=l), Node(float("inf"), level=l)
            headleft.right = headright
            headleft.down = self.head
            self.head = headleft
        head = self.head # 跳表最高层的头
        while head.level != k:
            head = head.down
        self.insertNode(head, key, value)
        print ("k=%s, key=%s, value=%s, insert OK" %(k, key, value))

    def erase(self, num):
        current = self.head
        is_removed = False
        while current:
            if current.val < num <= current.right.val:
                if current.right.val == num:
                    current.right = current.right.right
                    is_removed = True
                current = current.down
            else:
                current = current.right
        return is_removed


if __name__ == '__main__':
    skiplist = SkipList()
    skiplist.insert(4, random.randint(1,100))
    skiplist.insert(5, random.randint(1,100))
    skiplist.insert(15, random.randint(1,100))
    skiplist.insert(25, random.randint(1,100))
    skiplist.insert(35, random.randint(1,100))
    print (skiplist.find_node(25))
    print (skiplist.find_node(15))
    travel(skiplist=skiplist)