Optimal binary trees with order constraints

DOI10.1016/S0166-218X(98)00138-3MaRDI QIDQ1283811zbMATH OpenOpenAlexWikidataFDO

Authors András Sebö, Z. Waksman

Publication date 30 March 1999

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(98)00138-3

zbMATH Keywords

algorithmbinary treeoptimal decomposition

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

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.

Recommendations

• Optimal leaf ordering of complete binary trees
• Optimal binary search trees
• Optimal binary search trees
• Height Restricted Optimal Binary Trees
• Binary search trees of almost optimal height
• scientific article; zbMATH DE number 1456949
• Binary Trees and (Maximal) Order Types
• Optimal binary split trees
• scientific article; zbMATH DE number 15358

Cites work

• A Fast Selection Algorithm and the Problem of Optimum Distribution of Effort
• A linear-time algorithm for a special case of disjoint set union
• A Method for the Construction of Minimum-Redundancy Codes
• Applications of Path Compression on Balanced Trees
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems
• On an optimization problem with nested constraints
• Optimal Computer Search Trees and Variable-Length Alphabetical Codes
• The complexity of selection and ranking in X+Y and matrices with sorted columns

Cited in

(12)

• Partial-order analogue of the secretary problem: The binary tree case
• Minimax trees in linear time with applications
• Optimal leaf ordering of complete binary trees
• scientific article; zbMATH DE number 4135962 (Why is no real title available?)
• Height Restricted Optimal Binary Trees
• Ranking the Best Binary Trees
• Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums
• Restructuring ordered binary trees
• scientific article; zbMATH DE number 1445337 (Why is no real title available?)
• Assigning bookmarks in perfect binary trees.
• The Optimization of Signed Trees
• Optimal binary search trees

This page was built for publication: Optimal binary trees with order constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1283811)