Question

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.

Answer 1

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).