{"ID":2897969,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.04505","arxiv_id":"2507.04505","title":"Heights of butterfly trees","abstract":"Binary search trees (BSTs) are fundamental data structures whose performance is largely governed by tree height. We introduce a block model for constructing BSTs by embedding internal BSTs into the nodes of an external BST -- a structure motivated by parallel data architectures -- corresponding to composite permutations formed via Kronecker or wreath products. Extending Devroye's result that the height $h_n$ of a random BST satisfies $h_n / \\log n \\to c^* \\approx 4.311$, we show that block BSTs with $nm$ nodes and fixed external size $m$ satisfy $h_{n,m} / \\log n \\to c^* + h_m$ in distribution. We then study butterfly trees: BSTs with $N = 2^n$ nodes generated from permutations built using iterated Kronecker or wreath products. For simple butterfly trees (from iterated Kronecker products of $S_2$), we give a full distributional description showing polynomial height growth: $\\mathbb{E} h_n^{\\operatorname{B}} = Θ(N^α)$ with $α= \\log_2(3/2) \\approx 0.58496$. For nonsimple butterfly trees (from wreath products), we prove power-law bounds: $cN^α\\cdot (1 + o(1)) \\le \\mathbb{E} h_n^{\\operatorname{B}} \\le dN^β\\cdot (1 + o(1))$, with $β\\approx 0.913189$.","short_abstract":"Binary search trees (BSTs) are fundamental data structures whose performance is largely governed by tree height. We introduce a block model for constructing BSTs by embedding internal BSTs into the nodes of an external BST -- a structure motivated by parallel data architectures -- corresponding to composite permutation...","url_abs":"https://arxiv.org/abs/2507.04505","url_pdf":"https://arxiv.org/pdf/2507.04505v3","authors":"[\"John Peca-Medlin\",\"Chenyang Zhong\"]","published":"2025-07-06T18:42:02Z","proceeding":"math.PR","tasks":"[\"math.PR\",\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}