أفضل الأحوال "الانحراف ارتفاع" التعسفي شجرة

Question

نظرا التعسفي شجرة ثنائية على $n$ العقد ، اختر مهمة $A$ من كل من الوالدين أن أحد الأطفال ("رعاية الطفل" كما كانت).تعريف الانحراف ارتفاع الشجرة كما $H_A(\mathsf{النيل})=0$ و $H_A(\mathsf{عقدة}\;a\b)=\ماكس(H_A(أ) ، H_A(ب)+1)$ إذا $A(\mathsf{عقدة}\;a\b)=a$ هو يفضل الطفل بشكل متناظر $\ماكس(H_A(أ)+1, H_A(ب))$ إذا $b$ هو فضل.

السؤال هو:ثابت شجرة $T$, ما هو الحد الأدنى من الانحراف الارتفاع فوق كل الواجبات ؟ وأود أن الحصول على مقارب ملزمة على $f(n)=\max_{|T|=n}\min_AH_A(T)$.

نماذج أخرى على هذه المشكلة أنا مهتم في حين الأشجار ليست الثنائية (ولكن لا يزال هناك واحد يفضل الطفل وجميع الآخرين إضافة إلى ارتفاع), وعندما يكون هناك تقاسم (أيوهو داغ), التي لا تؤثر على ارتفاع حساب ولكن يسمح أوسع بكثير "الأشجار" في حين أن البقاء تحت $n$ عقدة ملزمة.

واضح حدود $f(n)=\Omega(\log n)$ و $f(n)=O(n)$.تخميني هو أن $f(n)= heta(\log n)$ على الأشجار الثنائية ، $f(n)= heta(\sqrt ن)$ بالنسبة dags (مع بعض نوع من الشبكة الرسم البياني كما بالدليل).

Answer 1

عن شجرة ثنائية ، والسماح $H(T)=\min_AH_A(T)$, حيث $A$ نطاقات على جميع يفضل الطفل الاحالات $T$.الاتصال $H(T)$ على الانحراف ارتفاع $T$.

هنا هو ملاحظة بسيطة.الانحراف ذروة الكمال الثنائية شجرة (العادية) ارتفاع $n$ هو $n$, أيضا.

عن شجرة ثنائية $T$, وحافة يسمى يمر حافة إن واحدة من نقاط النهاية بالضبط طفل واحد.ونحن ندعو شجرة ثنائية $م$ ب-القصر $T$ إذا $م$ يمكن الحصول عليها عن طريق إزالة الشجرة أو التعاقد مع مرور حافة مرارا وتكرارا.

عن شجرة ثنائية $T$, ما هو الانحراف الارتفاع ؟ هنا هو البصري توصيف.

الانحراف ارتفاع $T$ هو الحد الأقصى (العادية) ارتفاع كل الكمال الأشجار الثنائية التي هي أيضا ب-القصر من $T$. حدسي يتحدث شجرة ثنائية من الانحراف ارتفاع $s$ $\المنتدى$ أنه "يحتوي على" الكمال شجرة ثنائية العاديين ارتفاع $s$.

برهان. لأن كلا إزالة الشجرة و التعاقد مع مرور حافة لا تزيد الانحراف الارتفاع ، $$H(T)\ge \max_{M ext{ هو b-ثانوية T}}\mathsf{الطول}(M),$$ حيث $\mathsf{الطول}(\cdot)$ هو (العادية) ارتفاع شجرة.من ناحية أخرى, من خلال الحث على عدد من العقد $T$, يمكننا أن نبين أن شجرة ثنائية من الانحراف ارتفاع $s$ يجب أن يحتوي على b-الطفيفة التي هي مثالية شجرة ثنائية العاديين ارتفاع $s$. $\quad\علامة$.

---

يذكر أن $n$ هو عدد العقد في $T$.لدينا ، $$H(T) \لو \lceil \log_2(n+1) ceil - 1.$$ برهان. الحث على $n$.الحالة الأساسية ، $n = 1$ من السهل أن تحقق.

لنفترض أن هذا صحيح إذا كان عدد العقد في $T$ هو أصغر من $n$.النظر في شجرة ثنائية $T$ من $n$ العقد مع عقدة الجذر $r$.

• إذا $r$ لديها طفل واحد فقط ، كما يقول ، $a$, ثم $$H(T)=ح( ext{الشجرة متجذرة في } أ)\لو \lceil \log_2((n-1)+1) ceil - 1\لو \lceil \log_2(n+1) ceil - 1.$$
• إذا $r$ اثنين من الأطفال ، كما يقول ، $a$ و $b$.منذ عدد العقد في الشجرة ذات الجذور في $a$ و الشجرة ذات الجذور في $b$ هو $n-1$, واحدة من الأشجار الفرعية في معظم $\lfloor (n-1)/2 floor$ العقد.WLOG ، لنفترض انها الشجرة ذات الجذور في $b$.ثم $$H(T)=\ماكس(ح( ext{الشجرة متجذرة في }أ ) + 1, ح( ext{الشجرة متجذرة في } ب)) \\ \لو \ماكس(\lceil \log_2(\lfloor(n-1)/2 floor+1) ceil,\lceil \log_2((n-2)+1) ceil -1) $$ منذ $$ \lceil \log_2(\lfloor(n-1)/2 floor+1) ceil=\lceil \log_2(\lfloor(n+1)/2 floor) ceil=\lceil \log_2(n+1) ceil-1,$$ لدينا $H(T)\لو \lceil \log_2(n+1) ceil-1.$ $\quad\علامة$

---

يذكر أن $f(n)=\max_{T ext{ هو ثنائي الشجرة }|T|=n}H(T)$.المقطع أعلاه أثبت $f(n)\لو \lceil\log_2(n+1) ceil-1$.

ومن ناحية أخرى ، فإن الانحراف الوزن المثالي شجرة ثنائية مع $2^m-1$ عقدة $m-1$.ومن ثم ، $$f(n)=\lceil\log_2(n+1) ceil-1.$$