2020/07/27 by Addario-Berry, Louigi, Corsini, Benoît · 1 citation
#60C05. Secondary: 05A05 #60F05 #60F15 #60K35 #82B23 #82B26 #Combinatorics (math.CO) #FOS: Mathematics #Primary: 60B15 #Probability (math.PR)
paper · doi:10.48550/arxiv.2007.13728
Random binary search trees are obtained by recursively inserting the elements σ(1),σ(2),…,σ(n) of a uniformly random permutation σ of [n]=\1,…,n\ into a binary search tree data structure. Devroye (1986) proved that the height of such trees is asymptotically of order c^*log n, where c^*=4.311… is the unique solution of c log((2e)/c)=1 with c ≥ 2. In this paper, we study the structure of binary search trees Tn,q built from Mallows permutations. A \textrmMallows(q) permutation is a random permutation of [n]=\1,…,n\ whose probability is proportional to q^\textrmInv(σ), where \textrmInv(σ) = #\i < j: σ(i) > σ(j)\. This model generalizes random binary search trees, since \textrmMallows(q) permutations with q=1 are uniformly distributed. The laws of Tn,q and Tn,q-1 are related by a simple symmetry (switching the roles of the left and right children), so it suffices to restrict our attention to q≤1. We show that, for q∈[0,1], the height of Tn,q is asymptotically (1+o(1))(c^* log n + n(1-q)) in probability. This yields three regimes of behaviour for the height of Tn,q, depending on whether n(1-q)/log n tends to zero, tends to infinity, or remains bounded away from zero and infinity. In particular, when n(1-q)/log n tends to zero, the height of Tn,q is asymptotically of order c^*log n, like it is for random binary search trees. Finally, when n(1-q)/log n tends to infinity, we prove stronger tail bounds and distributional limit theorems for the height of Tn,q.