Obteniendo AttributeError: el objeto ‘NoneType’ no tiene el atributo ‘rightnode’ en el árbol AVL.
Actualmente estoy aprendiendo estructuras de datos y tengo un problema con el árbol AVL.
Código:
from myqueue import Queue # mi cola personalizada implementada por una lista enlazada
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()
Dado que el nodo izquierdo está desbalanceado, está generando un error en el método rightrotation () cuando intentamos equilibrar ese nodo.
Por lo tanto, el error se produce en el método insertnode ().
Error que me está apareciendo:
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'
Intenté depurar pero no encontré nada.
Aquí está mi archivo myqueue.py: https://paste-bin.xyz/18851
Cualquier ayuda o pista será apreciada.
Gracias.
Edit:
Actualmente, mi árbol se ve así:
5
\
10
\
15
\
20
# como se puede ver, está claramente desequilibrado, por lo que necesitamos una rotación hacia la izquierda, ya que es la condición RR
Entonces, después de hacer la rotación a la izquierda, el resultado se ve así:
10</rootnode.rightnode.data:></rootnode.leftnode.data:>
/ \
5 15
\
20
davy.ai
Posibles soluciones al error en la implementación del árbol AVL en Python:
disbalancenodetiene un atributoleftnodeque es None, por lo que la funciónrightrotation()falla al intentar acceder a su atributorightnode. Una posible causa de este error es que la funcióninsertnode()no está devolviendo el nodo raíz modificado después de insertar un nuevo nodo de forma recursiva. Para solucionar esto, agregue una declaración de retorno al final de la función que devuelva el nodo raíz actualizado. Por ejemplo:De esta manera, se devuelve al llamador el objeto rootnode que se modifica recursivamente, para que la estructura del árbol AVL se actualice correctamente.
Otra posible problema es que la altura de cada nodo no se calcula correctamente después de realizar una rotación. Para solucionar esto, actualice el atributo de la altura de ambos, el nodo rotado y sus nodos hijos en función de sus alturas actuales. Por ejemplo, en la función
leftrotation()agregue la siguiente línea antes de devolver el nuevo nodo raíz:Y en la función
rightrotation()agregue la siguiente línea antes de devolver el nuevo nodo raíz:De esta manera, la estructura del árbol AVL mantendrá su propiedad de equilibrio, donde la diferencia de alturas entre dos subárboles de un nodo es como máximo uno.
Por último, asegúrese de que la implementación de
Queueque está utilizando funciona correctamente, ya que no se proporciona en el fragmento de código. Si la cola no está implementada correctamente, puede causar errores o comportamientos inesperados en el algoritmo de recorrido del árbol AVL. Puede probar laQueuepor separado y asegurarse de que funcione como se espera antes de usarla en la implementación del árbol AVL.