How to implement AVL tree rotation?

I have coded an AVL Tree and my logic for the rotations is correct but I am still not able to get it working properly. For rotations on the root node my rotations work properly but if the rotation is further down the tree, the parent node does not point to the new node that has been rotated into place and continues to point to the node that was in place before the rotation. I am pretty sure the issues lies with my insert method but I am not sure how to get the parent node to point to the new node when a rotation occurs. I know you can add a parent variable to fix this but I am wondering if there is a way to do it without that.

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

In your code, the insert method returns the new root of the subtree, after the insertion has been done and any needed rotations have happened. Your issue is that you’re not using that return value when you recursively call insert on one of your child nodes.

            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

Advertisement

Answer