[Python] Getting AttributeError: 'NoneType' object has no attribute 'rightnode' in avl tree

I am currently learning data structures and I have having an issue in AVL tree.

Code:

from myqueue import Queue # my custom queue implemented by linked list

class AVL:

def __init__(self,data):
self.data=data
self.leftnode=self.rightnode=None
self.height=1

def LevelOrderTransversal(self):
if not self:
return
queue=Queue()
queue.enqueue(self)
while not (queue.isempty()):
root=queue.dequeue()
print(root.data)
if root.leftnode is not None:
queue.enqueue(root.leftnode)
if root.rightnode is not None:
queue.enqueue(root.rightnode)

def getheight(rootnode):
if not rootnode:
return 0
return rootnode.height

def getbalance(rootnode):
if not rootnode:
return 0
return getheight(rootnode.leftnode)-getheight(rootnode.rightnode)

def leftrotation(disbalancenode):
rootnode=disbalancenode.rightnode
disbalancenode.rightnode=disbalancenode.rightnode.leftnode
rootnode.leftnode=disbalancenode
disbalancenode.height=1+max(getheight(disbalancenode.leftnode),getheight(disbalancenode.rightnode))
rootnode.height=1+max(getheight(rootnode.leftnode),getheight(rootnode.rightnode))
return rootnode

def rightrotation(disbalancenode):
rootnode=disbalancenode.leftnode
disbalancenode.leftnode=disbalancenode.leftnode.rightnode
rootnode.rightnode=disbalancenode
disbalancenode.height=1+max(getheight(disbalancenode.leftnode),getheight(disbalancenode.rightnode))
rootnode.height=1+max(getheight(rootnode.leftnode),getheight(rootnode.rightnode))
return rootnode

def insertnode(rootnode,nodevalue):
if rootnode.data is None:
return AVL(nodevalue)
elif nodevalue<rootnode.data:
if rootnode.leftnode is None:
rootnode.leftnode=AVL(nodevalue)
else:
insertnode(rootnode.leftnode,nodevalue)
else:
if rootnode.rightnode is None:
rootnode.rightnode=AVL(nodevalue)
else:
insertnode(rootnode.rightnode,nodevalue)

rootnode.height=1+max(getheight(rootnode.leftnode),getheight(rootnode.rightnode))
balance=getbalance(rootnode)

if balance>1 and nodevalue<rootnode.leftnode.data:
return rightrotation(rootnode)
if balance>1 and nodevalue>rootnode.leftnode.data:
rootnode.leftnode=leftrotation(rootnode.leftnode)
return rightrotation(rootnode)
if balance<-1 and nodevalue<rootnode.rightnode.data:
return leftrotation(rootnode)
if balance<-1 and nodevalue>rootnode.rightnode.data:
rootnode.rightnode=rightrotation(rootnode.rightnode)
return leftrotation(rootnode)
return rootnode



A=AVL(5)
A=insertnode(A,10)
A=insertnode(A,15)
A=insertnode(A,20)
A.LevelOrderTransversal()


Since the leftnode is disbalanced so it's raising error in rightrotation() method when we try to balance that node

So the error is arising in insertnode() method

Error I am getting:

Traceback (most recent call last):
File "c:\Users\Anurag Dabas\Desktop\python\avl tree\newavl.py", line 84, in <module>
A=insertnode(A,15)
File "c:\Users\Anurag Dabas\Desktop\python\avl tree\newavl.py", line 76, in insertnode
rootnode.rightnode=rightrotation(rootnode.rightnode)
File "c:\Users\Anurag Dabas\Desktop\python\avl tree\newavl.py", line 45, in rightrotation
disbalancenode.leftnode=disbalancenode.leftnode.rightnode
AttributeError: 'NoneType' object has no attribute 'rightnode'


I tried debugging but couldn't found anything

Here is my myqueue.py file: https://paste-bin.xyz/18851

Any help or clue will be appreciated

Thanks

Edit:

currently my tree looks like:

5
\
10
\
15
\
20
#as you can see it's clearly unbalance so we need leftrotation since it's RR condition


so after doing left rotation result looks like:

10
/ \
5 15
\
20

Continue reading...