Editor">
Editor Staff asked 5 months ago
Editor Staff asked 5 months ago
What is the range of β in finding the length of the longest path in a randomized binary search tree?
(a) (-1, 0)
(b) (1, 0)
(c) (0, 5)
(d) (0, 1)
I’d like to ask this question from Binary Trees in chapter Binary Trees of Data Structures & Algorithms I
The question was asked in semester exam.
1 Answers
Editor">Editor Staff answered 5 months ago
Editor Staff answered 5 months ago
Right option is (d) (0, 1)
The explanation is: The longest path in a randomized binary search tree, but it has been found that the longest length is around 4.311 log x for node x. This is also equal to 1/β log x where β lies in the range (0, 1).
