What is the worst-case time complexity of searching for an element in a balanced binary search tree (AVL tree) containing n nodes?
Answer and explanation
Correct answer: A. O(log n)
- Step 1: In a self-balancing binary search tree (such as an AVL or Red-Black tree), the tree height is strictly maintained at .
- Step 2: Each comparison eliminates half of the remaining subtrees, ensuring that search, insertion, and deletion operate in worst-case logarithmic time .
Answer
O(log n).
Why not the others: is average hash map lookup; is worst-case for degenerate unbalanced BSTs or linear search; is optimal comparison sorting.
Practise more Algorithms and Python Programming.
Free questions with an explanation for every one, and full timed EmSAT Achieve (UAE) mock tests.
More Algorithms and Python Programming questions
- What is the output of the following Python expression: [x**2 for x in range(6) if x % 2 != 0]?
- What will be printed by the following Python code snippet?
def func(val, lst=[]):
lst.append(val)
return lst
print(func(1))
print(… - Which abstract data structure operates on a First-In, First-Out (FIFO) ordering principle?
- What is the return value of executing the recursive Python function `mystery(4)`?
def mystery(n):
if n <= 1:
return 1
retur… - What is the worst-case time complexity of the standard QuickSort algorithm when the chosen pivot is consistently the smallest or largest ele…
- In Python, which of the following built-in data types is immutable?