educative.io

AVL Trees rotation : Clarifying case-3 of single left rotation in the the right-right case

Courses
,
#1

I want to clarify the after rotation tree in the case 3, where the C is the right child of U and G is the right child of C. The tree looks like this

       U
   /       \
  ST4        C
           /    \
       ST3          G
                 /      \
                ST1     ST2

Where ST4, ST3, ST1 and ST2 are corresponding subtrees. Note: The above tree exactly resembles the tree from the tree included in the example.

Note that according to the BST property, ST4 < U.

According to the U, C and G positions, this is a right-right case which means it requires a single left rotation for the balancing. So after we perform the left rotation around U and C, the after rotation tree is shown as below.

                C
          /           \
         U             G
     /       \      /       \
   ST3      ST4    ST1      ST2

My doubt is about the positions of ST3 and ST4 in the after rotation tree. Doesn’t it break the initial BST property from the original tree that ST4 < U ?

Course: Data Structures for Coding Interviews in C++ - Learn Interactively
Lesson: AVL Insertion

Course: Data Structures for Coding Interviews in C++ - Learn Interactively
Lesson: AVL Insertion

#2

Hi @Dishant_Arora,
Thanks for pointing this out. You are right. Children of the “U” node were not in their correct positions. We’ve verified and fixed this.

The ST4 node should be on the left, and ST3 should be on the right. Here is the correct AVL tree after the balancing.

                C
          /           \
         U             G
     /       \      /       \
   ST3      ST4    ST1      ST2

Thanks again for highlighting this.
Happy Learning!