scientific article; zbMATH DE number 4027493
[For the entire collection see Zbl 0626.00008.] This paper deals with enumeration problems involving the register function of a binary tree. This function is defined recursively as: \(reg(T)=0\) if T is a leaf (a one-node tree); assuming \(r_ 1\), \(r_ 2\) are the register numbers of the left and right subtrees of the root of T, then \(reg(T)=\max \{r_ 1,r_ 2\}\) if \(r_ 1\neq r_ 2\) and \(=r_ 1+1\) if \(r_ 1=r_ 2\). A node is called critical if its two subtrees have equal register numbers. The register path length rpl(T) of a binary tree T is the number of critical nodes on the path from the root to an internal node, summed over all internal nodes. The author obtains, using generating functions, that the average register path length of an n-node binary tree is asymptotically equal to (1/6)n log\({}_ 2n\). Several similar asymptotic results are obtained.
- Efficient computation of the iteration of functions
- On a problem of Yekutieli and Mandelbrot about the bifurcation ratio of binary trees
- Reductions of binary trees and lattice paths induced by the register function
- Random self-similar trees: a mathematical theory of Horton laws
- The register function for \(t\)-ary trees
- The register function for lattice paths
- scientific article; zbMATH DE number 3872676 (Why is no real title available?)
- scientific article; zbMATH DE number 3896954 (Why is no real title available?)
- Register Allocation for Unary–Binary Trees
- On the average number of registers needed to evaluate a special class of backtrack trees
- The register function and reductions of binary trees and lattice paths
- Solution of a problem of Yekutieli and Mandelbrot
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3768922)