python - Rotation of AVL tree nodes does not work -
i trying write avl tree in python rotation doesnt work becase cannot swap "self" node other. there way fix it? think doing in java or c way not correct...
class sentinel(object): value = left = right = none height = -1 sentinel = sentinel() #singleton of sentinel node class node: def __init__(self, data, left=sentinel, right=sentinel, height=0): self.data = data self.left = left self.right = right self.height = height def addnode(self, data): if self.data == data: #return when node duplicated return isleft = self.data > data child = self.left if isleft else self.right if child sentinel: if isleft: self.left = node(data) else: self.right = node(data) else: child.addnode(data) if abs(child.right.height - child.left.height) == 2: print("rebalancing after inserting", data) ''' need balance subtree''' if data < child.data: rotation = self.rotateleft if isleft else self.rotateright else: rotation = self.doublerotateleft if isleft else self.doublerotateright rotation() self.left.setheight() if isleft else self.right.setheight() self.setheight() def printnodes(self): if self.left not sentinel: self.left.printnodes() print(self) if self.right not sentinel: self.right.printnodes() def setheight(self): self.height = max(self.left.height, self.right.height) + 1 def rotateright(self): new_root = self.left new_left_sub = new_root.right old_root = self self = new_root old_root.left = new_left_sub new_root.right = old_root def rotateleft(self): new_root = self.right new_left_sub = new_root.left old_root = self self = new_root old_root.right = new_left_sub new_root.left = old_root def doublerotateright(self): return def doublerotateleft(self): return def __str__(self): return str(self.data) class binarytree: def __init__(self): self.root = sentinel def add(self, data): print("before adding", data) self.printall() if self.root sentinel: self.root = node(data) else: self.root.addnode(data) def printall(self): if self.root sentinel: print("empty tree") else: self.root.printnodes() if __name__ == '__main__': b = binarytree() b.add(1) b.add(22) b.add(4) b.add(26) b.add(13) b.add(3) b.add(14) b.add(6) b.add(13) b.add(5) b.add(36) b.add(43) b.add(5) in range(1, 20): b.add(i) b.printall()
i suggest nodes contain link parent (the root having parent). easy:
def rotateleft(self): new_root = self.right new_left_sub = new_root.left old_root = self self.parent.right = new_root #assuming self right child old_root.right = new_left_sub new_root.left = old_root my code may not correct, can't test right now, idea is: have nodes keep reference parent.
some reference: http://interactivepython.org/runestone/static/pythonds/trees/avltreeimplementation.html
Comments
Post a Comment