Extremal properties of ?-weighted binary trees (Q3817628)
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 4090820
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Extremal properties of ?-weighted binary trees |
scientific article; zbMATH DE number 4090820 |
Statements
Extremal properties of ?-weighted binary trees (English)
0 references
1987
0 references
weighted tree
0 references
joint file processing
0 references
binary tree
0 references
external path length
0 references
0.8280355334281921
0 references
0.8266938924789429
0 references
A directed binary tree is a directed tree in which the out-degree of any vertex is 0 or 2. Vertices with out-degree equal to 2 are called internal vertices, and those with out-degree equal to 0 are called leaves. The level of a vertex is the length of the path from the root to the vertex. Let \({\mathfrak D}_ n\) be the set of all directed binary trees with \(n\geq 1\) leaves. On the vertices of a tree \(D_ n\in {\mathfrak D}_ n\) functions \(\mu_{\alpha}\) and \(\sigma '_{\alpha}\) are defined recursively: \(\mu_{\alpha}(x)=1\), if x is a leaf, \(\mu_{\alpha}(x)=\alpha (\mu_{\alpha}(x_ 1)+\mu_{\alpha}(x_ 2))\) otherwise, and \(\sigma '_{\alpha}(x)=\mu_{\alpha}(x)\) if x is a leaf, \(\sigma '_{\alpha}(x)=\mu_{\alpha}(x)+\sigma '_{\alpha}(x_ 1)+\sigma '_{\alpha}(x_ 2)\) otherwise, where \(x_ 1\) and \(x_ 2\) are the vertices reached by arcs from x, and \(\alpha >0\). The values of \(\mu_{\alpha}\) and \(\sigma '_{\alpha}\) at the root of the tree \(D_ n\) are denoted, respectively, by \(\mu_{\alpha}(D_ n)\) and \(\sigma '_{\alpha}(D_ n)\). Let \(\sigma_{\alpha}(D_ n)=\sigma '_{\alpha}(D_ n)-\mu_{\alpha}(D_ n).\) The weight of an arc entering the vertex x is the value \(\mu_{\alpha}(x)\), and the \(\alpha\)- weighted external path length of \(D_ n\) is the sum of the weights of all the tree arcs. The \(\alpha\)-weighted external path length of a tree \(D_ n\) is equal to \(\sigma_{\alpha}(D_ n)\). The 1-weighted external path length is just the external path length considered in [\textit{D. E. Knuth}, The art of computer programming. Vol. 1: Functional algorithms (Addison-Wesley, Reading, Mass. 1968; Zbl 0191.179)]. For fixed \(\alpha\), a tree \(D_ n\) is said to be optimal in \({\mathfrak D}_ n\) if \(\sigma_{\alpha}(D_ n)\) is minimal. The author proves the following characterization of optimal trees: For \(0<\alpha <0.5\) an optimal tree is quasilinear; that is, all its internal vertices form a chain. For \(\alpha >0.5\) a tree is optimal in \({\mathfrak D}_ n\) if and only if it is completely balanced; that is, all leaves of the tree are on the maximal level or on the preceding level. For \(\alpha =0.5\) every tree in \({\mathfrak D}_ n\) is optimal. As a corollary the author obtains explicit formulas for the \(\alpha\)- weighted external path length of optimal trees. The author has investigated \(\alpha\)-weighted t-ary trees for any \(t\geq 2\) [Vestn. Beloruss. Gos. Univ. Im. V. I. Lenina, Ser. I 1986, No.2, 55-58 (1986)]. The results are useful for the evaluation of various strategies for the joint processing of files [\textit{G. A. Dobrushevich} and the author, ibid. 1983, No.1, 37-40 (1983)].
0 references