python AVL tree insertion

Question

I have written a python code to implement. While writing the code I referred completely to the pseudo code I had. To test the class 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()

the following is the AVL tree implementation saved 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 outputs of app.py seemed fine at the beginning. But for repeatedly running app.py with higher values of n (over fifty) I began to notice that often some nodes had a balance factor of absolute value strictly greater than 1 or even 2. During one run it even gave an error because it tried to left-rotate a node with no right child.

The problem most probably lies in the insertion function. I have repeatedly checked my balancing conditions and rotation algorithms. They all seem fine theoretically. I'd be glad if someone could find the error.

Answer 1

self is immutable in Python, when you return from a method, local variable is released and will not really change self like a pointer in c. You have to come up with another way to handle rotation. For example, https://github.com/pgrafov/python-avl-tree/blob/master/pyavltree.py handle a rotation by inferring a parent node.

See also: Is it safe to replace a self object by another object of the same type in a method?