algorithmdata-structuresavl-tree

AVL: Right rotation, updating heights

I am reading a tutorial in AVL trees https://www.programiz.com/dsa/avl-tree In the implementation of right rotation https://www.programiz.com/dsa/avl-tree # Function to perform right rotation

def rightRotate(self, z):
    y = z.left
    T3 = y.right
    y.right = z
    z.left = T3
    z.height = 1 + max(self.getHeight(z.left),
                       self.getHeight(z.right))
    y.height = 1 + max(self.getHeight(y.left),
                       self.getHeight(y.right))
    return y

I do not understand why we need to change only these heights.

For example here: enter image description here

Both 8 , 9 and 11 changed heights but according to the implementation only 9's and 11's heights will be informed as I understand.

Solution

  • The left subtree and the right subtree of the node in your example (node 8) will not be affected by the right rotation، and so the height of that node will not need to change. (Because the height of a node is equal to 1 + max(height of left subtree, height of right subtree)).