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^{\ast }\approx 4.311$, we show that block BSTs with $nm$ nodes and fixed external size $m$ satisfy $h_{n,m}/\log n\to c^{\ast }+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^B=\Theta (N^{\alpha })$ with $\alpha ={\log }_2(3/2)\approx 0.58496$. For nonsimple butterfly trees (from wreath products), we prove power-law bounds: $c{N}^{\alpha }\cdot (1+o(1))\le \mathbb{E}{h}_n^B\le d{N}^{\beta }\cdot (1+o(1))$, with $\beta \approx 0.913189$.