Aspects of the Search Time in Binary Search Trees Modified According to the Move-to-Root Heuristic

摘要

The search time in a binary search tree organized according to the self-organizing move-to-root heuristic is considered. Supposing that the records in the tree are requested independently with constant probabilities, the mean, variance and two different (but equivalent) expressions for the generating function for the search time in stationarity are derived by embedding in Poisson processes. We look for the 'worst' request probabilities, i.e., those that maximize the search time, and rearrange them into a 'best' permutation that minimizes the search time. Mean, variance and probability functions are computed numerically for some illustrating request probability distributions and their 'best' and 'worst' permutations. Finally, an approximating distribution is found for the search time in the special case arising when all of the request probabilities are equal.