No label defined (Q3768922)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4027493
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4027493

      Statements

      0 references
      1987
      0 references
      enumeration
      0 references
      register function
      0 references
      binary tree
      0 references
      register path length
      0 references
      [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.
      0 references

      Identifiers