Mathematicians discover hidden patterns in how data structures grow
Researchers have mapped the mathematical rules governing how tree-shaped data structures develop, revealing that their complexity grows far slower than previously thought. The findings could improve how engineers design algorithms for everything from databases to network systems, potentially making data processing faster and more predictable at scale.
Originaltitel: The distribution of the maximum protection number in simply generated trees
<p>The protection number of a vertex v in a tree is the length of the shortest path from v to any leaf contained in the maximal subtree where v is the root. In this paper, we determine the distribution of the maximum protection number of a vertex in simply generated trees, thereby refining a recent result of Devroye, Goh, and Zhao. Two different cases can be observed: if the given family of trees allows vertices of outdegree 1, then the maximum protection number is on average logarithmic in the tree size, with a discrete double-exponential limiting distribution. If no such vertices are allowed, the maximum protection number is doubly logarithmic in the tree size and concentrated on at most two values. These results are obtained by studying the singular behaviour of the generating functions of trees with bounded protection number. While a general distributional result by Prodinger and Wagner can be used in the first case, we prove a variant of that result in the second case. </p>