Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R.
Assertion A: AVL trees are more balanced than red-black trees, but they may cause more rotations during insertion and deletion.
Reason R: A red-black tree with n nodes has height greater than 2 log₂(n + 1), and an AVL tree with n nodes has height less than log_φ(√5 (n + 2)) − 2 (where φ is the golden ratio).
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. A is true but R is false
Explanation
A is true. R is false: a red-black tree's height is at most 2 log₂(n + 1), not greater than it.More Data Structures and Algorithms questions
- Consider a hash table of size 7 with starting index 0 and hash function (6x + 3) mod 4. Assuming the table is initially empty, which of the…
- Match List I with List IIList I List II A. Running time of a straightforward recursive method to compute the nth Fibonacci number Fₙ I. O(n…
- Statement I: If f and g are two functions and f = O(g) but g ≠ o(f), we say that the growth rate of g is smaller than that of f. Statement…
- Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R. Assertion A: It is possible to create…
- For each function below, let n be the least integer such that f(x) is O(xⁿ). Arrange the functions in increasing order of n: A. f(x) = 3x³…
- f(n) = a·f(n/b) + g(n) is a divide-and-conquer recurrence. Match the algorithms in List I with their recurrences in List II.List I List II…