What is the worst-case time complexity of searching in an AVL tree?

Options

  • A. O(1)
  • B. O(log n)
  • C. O(n)
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

B. O(log n)

Detailed Explanation

Because an AVL tree maintains a balanced height, its height remains O(log n). Therefore, searching for a key takes O(log n) time in the worst case. The same logarithmic worst-case bound applies to insertion and deletion, although these operations may require rotations to maintain balance. This is a major advantage of AVL trees over ordinary unbalanced BSTs, whose worst-case height can become O(n).
← Previous Next →

Attempt Quiz Now:

BPSC TRE 4 DSA Practice set 1

Feature Posts