الوقت تعقيد خوارزمية لإيجاد أدنى سلف مشترك من جميع أعمق الأوراق

Question

هذا هو بيان المشكلة صادفت اليوم.

بالنظر إلى شجرة ثنائية, العثور على أدنى سلف مشترك من جميع أعمق الأوراق.

لقد جاء مع خوارزمية الصحيحة, ولكن أود أن أؤكد وقت تشغيل هذا النهج.

الخوارزمية هي على النحو التالي:

1. اجتياز شجرة والعثور على مستوى أعمق من الشجرة ، dmax.
2. اجتياز شجرة والعثور على جميع الأوراق في العمق dmax.
3. بالنظر إلى أن LCA(أ ، ب ، ج) = تحليل دورة الحياة(LCA(A,B),ج), اجتياز كافة العقد الموجودة في الخطوة 2 و حساب المخصص.

الروتين الفرعي على LCA(أ ، ب) هو بسيط.ابتداء من الساعة A, ، يذهب كل وسيلة تصل إلى الجذر و تخزين كل بزيارة عقدة في hashset.ثم تبدأ في ب, اذهب حتى تجد عقدة الوارد في hashset.

أعلم الأولين الخطوات الخوارزمية على حد سواء O(n), حيث n يتوافق مع عدد العقد في الشجرة.ومع ذلك, أنا متأكد حول الخطوة الأخيرة.

LCA(أ ، ب) روتين لديه الخطية التعقيد.ولكن كم من العقد ، في أسوأ سيناريو يمكن العثور عليه في الخطوة 2?.

حدسي, أنا أزعم أنه يجب أن يكون أقل بكثير من ن العقد.

Answer 1

كما @ريك ديكر أوضح هل يمكن أن يكون $n/2$ يترك في أقصى عمق في حالة واحدة.في هذه الحالة, الخطوة 3 $O(n\log n)$. هذا المنصب يظهر أسوأ الأحوال.تعتبر شجرة $T$ يتكون من سلسلة من $n/2$ العقد حيث المتبقية $n/2$ العقد تعلق كما متوازن شجرة في أسفل السلسلة.وهذا يعطي كل ورقة عمق $n/2+\log_2(ن)=\ثيتا(n)$ مع $n/4$ يترك في العمق $\ثيتا(n)$ لدينا $\ثيتا(n^2)$ وقت التشغيل من أجل الخطوة 3 في هذه الحالة.هذا هو مقارب أسوأ الأحوال لأن لدينا $n$ العقد في أقصى العمق $n$.

هناك طريقة أفضل للقيام بذلك.يتيح تحديد وظيفة $f$

$ و(v) = \begin{حالة} v & ext{إذا}\quad exttt{الطول}(الخامس من اليسار) = exttt{الطول}(ضد الحق) \\ و(الخامس من اليسار) & ext{إذا}\quad exttt{الطول}(الخامس من اليسار) > exttt{الطول}(ضد الحق) \\ و(ضد الحق) & ext{إذا}\quad exttt{الطول}(الخامس من اليسار) < exttt{الطول}(ضد الحق) \end{حالة} $

إذا مرتفعات الأطفال من عقدة $v$ هي نفسها ، ثم بوضوح $v$ هو LCA من أعمق العقد من الشجرة الجذور في $v$.إذا الشجرة اليسرى اطول, ثم نريد الرابطة من أعمق العقد من الشجرة الجذور في $ضد اليسار$, لأنها أعمق من أعمق العقد في الشجرة ذات الجذور في $v. الحق$.نفس المنطق يلي على $v. الحق$ عندما أطول.

القيم $ exttt{الطول}$ و $f(v)$ يمكن حسابها في ما بعد من أجل اجتياز $T$ في الزمن الخطي.

الدعوة $f(الجذر)$ يجب أن تعود الرابطة من أعمق العقد في الشجرة.

Answer 2

حسنا, أنا لا أعرف ماذا كنت تنوي من قبل "أقل بكثير" لكن من الواضح أنه يمكن أن يكون عن $n/2$ يترك في أقصى عمق:اتخاذ شجرة ثنائية كاملة ، على سبيل المثال ، مع أدنى مستوى كامل.

Answer 3

كنت أكتب وظيفة كل شجرة يحسب أدنى سلف مشترك من جميع أعمق العقد ، و ارتفاع الشجرة.هذا هو بسيط جدا:

إذا كان الجذر R لا اليسار أو اليمين فرع ، ثم ارتفاع 1 و سلف مشترك هو R.إذا كان الجذر R إما اليسار أو اليمين فرع ، ثم حساب ارتفاع أدنى سلف مشترك من فرع ارتفاع مع الجذر R هي واحدة أعلى ، ولكن بأقل سلف مشترك هو نفسه.

إذا كان هناك يسار و حق فرع ، ثم حساب ارتفاع أدنى سلف مشترك من كل الفروع.إذا كان ارتفاعات مختلفة ، ثم نعود (الطول + 1) بالاضافة الى أدنى سلف من هذا الفرع.إذا مرتفعات هي نفسها ، ثم نعود (الطول + 1) ، R كما أدنى سلف مشترك.

التي ينبغي أن تأخذ cN خطوات صغيرة ثابتة ج إذا كان عدد العقد هو N.وبما أننا يجب أن زيارة كل عقدة N (على الأقل أن تعرف أنه لا يوجد لديه فروع) ، وهذا لا يمكن تحسينها.