跳表的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))