python AVL树插入

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 isn"
root.inorder()
k = input("Enter integer to insert: ")
root.insert(k)
root.inorder()
k = input("Enter integer to delete: ")
root.delete(k)
root.inorder()

以下是avl.py中保存的AVL树实现

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(),self.bal(),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,self.right.bal(),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,self.key
        if self.right:
            self.right.inorder()

app.py的输出在开始时似乎很好.但是为了反复运行具有更高n值(超过50)的app.py,我开始注意到通常一些节点的绝对值平衡因子严格大于1或甚至2.在一次运行期间它甚至给出了一个错误,因为它尝试过左旋转一个没有右子的节点.

问题最可能在于插入功能.我反复检查了我的平衡条件和旋转算法.它们在理论上看起来都很好.
如果有人能找到错误,我会很高兴.