2025/07/06 by Peca-Medlin, John, Zhong, Chenyang · 1 citation
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2507.04505
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 hn of a random BST satisfies hn / log n → c^* ≈ 4.311, we show that block BSTs with nm nodes and fixed external size m satisfy hn,m / log n → c^* + hm in distribution. We then study butterfly trees: BSTs generated from permutations built using iterated Kronecker or wreath products. For simple butterfly trees (from iterated Kronecker products of S2), we give a full distributional description showing polynomial height growth: 𝔼 hnB = Θ(Nα) with α= log2(3/2) ≈ 0.58496. For nonsimple butterfly trees (from wreath products), we prove power-law bounds: cNα⋅ (1 + o(1)) ≤ 𝔼 hnB ≤ dNβ⋅ (1 + o(1)), with β≈ 0.913189.