Optimal binary trees with order constraints
type: Item
instance of: scholarly article
title: Optimal binary trees with order constraints
zbMATH Open document ID: 0920.05020
DOI: 10.1016/S0166-218X(98)00138-3
author: András Sebö
author: Z. Waksman
published in: Discrete Applied Mathematics
publication date: 1999-03-30T00:00:00Z
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.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1271083
zbMATH Keywords: optimal decomposition
zbMATH Keywords: algorithm
zbMATH Keywords: binary tree
reviewed by: G. Gutin
MaRDI profile type: Publication
cites work: On an optimization problem with nested constraints
cites work: The complexity of selection and ranking in X+Y and matrices with sorted columns
cites work: A linear-time algorithm for a special case of disjoint set union
cites work: A Fast Selection Algorithm and the Problem of Optimum Distribution of Effort
cites work: Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems
cites work: Optimal Computer Search Trees and Variable-Length Alphabetical Codes
cites work: A Method for the Construction of Minimum-Redundancy Codes
cites work: Q5585020
cites work: Applications of Path Compression on Balanced Trees
full work available at URL: s0166-218x(98)00138-3
OpenAlex ID: W2116505441
Wikidata QID: Q127363110
Recommended article: Optimal leaf ordering of complete binary trees
Recommended article: Optimal binary search trees
Recommended article: Height Restricted Optimal Binary Trees
Recommended article: Binary search trees of almost optimal height
Recommended article: Q4954438
Recommended article: Binary Trees and (Maximal) Order Types
Recommended article: Optimal binary split trees
Recommended article: Q3972002
description: scientific article; zbMATH DE number 1271083