On a random search tree: asymptotic enumeration of vertices by distance from leaves

Abstract: A random binary search tree grown from the uniformly random permutation of

[n]

is studied. We analyze the exact and asymptotic counts of vertices by rank, the distance from the set of leaves. The asymptotic fraction

c_{k}

of vertices of a fixed rank

k g e 0

is shown to decay exponentially with

k

. Notoriously hard to compute, the exact fractions

c_{k}

had been determined for

k l e 3

only. We computed

c_{4}

and

c_{5}

as well; both are ratios of enormous integers, denominator of

c_{5}

being

274

digits long. Prompted by the data, we proved that, in sharp contrast, the largest prime divisor of

c_{k}

's denominator is

2^{k + 1} + 1

at most. We conjecture that, in fact, the prime divisors of every denominator for

k > 1

form a single interval, from

2

to the largest prime not exceeding

2^{k + 1} + 1

.

Recommendations

Cites Work

Cited In (7)

This page was built for publication: On a random search tree: asymptotic enumeration of vertices by distance from leaves