任意树的最佳案例“歪斜高度”

Question

给定 $ n $ 节点上的任意二叉树，从每个中选择分配 $ a $ 父母给其中一个孩子（“青睐孩子”是这样）。我们将树的偏斜高度定义为 $ h_a（\ mathsf {nil}）= 0 $ 和 $ h_a（\ Mathsf {node} \; a \; b）=max（h_a（a），h_a（b）+1）$ 如果 $ a（\ mathsf {node } \;一个\; b）= $ 是受欢迎的子女和对称 $ \ max（h_a（a）+1，h_a（b））$ 如果 $ b $ 是有利的。

问题是：对于固定的树 $ t $ ，所有作业的最小偏斜高度是多少？我想在 $ f（n）= max_ {| t |= n} \ min_ah_a（t）$ 上获得一个渐近绑定。

其他问题的变体是我感兴趣的是树木不是二进制（但仍然有一个有利的孩子，并且所有其他人都会增加一个到高度），并且当共享（即它是一个DAG）时，它不会影响高度计算，但允许在 $ n $ 节点绑定的同时保持更广泛的“树木”。

明显的界限是 $ f（n）=oomega（\ log n）$ 和 $ f（n ）= o（n）$ 。我的猜测是 $ f（n）=theta（\ log n）$ for二进制树， $ f（ n）=theta（\ sqrt n）$ 对于dag（具有某种网格图形为contenerexample）。

Answer 1

对于二进制树，让 $ h（t）=min_ah_a（t）$ ，其中 $ a $ 范围内所有受利于 $ t $ 的子项分配。调用 $ h（t）$ $ t $ 的 skew高度。

这是一个简单的观察。 （普通）高度 $ n $ 是 $ n $ 的完美二叉树的偏斜高度。

对于二进制树 $ t $ ，如果其中一个端点恰好一个孩子，则将边缘称为传递边缘。我们调用二进制树 $ m $ $ t $ 如果 $ M $ 可以通过反复删除子树或通过传递边缘来获得。

对于二进制树 $ t $ ，它的偏斜高度是多少？这是一个视觉表征。

$ t $ 是所有完美二叉树的最大（普通）高度也是 $ t $ 。直观地说，二进制树是偏斜高度 $ s $ $ \ iff $ 它”包含“普通高度的完美二叉树 $ s $ 。

证明。因为删除子树和收缩传递边缘都不会增加偏斜高度， $$ h（t）\ ge \ max_ { m \ text {是t} \ mathsf {height}（m），$$ 其中 $ \ mathsf {height}（\ cdot）$$ 是树的（普通）高度。另一方面，通过诱导 $ t $ 的节点数量，我们可以显示偏斜高度 $ s $ 必须包含一个b-minor，这是一个完美的普通高度的二叉树 $ s $ 。 $ \ quad \ checkmark $ 。

---

回想一下， $ n $ 是 $ t $ 中的节点数。我们有， $$ h（t）\ le \ lceil \ log_2（n + 1）\ rceil - 1。$$ 证明。 $ n $ 上的诱导。基本情况， $ n= 1 $ 易于验证。

假设如果 $ t $ 中的节点数量小于 $ n $ 。考虑二进制树 $ t $ $ n $ n $ n $ nodes，带有根节点 $ r $ 。

• 如果 $ r $ 只有一个孩子，例如 $ a $ ，那么 $$ h（t）= h（\ text {subetree overed at}）\ le \ lceil \ log_2（（n-1）+1）\ rceil - 1 \ le \ lceil \ log_2（n + 1）\ rceil - 1。$$
• 如果 $ r $ 有两个孩子，例如， $ a $ 和 $ B $ 。由于子树中的节点数为 $ a $ ，并且植根于 $ b $ 的子树 $ n-1 $ ，其中一个子树具有大多数 $ \ lfloor（n-1）/ 2 \ rfloor $ 节点。 WLOG，假设它是在 $ b $ 上的子树。然后 $$ h（t）=max（h（\ text {subeted areed areeded）+ 1，h（\ text {subtree overed areded} b））\\ \ Le \ Max（\ Lceil \ log_2（\ Lfloor（n-1）/ 2 \ rfloor + 1）\ rceil，\ lceil \ log_2（（n-2）+1）\ rceil -1）$$ 由于<跨度类=“math-container”> $$ \ lceil \ log_2（\ lfloor（n-1）/ 2 \ rfloor + 1）\ rceil=lceil \ log_2（\ lfloor（n + 1）/ 2 \ rfloor）\ rceil=lceil \ log_2（n + 1）\ rceil-1，$$ 我们有 $ h（t）\ le \ lceil \ log_2（n + 1）\ rceil-1。$ $ \ quad \ checkmark $

---

调用 $ f（n）=max_ {t \ text {是二进制树和} |= n} h（t）$ 。上述部分已证明 $ f（n）\ le \ lceil \ log_2（n + 1）\ rceil-1 $ 。

另一方面，使用 $ 2 ^ m-1 $ 节点是 $的完美二叉树的歪斜重量M-1 $ 。因此， $$ f（n）=lceil \ log_2（n + 1）\ rceil-1。$$