  Random binary search trees are obtained by recursively inserting the elements
$\sigma(1),\sigma(2),\ldots,\sigma(n)$ of a uniformly random permutation
$\sigma$ of $[n]=\{1,\dots,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\ldots$ is the unique solution of $c
\log((2e)/c)=1$ with $c \geq 2$. In this paper, we study the structure of
binary search trees $T_{n,q}$ built from Mallows permutations. A
$\textrm{Mallows}(q)$ permutation is a random permutation of
$[n]=\{1,\ldots,n\}$ whose probability is proportional to
$q^{\textrm{Inv}(\sigma)}$, where $\textrm{Inv}(\sigma) = \#\{i < j: \sigma(i)
> \sigma(j)\}$. This model generalizes random binary search trees, since
$\textrm{Mallows}(q)$ permutations with $q=1$ are uniformly distributed. The
laws of $T_{n,q}$ and $T_{n,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\leq1$.
  We show that, for $q\in[0,1]$, the height of $T_{n,q}$ is asymptotically
$(1+o(1))(c^* \log n + n(1-q))$ in probability. This yields three regimes of
behaviour for the height of $T_{n,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
$T_{n,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
$T_{n,q}$.
