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
1987
0 references
enumeration
0 references
register function
0 references
binary tree
0 references
register path length
0 references
0.8777532577514648
0 references
0.8756990432739258
0 references
0.8478444814682007
0 references
0.8419312238693237
0 references
0.8391507267951965
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