Abstract
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 of a random BST satisfies , we show that block BSTs with nodes and fixed external size satisfy in distribution. We then study butterfly trees : BSTs with nodes generated from permutations built using iterated Kronecker or wreath products. For simple butterfly trees (from iterated Kronecker products of ), we give a full distributional description showing polynomial height growth: with . For nonsimple butterfly trees (from wreath products), we prove power‐law bounds: , with .
Abstract from the paper’s OpenAlex record; open copy licensed cc-by-nc-nd. Read at the source ↗
The text the model read, with the source record’s inline markup (italics, sub- and superscripts) rendered and its character entities decoded; quote offsets refer to the raw text.
Claims 0
Judged off_topic: no plant question — claims were not extracted. This is a scope decision by the model, not a statement about the paper’s findings.