What is the range of β in finding the length of the longest path in a randomized binary search tree?

Category: QuestionsWhat is the range of β in finding the length of the longest path in a randomized binary search tree?
Editor">Editor Staff asked 4 weeks 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 4 weeks 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).