The height of Mallows trees

Louigi Addario-Berry, Benoît Corsini

Random binary search trees are obtained by recursively inserting the elements $\sigma (1),\sigma (2),\dots ,\sigma (n)$ of a uniformly random permutation $\sigma$ of $[n]=\{1,\dots ,n\}$ into a binary sea…