获取属性错误：'NoneType'对象在avl树中没有属性'rightnode'

Question

我目前正在学习数据结构，并且在 AVL 树中遇到问题。

代码：

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()

由于左节点不平衡，因此当我们尝试平衡该节点时，它会在

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

所以左旋转后结果看起来像：

    10
   /  \  
  5    15
        \
         20

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