اتحاد/العثور على خوارزمية بدون اتحاد عن طريق رتبة هيكل بيانات الغابات غير المحدد

Question

إليك انهيار على خوارزمية الاتحاد/البحث عن الغابات المنفصلة ويكيبيديا:

• غابات Barebone DISJOINT SET ... (O(n))
  • ... مع Union by Rank ... (تحسن الآن إلى O(log(n))
    • ... مع ضغط المسار (تحسن الآن إلى O(a(n)), ، على نحو فعال O(1))

يستلزم تنفيذ الاتحاد عن طريق الترتيب أن تحتفظ كل عقدة rank حقل لأغراض المقارنة. سؤالي هو ، هل يونيون من رتبة يستحق هذه المساحة الإضافية؟ ماذا يحدث إذا تخطيت الاتحاد عن طريق الرتبة وقمت فقط بالضغط على المسار بدلاً من ذلك؟ هل هو جيد بما فيه الكفاية؟ ما هو التعقيد المطفأ الآن؟

---

يتم تقديم تعليق يعني أن الاتحاد عن طريق رتبة بدون ضغط مسار (تم إطفاؤه O(log(n) التعقيد) يكفي لأكثر التطبيقات العملية. هذا صحيح. ما أطلبه هو العكس: ماذا لو تخطيت الاتحاد عن طريق الرتبة ولم تفعل سوى ضغط المسار بدلاً من ذلك؟

بمعنى ما ، يعد ضغط المسار خطوة إضافية لتحسين الاتحاد عن طريق الترتيب ، ولهذا السبب يمكن حذف هذه الخطوة الإضافية دون نتيجة كارثية. ولكن هل يونيون برتبة خطوة وسيطة ضرورية لضغط المسار؟ هل يمكنني تخطيه والذهاب مباشرة إلى ضغط المسار ، أم أن ذلك سيكون كارثيًا؟

---

وقد أشار أيضًا إلى أنه بدون Union by Rank ، يمكن للاتحادات المتكررة إنشاء هيكل مثل القائمة المرتبطة. هذا يعني أن عملية ضغط المسار الواحدة قد تتطلب O(n) في أسوأ الأحوال. هذا من شأنه أن يؤثر بالطبع على العمليات المستقبلية ، فكيف يتم تشغيل هذا عند إطفاءه على العديد من العمليات هو ما يهمني أكثر.

Answer 1

لقد غوغل عن "بدون اتحاد حسب الرتبة" والرابط الثاني الذي ظهر هذا:

... نغلق هذا القسم بتحليل للاتحاد مع ضغط المسار ولكن بدون اتحاد عن طريق الترتيب ...

بنية داس في الاتحاد مع ضغط المسار ولكن بدون اتحاد عن طريق عمليات الرتبة M Find و N-1 Link Link في الوقت O ((M+N) log n)

Answer 2

ضغط المسار يضيء بنية الشجرة. الاتحاد عن طريق رتبة يساعد على الاندماج. افترض أنك تخطي الأخير. حتى الآن ، لديك غابة بدون معلومات رتبة لاختيار كيفية الاندماج. من المحتمل أن تتعرض الآن لخطر دمج شجرة بعمق أكبر إلى واحدة ذات عمق أصغر - مما يؤدي إلى بنية شجرة غير متوازنة. في أسوأ الحالات ، قد ينتهي بك الأمر بقائمة مرتبطة. يزداد تعقيد الوقت الذي تم إطفاؤه في اتحاد حتى لو لم يبقى ذلك هو نفسه.

IMO ، سيكون من الأفضل تخطي ضغط المسار ولكن ليس المرتبة.