EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

Heights of Butterfly Trees

John Peca‐Medlin, Chenyang Zhong

Random Structures & Algorithms · 2026-05 · 68 (3)

DOI: 10.1002/rsa.70068 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 30.04.2026. Verfasst von John Peca‐Medlin und 1 weiteren Autor:innen. Die Arbeit nennt 48 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 .

Zitieren

APA

Peca‐Medlin, J., & Zhong, C. (2026). Heights of Butterfly Trees. Random Structures & Algorithms, 68(3). https://doi.org/10.1002/rsa.70068

Vancouver

Peca‐Medlin J, Zhong C. Heights of Butterfly Trees. Random Structures & Algorithms. 2026;68(3). doi:10.1002/rsa.70068

BibTeX
@article{PecaMedlin2026,
  author = {Peca‐Medlin, John and Zhong, Chenyang},
  title = {Heights of Butterfly Trees},
  journal = {Random Structures & Algorithms},
  year = {2026},
  volume = {68},
  number = {3},
  doi = {10.1002/rsa.70068}
}
Kostenlos starten →