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 MyAVL():      def __init__(self, data):          self.data = data          self.left = None          self.right = None          self.height = 0          self.balf = 0            def getLeft(self):          return self.left            def getRight(self):          return self.right            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 = MyAVL(data)                                         else:                          self.left.insert(data)                                        elif data >= self.data:                      if self.right is None:                          self.right = MyAVL(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 = MyAVL(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 = MyAVL(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  

https://stackoverflow.com/questions/66809427/how-to-implement-avl-tree-rotation March 26, 2021 at 08:28AM