scientific article; zbMATH DE number 4027493

From MaRDI portal
Publication:3768922





[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.











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)