I wrote code for python to implement. When writing code, I completely referenced the pseudocode that I had. To test the class that I created, I wrote a little test code "app.py". It takes the number of nodes from the user and randomly generates an AVL tree as follows: -
from avl import * import random n = input("Enter number of nodes: ") l = random.sample(range(-10000,10001),n) root = node(l[0]) for x in l: root = root.insert(x) print root.key print "Your tree is\n" root.inorder() k = input("Enter integer to insert: ") root.insert(k) root.inorder() k = input("Enter integer to delete: ") root.delete(k) root.inorder()
implements the AVL tree implementation stored in avl.py
class node: def __init__(self,data): self.left = None self.right = None self.key = data self.height = 1 def calheight(self): if not self.left: if not self.right: return 1 else: return 1 + self.right.height else: if not self.right: return 1 + self.left.height else: return max(self.left.height,self.right.height)+1 def rrotate(self): p=self.left self.left=p.right p.right=self self=p self.right.calheight() self.calheight() return self def lrotate(self): p=self.right self.right=p.left p.left=self self=p self.left.calheight() self.calheight() return self def dlrotate(self): self.right = self.right.rrotate() self = self.lrotate() return self def drrotate(self): self.left = self.left.lrotate() self = self.rrotate() return self def bal(self): if not self.left: if not self.right: return 0 else: return -(self.right.height) else: if not self.right: return self.left.height else: return (self.left.height-self.right.height) def insert(self,data): if (data < self.key): if not self.left: self.left = node(data) else: self.left = self.left.insert(data) if(self.bal() == 2): print self.height,"\t",self.left.bal(),"\t",self.bal(),"\t",self.key if(self.left.bal() == 1): self = self.rrotate() else: self = self.drrotate() elif (data > self.key): if not self.right: self.right = node(data) else: self.right = self.right.insert(data) if(self.bal() == -2): print self.height,"\t",self.right.bal(),"\t",self.bal(),"\t",self.key if(self.right.bal() == -1): self = self.lrotate() else: self = self.dlrotate() else: print "Key Already Exists" self.height=self.calheight() return self def delete(self,data): if (data < self.key): self.left = self.left.delete(data) elif (data > self.key): self.right = self.right.delete(data) else: if not self.left: if not self.right: temp = self self = None else: temp = self.right self = temp del temp elif not self.right: if not self.left: temp = self self = None else: temp = self.left self = temp del temp else: temp = self.right while temp.left: temp = temp.left self.key = temp.key self.right = self.right.delete(temp.key) if self: self.height=self.calheight() if(self.bal() > 1): if(self.left.bal() > 0): self = self.rrotate() else: self = self.drrotate() elif(self.bal() < -1): if(self.right.bal() < 0): self = self.lrotate() else: self = self.dlrotate() return self def inorder(self): if self.left: self.left.inorder() print self.height,"\t",self.bal(),"\t",self.key if self.right: self.right.inorder()
The conclusions of app.py looked fine at the beginning. But to run app.py multiple times with higher n values (more than fifty), I began to notice that often some nodes had an absolute balance coefficient strictly exceeding 1 or even 2. During one run, he even threw an error because he tried left-turn a node without the right of the child.
The problem most likely is the insert function. I have repeatedly checked my balancing conditions and rotation algorithms. All of them seem quite theoretical. I would be glad if anyone could find a mistake.