getting AttributeError: 'NoneType' object has no attribute 'rightnode' in avl tree

Question

我目前正在学习数据结构，但我在 AVL 树中遇到了问题

代码：

from myqueue import Queue   #my custom queue implimented 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()

由于左节点不平衡，因此当我们尝试平衡该节点时，rightrotation() 方法会出现错误

所以错误出现在insertnode()方法

我得到的错误：

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'

我试过调试但找不到任何东西

这是我的 myqueue.py 文件：https://paste-bin.xyz/18851

任何帮助或线索将不胜感激

谢谢

编辑：

目前我的树看起来像：

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

所以在左旋转后结果如下：

Answer 1

实际上有几个原因会导致您收到此错误：

平衡因子的计算方式与通常情况相反：当树的左子树较高时，平衡因子为正，而右子树较高时，平衡因子为负。这让我很困惑。
可能你有同样的困惑，因为多个if条件（如：nodevalue<rootnode.leftnode.data）中的比较运算符是错误的，所以你的代码结束了向上旋转错误，导致异常。
当你做双旋转时，旋转的方向应该是相反的。在一种情况下，您有两个连续的 leftrotation 调用。这是错误的。

因此，在不更改余额计算的情况下，您可以更正它：

    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)  # <-- corrected
    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

getting AttributeError: 'NoneType' object has no attribute 'rightnode' in avl tree

getting AttributeError: 'NoneType' object has no attribute 'rightnode' in avl tree

python

tree

avl-tree

data-structures