Optimal binary trees with order constraints (Q1283811)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Optimal binary trees with order constraints |
scientific article; zbMATH DE number 1271083
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Optimal binary trees with order constraints |
scientific article; zbMATH DE number 1271083 |
Statements
Optimal binary trees with order constraints (English)
0 references
30 March 1999
0 references
An \(O(q)\)-algorithm is designed for the following problem: given a sequence of numbers \(a_1,\dots, a_q\), construct a binary tree with \(q\) leaves minimizing \(\max\{h_1+ a_1,\dots, h_q+ a_q\}\), where \(h_i\) is the distance from the \(i\)th leaf to the root, \(i= 1,\dots, q\). A sharp upper bound for the minimum is given by an explicit formula.
0 references
optimal decomposition
0 references
algorithm
0 references
binary tree
0 references
0 references
0 references
0 references
0 references
0 references
0.90551627
0 references
0 references
0 references
