Scholarlink

<p>Tree balance plays an important role in various research areas in phylogenetics and computer science. Typically, it is measured with the help of a balance index or imbalance index. There are more than 25 such indices available, recently surveyed in a book by Fischer et al. They are used to rank rooted binary trees on a scale from the most balanced to the least balanced. We show that a wide range of subtree-size based measures satisfying concavity and monotonicity conditions are minimized by the complete or greedy from the bottom (GFB) tree and maximized by the caterpillar tree, yielding an infinitely large family of distinct new imbalance indices. Answering an open question from the literature, we show that one such established measure, the <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11538_2025_1522_Article_IEq1.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="12" /> </InlineMediaObject> <EquationSource Format="TEX">\(\widehat{s}\)</EquationSource> <EquationSource Format="MATHML"><math> <mover accent="true"> <mi>s</mi> <mo stretchy="true">^</mo> </mover> </math></EquationSource> </InlineEquation>-shape statistic, has the GFB tree as its unique minimizer. We also provide an alternative characterization of GFB trees, showing that they are equivalent to complete trees, which arise in different contexts. We give asymptotic bounds on the expected <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11538_2025_1522_Article_IEq1.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="12" /> </InlineMediaObject> <EquationSource Format="TEX">\(\widehat{s}\)</EquationSource> <EquationSource Format="MATHML"><math> <mover accent="true"> <mi>s</mi> <mo stretchy="true">^</mo> </mover> </math></EquationSource> </InlineEquation>-shape statistic under the uniform and Yule-Harding distributions of trees, and answer questions for the related <i>Q</i>-shape statistic as well.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

The GFB Tree and Tree Imbalance Indices

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年9月5日

查看全文
  • Sean Cleary,
  • Mareike Fischer,
  • Katherine St. John

摘要

Tree balance plays an important role in various research areas in phylogenetics and computer science. Typically, it is measured with the help of a balance index or imbalance index. There are more than 25 such indices available, recently surveyed in a book by Fischer et al. They are used to rank rooted binary trees on a scale from the most balanced to the least balanced. We show that a wide range of subtree-size based measures satisfying concavity and monotonicity conditions are minimized by the complete or greedy from the bottom (GFB) tree and maximized by the caterpillar tree, yielding an infinitely large family of distinct new imbalance indices. Answering an open question from the literature, we show that one such established measure, the \(\widehat{s}\) s ^ -shape statistic, has the GFB tree as its unique minimizer. We also provide an alternative characterization of GFB trees, showing that they are equivalent to complete trees, which arise in different contexts. We give asymptotic bounds on the expected \(\widehat{s}\) s ^ -shape statistic under the uniform and Yule-Harding distributions of trees, and answer questions for the related Q-shape statistic as well.