任意の木のベストケース「スキュー高さ」

Question

$ n $ ノード上の任意のバイナリツリーを指定して、それぞれの割り当て $ a $ を選択します。その子供の一人に親（「好尚な子供」）ツリーのスキュー高さを $ h_a（\ mathsf {nil}）= 0 $ と $ h_a（\ mathsf {node} \; a \; b）=max（h_a（a）、h_a（b）+1）$ $ a（\ mathsf {ノード\; a \; b）= $ は、好意的な子と対称的に $ \ max（h_a（a）+ 1、h_a（b））$ $ b $ が好ましい場合は

質問は次のとおりです。 $ t $ の場合、すべての割り当てに対する最小スキューの高さは何ですか？ $ f（n）=max_ {| t |= n} \ min_ah_a（t）$ の漸近的なバインドを取得したいと思います。

その他のバリエーション私が興味を持っているのは、木がバイナリではないとき（しかし、まだ1つの好意的な子供があり、他のすべての人が身長に追加されています）、そして共有があるとき（それはDAGです）。これは高さ計算に影響を与えませんが、 $ n $ ノードバインドの下に滞在しながら、はるかに広い「木」を可能にします。

明らかな境界は $ f（n）=omega（\ log n）$ と $ f（n ）= o（n）$ 。私の推測は、バイナリツリーの $ f（n）=theta（\ log n）$ 、 $ f（ n）=theta（\ sqrt n）$ は（ある種のグリッドグラフをConterExampleとして）。

Answer 1

バイナリツリーの場合、 $ h（t）=min_ah_a（t）$ 、ここで $ a $ $ t $ のすべての好ましい子の割り当てに沿って及びます。 $ h（t）$ $ t $ の skewの高さを呼び出します。

これは簡単な観察です。 （通常）height $ n $ の完璧なバイナリツリーのスキュー高さは、 $ n $ です。 。

バイナリツリー $ t $ の場合、エンドポイントの1つが1つの子にある場合、エッジは渡されたエッジと呼ばれます。バイナリツリー $ m $ b-minor $ t $ " $ m $ は、サブツリーを削除したり、繰り返し通過エッジを縮小することで入手できます。

バイナリツリー $ t $ 、そのスキューの高さは何ですか？これは視覚的な特徴付けです。

$ t $ のスキュー高さは、 $ T $ 。直感的に言えば、バイナリツリーはスキュー高さ $ s $ $ \ IFF $ 普通の高さ $ s $ の完璧なバイナリツリーを"含んでいます "。

証明書サブツリーを取り外し、渡り刃を縮小するのはスキュー高さ、 $$ h（t）\ max_ { m \ text {b-minor}} \ mathsf {高さ}（m）、$$ ここで、 $ \ mathsf {height}（\ cdot）$ は木の（通常）高さです。一方、 $ t $ のノード数を誘導することで、スキュー高さ $ s $ は、通常の高さ $ s $ の完璧なバイナリツリーです。 $ \ quad \ checkmark $ 。

---

$ n $ は、 $ t $ のノード数です。我々は持っています、 $$ h（t）\ le \ lceil \ log_2（n + 1）\ Rceil - 1 $$ 証明 $ n $ の誘導。基本ケース、 $ n= 1 $ は検証が簡単です。

$ t $ のノード数が $ n $ より小さい場合、trueとしたとします。 。 $ t $ のバイナリツリー $ R $ 。

• $ R $ の場合、 $ a $ 、 $$ h（t）= h（\ text {reot the}} a）\ le \ lceil \ log_2（（n-1）+ 1）\ Rceil - 1 \ le \ lceil \ log_2（n + 1）\ RCEIL - 1。$$
• $ r $ の場合、 $ a $ と $ b $ 。 $ a $ に根ざしたサブツリーのノード数、および $ b $ に根ざしたサブツリーは $ n-1 $ 、サブツリーの1つが $ \ lfloor（n-1）/ 2 \ rforoor $です。 ノードwlog、 $ b $ に根ざしたサブツリーであるとします。それから $$ h（t）=max（h（\ text {rootused}} a）+ 1、h（\ text {} b）））\\ \ le \ max（\ lceil \ log_2（\ lceil \ log_2（\ lceil \ log_2（\ lforo（n-1）/ 2 \ rforoor + 1）\ Rceil、\ Lceil \ Log_2（（N-2）+ 1）\ RCEIL -1）$$ $$ \ 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 {2進数ツリー、} | t |= 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。$$