An extended result of Kleitman and Saks concerning binary trees
type: Item
instance of: scholarly article
title: An extended result of Kleitman and Saks concerning binary trees
zbMATH Open document ID: 0567.68039
DOI: 10.1016/0166-218X(85)90047-2
author: Yongjin Zhu
published in: Discrete Applied Mathematics
publication date: 1985-01-01T00:00:00Z
review text: In a recent paper, \textit{D. J. Kleitman} and \textit{M. E. Saks} [SIAM J. Alg. Discrete Meth. 2, 142-146 (1981; Zbl 0498.68038)] gave a proof of Huang's conjecture on alphabetic binary trees. Given a set \(E=\{e_ i\}\), \(i=0,1,2,...,m\) and assigned positive weights to its elements and supposing the elements are indexed such that \(w(e_ 0)\leq w(e_ 1)\leq...\leq w(e_ m)\), where \(w(e_ i)\) is the weight of \(e_ i\), we call the following sequence \(E^*\) a 'saw-tooth' sequence \(E^*=(e_ 0,e_ m,e_ 1,...,e_ j,e_{m-j},...)\). Huang's conjecture is: \(E^*\) is the most expensive sequence for alphabetic binary trees. This paper shows that this property is true for the L-restricted alphabetic binary trees, where L is the maximum length of the leaves and \(\lceil \log_ 2(m+1)\rceil \leq L\leq m\).
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 3905858
zbMATH Keywords: Huang's conjecture
zbMATH Keywords: alphabetic binary trees
MaRDI profile type: Publication
cites work: Set Orderings Requiring Costliest Alphabetic Binary Trees
cites work: Optimal Computer Search Trees and Variable-Length Alphabetical Codes
cites work: Some results on Hu's conjecture concerning binary trees
Recommended article: The extended Cantor-Bendixson analysis of trees
Recommended article: A tree version of Kőnig's theorem
Recommended article: A version of the Loebl-Komlós-Sós conjecture for skew trees
Recommended article: Q3765795
Recommended article: Q4894966
Recommended article: An extension to trees of the Sardinas and Patterson algorithm
Recommended article: A Borg–Levinson theorem for trees
Recommended article: The Cantor-Bendixson Analysis of Finite Trees
Recommended article: An almost sure result for path lengths in binary search trees
description: scientific article; zbMATH DE number 3905858