Which of the following is TRUE?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. The cost of searching an AVL tree is Θ(log n) but that of a binary search tree is O(n)
Explanation
An AVL tree stays balanced, so search is Θ(log n). An unbalanced BST can degenerate into a chain, giving O(n) search.More Data Structures and Algorithms questions
- What is the result of evaluating the postfix expression "4 3 * 2 5 * + 8 -"?
- Which data structure is typically used to implement a hash table?
- Which collision resolution technique involves maintaining a linked list of collided keys?
- Consider the following functions: f(n) = 3n√n, g(n) = 2√n log₂ n, h(n) = n!. Which of the following is true?
- 2-3-4 trees are B-trees of order 4. They are isometric to ______ trees.
- Consider the following statements about the heap sort algorithm: A. The MAX-HEAPIFY procedure, which runs in O(lg n) time, is the key to ma…