Which operation is used to restore the balance of an AVL tree after an insertion?

Options

  • A. Rotation
  • B. Hashing
  • C. Linear probing
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

A. Rotation

Detailed Explanation

When insertion causes an AVL tree to become unbalanced, rotations are used to restore the required height balance while preserving the Binary Search Tree ordering property. The four common imbalance cases are LL, RR, LR, and RL. LL is corrected using a right rotation, RR using a left rotation, while LR and RL require combinations of rotations. Rotations change the tree structure without changing the sorted order of its keys.