Abstract

For any fixed integer $d\geq 2$, the $d$-ary increasing tree is a rooted, ordered, labeled tree where the out-degree is bounded by $d$, and the labels along each path beginning at the root increase. Total path length, or search cost, for a rooted tree is defined as the sum of all root-to-node distances and the Sackin index is defined as the sum of the depths of its leaves. We study these quantities in random $d$-ary increasing trees.

Keywords: $d$-ary increasing tree; total path length; Sackin index; covariance.

MSC: 05C05, 60F05

Pages:  55--62     

Volume  73 ,  Issue  1 ,  2021