跳表的python实现

跳表的性能和红黑树 avl差不多，但是结构相当简单。

只需要简单操作链表，就能很容易实现跳表。

参考如下文章，自己用python实现了一个跳表的例程

https://blog.sina.com.cn/s/blog_72995dcc01017w1t.html

##
#  example of skip list source code for c
##
import random
import sys

minint=0
maxint=65535
class node(object):
    def __init__(self, key=minint, value=none, level=1):
        self.key = key
        self.value = value
        self.level = level
        self.right = none
        self.down = none

class skiplist(object):
    def __init__(self):
        self.top = node(minint)
        self.top.right = node(maxint)
        self.nodenum = 0
        pass

    def getnode(self, key):
        node = self.top
        while 1:
            while key >= node.right.key :
                node = node.right
            if( key == node.key):
                return node
            if node.down == none:
                return none
            node = node.down
    def findnode(self, key):
        return self.searchnode(self.top,key)

    def searchnode(self, node, key):
        while key >= node.right.key:
            node = node.right
        if key == node.key:
            return node
        if node.down == none:
            return none
        return self.searchnode(node.down, key)


    def insertnode(self, top, key, value):
        while key >= top.right.key:
            top = top.right
        if key == top.key:
            return none
        if top.down == none:
            node = node(key, value)
            node.right = top.right
            top.right = node
            node.level = top.level
            self.nodenum = self.nodenum + 1
            return node
        downnode = self.insertnode(top.down, key, value)
        if downnode:
            node = node(key, value)
            node.right = top.right
            top.right = node
            node.down = downnode
            node.level = top.level
            return node
        return none

    def insert(self, key, value):
        k = self.getk()
        for l in xrange(self.top.level+1,k+1):
            topleft = node(minint, level=l)
            topright = node(maxint, level=l)
            topleft.right = topright
            topleft.down = self.top
            self.top = topleft
            print "l="+str(self.top.level)
        top = self.top
        while top.level != k:
            top = top.down
        
        self.insertnode(top, key, value)
        print "num="+str(self.nodenum)+" "+str(k)+" "+str(key)+" "+str(value)+" insert ok"
        
    def getk(self):
        k = 1
        while random.randint(0,1):
            k = k + 1
        return k

def printnode(node):
    print "level="+str(node.level)+" key="+str(node.key)+" value="+str(node.value)
    pass
if __name__ == '__main__':
    skiplist = skiplist()
    for x in xrange(1,10):
        skiplist.insert(x, random.randint(3,1000))
    printnode(skiplist.getnode(4))
    printnode(skiplist.findnode(4))