论文标题
绿树的高度
The height of Mallows trees
论文作者
论文摘要
随机二进制搜索树是通过递归将元素$σ（1），σ（2），\ ldots，σ（n）$的元素$σ（n）$ $σ（n）$ [n] = n] = \ {1，\ dots，n \} $插入二元搜索树数据结构的。 Devroye（1986）证明了此类树的高度在$ c^*\ log n $的顺序上，其中$ c^*= 4.311 \ ldots $是$ c \ log（（2e）/c）= 1 $的唯一解决方案，带有$ c \ geq 2 $。在本文中，我们研究了二进制搜索树的结构$ t_ {n，q} $从木匠排列中构建的$。 a $ \ textrm {mallows}（q）$排列是$ [n] = \ {1，\ ldots，n \} $的随机排列，其概率与$ q^{\ textrm {invt}（inv}（σ）}（σ）} $，wher σ（j）\} $。该模型概括了随机二进制搜索树，因为$ \ textrm {mallows}（q）$ $ q = 1 $的排列是均匀分布的。 $ t_ {n，q} $和$ t_ {n，q^{ - 1}} $的定律与简单的对称性相关（切换左和右子女的角色），因此足以将注意力限制在$ q \ leq1 $上。 我们表明，对于[0,1] $中的$ q \，$ t_ {n，q} $的高度是渐近$（1 + o（1））（c^* \ log n + n + n + n + n（1-q））$。这产生了$ t_ {n，q} $的高度的三个行为制度，具体取决于$ n（1-q）/\ log n $趋于零，倾向于无穷大，还是远离零和无穷大。特别是，当$ n（1-q）/\ log n $趋于零时，$ t_ {n，q} $的高度是渐近的$ c^*\ log n $，就像是随机二进制搜索树一样。最后，当$ n（1-q）/\ log n $倾向于无穷大时，我们证明了$ t_ {n，q} $的高度的尾部界限和分布限制定理。
Random binary search trees are obtained by recursively inserting the elements $σ(1),σ(2),\ldots,σ(n)$ of a uniformly random permutation $σ$ 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}(σ)}$, where $\textrm{Inv}(σ) = \#\{i < j: σ(i) > σ(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}$.
