Which of the following is TRUE?
2008
Which of the following is TRUE?
- A.
The cost of searching an AVL tree is θ (log n) but that of a binary search tree is O(n)
- B.
The cost of searching an AVL tree is θ (log n) but that of a complete binary tree is θ (n log n)
- C.
The cost of searching a binary search tree is O (log n ) but that of an AVL tree is θ(n)
- D.
The cost of searching an AVL tree is θ (n log n) but that of a binary search tree is O(n)
Attempted by 381 students.
Show answer & explanation
Correct answer: A
Answer: The statement that an AVL tree has search cost Θ(log n) while a binary search tree can have search cost O(n) is correct.
Key points:
AVL tree: It is a height-balanced binary search tree (balance factor maintained at each node). Its height is Θ(log n), so search (and insert/delete) are guaranteed Θ(log n).
Binary search tree (BST): If the BST is unbalanced (e.g., nodes inserted in sorted order), it can become a chain of height n, giving worst-case search time O(n).
Average-case BST: With random insertions or if the tree is approximately balanced, the height is Θ(log n) and average search is Θ(log n). The worst-case bound remains O(n).
Complete binary tree: Its height is Θ(log n), so searching (following parent/child pointers down the tree) costs Θ(log n), not Θ(n log n).
Conclusion: The correct complexity facts are: AVL search is Θ(log n); a general BST can be O(n) in the worst case (but Θ(log n) on average if balanced); searching a complete binary tree is Θ(log n). The first given statement matches these facts.
A video solution is available for this question — log in and enroll to watch it.