如何实现AVL树旋转？

Question

我编写了一个 AVL 树，我的旋转逻辑是正确的，但我仍然无法让它正常工作。对于根节点上的旋转，我的旋转工作正常，但如果旋转在树的更下方，则父节点不会指向已旋转到位的新节点，而是继续指向旋转之前就位的节点.我很确定问题出在我的插入方法上，但我不确定如何在发生旋转时让父节点指向新节点。我知道你可以添加一个父变量来解决这个问题，但我想知道是否有没有办法做到这一点。

For example
               10                                     10                                10
            /      \                                /   \           instead of         /    \
           8        12     Rotates to ->            8    12                          6      12
          /          \                                    \                         / \      \
         6            14                                    14                     4   8       14
         /                                        4 and 6 are lost
        4

class AVL():
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 0
        self.balf = 0
    
    def getData(self):
        return self.data

    def getHeight(self):
        return self.height
  
    def heightCalc(self,node):
        
        if node is None:
            return -1
        else:
            return max(self.heightCalc(node.left), self.heightCalc(node.right)) + 1 
    
    def getBalanceFactor(self):      
        return self.balf
   
    def balCheck(self, node):
        if node is None:
            return -1
        else:
            return self.heightCalc(node.left) - self.heightCalc(node.right)
      
    def insert(self, data):
         if data is not None:   
            if self.data is None:
                self.data = data
            else:
                if data < self.data:
                    if self.left is None:
                        self.left = AVL(data)                   
                    else:
                        self.left.insert(data)                      
                elif data >= self.data:
                    if self.right is None:
                        self.right = AVL(data)                        
                    else:
                        self.right.insert(data)                       
        
         self.height=self.heightCalc(self)
         self.balf = self.balCheck(self)
         
         if self.balf > 1:
             if self.left.getBalanceFactor() < 0:
                 self.left = self.left.leftRotate()
                 return self.rightRotate()
             else:
                  
                  return self.rightRotate()
         elif self.balf < -1:
             if self.right.getBalanceFactor() > 0:
                 self.right = self.right.rightRotate()
                 return self.leftRotate()                    
             else:
                 
                 return self.leftRotate()
          
         return self
        

    def leftRotate(self):
         temp = self.right
         temp2 = self.right.left
         self.right.left = self
         self.right = temp2
         self.height = self.heightCalc(self)
         temp.height = self.heightCalc(temp)
         self.balf = self.balCheck(self)
         temp.balf = self.balCheck(temp)
         
         return temp
        
       

    def rightRotate(self):
       
        tmp = self.left
        tmp1 = self.left.right
        self.left.right = self
        self.left = tmp1
        
        self.height = self.heightCalc(self)
    
        tmp.height = self.heightCalc(tmp)
        
        self.balf = self.balCheck(self)
        
        tmp.balf = self.balCheck(tmp)
        return tmp

#This example works properly
test = AVL(10)
test= test.insert(12)
test = test.insert(8)
print(test.data) #outputs 8
print(test.left.data) #outputs 7
print(test.right.data) #outputs 10

#In this case the rotation occurs but the parent node does not update its left child to the new node and still points to 8
test2 = AVL(10)
test2 = test2.insert(12)
test2 = test2.insert(8)
test2 = test2.insert(14)
test2 = test2.insert(6)
test2 = test2.insert(4)
print(test2.data)#outputs 10
print(test2.left.data)#outputs 8 but should be 6
#4 and 6 can no longer be accessed because they are lost

Answer 1

在您的代码中，insert 方法 return 是子树的新根，在插入完成并发生任何需要的旋转之后。您的问题是，当您在其中一个子节点上递归调用 insert 时，您没有使用该 return 值。

            if data < self.data:
                if self.left is None:
                    self.left = MyAVL(data)                   
                else:
                    self.left = self.left.insert(data)     # update self.left here
            elif data >= self.data:
                if self.right is None:
                    self.right = MyAVL(data)                        
                else:
                    self.right = self.right.insert(data)   # and self.right here

如何实现AVL树旋转？

How to implement AVL tree rotation?

python

recursion

avl-tree