欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

跳表的python实现

程序员文章站 2022-06-25 15:48:07
跳表的性能和红黑树 avl差不多,但是结构相当简单。 只需要简单操作链表,就能很容易实现跳表。 参考如下文章,自己用python实现了一个跳表的例程 https://blog...

跳表的性能和红黑树 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))