This paper deals with register functions, which were introduced by Ershov. This function is equivalent to the Strahler number introduced by hydrogeologists. The function is recursively defined by reg[root] = 0, and, if a binary tree T has subtrees T1 and T2, then reg(T) = max{reg(T1), reg(T2)}, provided reg(T1) ≠ = reg(T2); otherwise it is 1 + reg(T1).
Register functions measure the number of registers needed to evaluate a binary tree, representing an arithmetic expression. When using the optimal strategy, the internal nodes represent the binary operators and the external nodes represent the operands. Intuitively, such a strategy implies the computation of the more complicated subtrees before the computation of the easier subtrees. If both the subtrees are equally difficult, the number of registers is simply one more than that required to compute any of the subtrees. Assuming all binary trees with n nodes to be equally likely, the average value of the register function was found earlier to be log4 n + O(1).
A recent result by Auber et al. has introduced a generalization of the register functions to t-ary rooted trees. The recursive definition of the register function for such trees is as follows: reg[root] = 0, and if the register functions for the subtrees T1, . . ., Tt are written in nondecreasing order as c1 ≥ c2 ≥ . . . ≥ ct ( t = maximum number of descendants), then the register function of the tree T is given by reg(T) = max {c1, c2 + 1, &, c2 + t - 1}. This paper shows that the average value of the register function for the t-ary trees is log4 n + O(1), provided that all such trees with n nodes are equally likely, and the set of possible out-degrees in the tree is finite. Thus, the register function is independent of the structure of the tree, but dependent only on the number of nodes in the tree.
In the attempt to prove the general result, the paper considers a generating function for the number of t-ary trees, paying attention to the number of internal nodes only. Through Lagrange inversion, the number of t-ary trees with n (internal) nodes is obtained. Finally, recursion on the generating function is used to derive an expression for the expected number of t-ary trees with n internal nodes. Exponential tail estimates for the distribution of the register function were computed, and the distribution was found to be concentrated mostly around the mean value.
