Which rotations in AVL trees are known as single rotations?
2021
Which rotations in AVL trees are known as single rotations?
- A.
LL and RR
- B.
LL and LR
- C.
RR and RL
- D.
LR and RL
Attempted by 716 students.
Show answer & explanation
Correct answer: A
In AVL trees, rotations are used to maintain balance after insertions or deletions. Rotations are classified as single or double based on the number of steps required.
Single rotations are performed when the imbalance is in the same direction as the insertion. These include:
LL rotation: performed when the left subtree of the left child is heavy.
RR rotation: performed when the right subtree of the right child is heavy.
Double rotations are used when the imbalance is in the opposite direction. These include:
LR rotation: left rotation on the left child, then right rotation on the root.
RL rotation: right rotation on the right child, then left rotation on the root.
Thus, only LL and RR are single rotations.