الضم حسب الرتبة والمكوّنات
إبقاء الأشجار مسطحة وعدّ المجموعات
الضم حسب الرتبة والمكوّنات درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 2 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
يمكن أن يكون Union كسولًا
يضع union العادي جذرًا تحت جذر آخر فحسب. وإذا نُفّذ بلا عناية، فقد يبني شجرة طويلة وبطيئة، لذلك نحتاج إلى طريقة أذكى لـدمج الجذور.
الفكرة الأساسية
يربط Union by rank دائمًا الشجرة الأقصر تحت الشجرة الأطول. ويجعل إبقاء الأشجار قصيرة كل عملية find لاحقة أسرع. 📏
ماذا تعني الرتبة
الرتبة تقدير لارتفاع الشجرة. يبدأ كل عنصر بالرتبة 0، لأن العقدة المفردة لا يوجد أسفلها أي عمق.
rank = [0] * nاربط الأقصر بالأطول
قارن رتبتي الجذرين. يصبح الجذر ذو الرتبة الأصغر ابنًا، وبذلك تبقى الشجرة المدمجة مسطحة قدر الإمكان.
if rank[ra] < rank[rb]:
parent[ra] = rbالتعادل يرفع الرتبة
عندما يكون للجذرين الرتبة نفسها، اختر أيًا منهما ليكون الجذر الجديد وزد رتبته بمقدار واحد، لأن الشجرة ازدادت ارتفاعًا بمستوى واحد.
else:
parent[rb] = ra
if rank[ra] == rank[rb]:
rank[ra] += 1تنويعة Union by size
البديل الشائع هو union by size: اربط المجموعة الأصغر تحت المجموعة الأكبر. وهو فعال بالقدر نفسه، كما يمنحك أحجام المجموعات مجانًا.
عدّ المكوّنات
ابدأ عدادًا بقيمة n، لأن كل عنصر يمثل مجموعته الخاصة. كل عملية union ناجحة تضم مجموعتين في واحدة، لذا أنقص العداد.
components = nتخطَّ عمليات Union التي لا تغيّر شيئًا
إذا كان عنصران يشتركان أصلًا في الجذر نفسه، فلن تفعل union شيئًا. أنقص العداد فقط عندما يختلف جذراهما فعليًا.
if find(a) != find(b):
union(a, b)
components -= 1الرتبة مع الضغط
اجمع بين union by rank وضغط المسار، وعندها يعمل DSU في زمن معكوس أكرمان، وهو ثابت عمليًا لأي إدخال واقعي. ⚡
أحجام المجموعات عند الطلب
باستخدام union by size، يمكنك معرفة حجم أي مجموعة فورًا: اقرأ الحجم المخزّن عند جذر ذلك العنصر.
group = size[find(x)]أين يفيد ذلك
يجيب عدّ المكوّنات عن أسئلة كلاسيكية مثل عدد مجموعات الأصدقاء أو المناطق المترابطة بعد سلسلة من استدعاءات union. 🌐
اختبار سريع
حلّل كيف يتغيّر عدد المكوّنات.
مراجعة
تعلّمت استخدام union by rank لإبقاء الأشجار مسطّحة، وكيفية تتبّع أعداد المكوّنات وأحجام المجموعات. أصبحت DSU الآن فائقة السرعة! 🎉
الأسئلة الشائعة
هل درس «الضم حسب الرتبة والمكوّنات» مجاني؟
نعم — نص درس «الضم حسب الرتبة والمكوّنات» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «الضم حسب الرتبة والمكوّنات»؟
إبقاء الأشجار مسطحة وعدّ المجموعات تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 2 من أصل 4.
كم من الوقت يستغرق درس «الضم حسب الرتبة والمكوّنات»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- DSU مع ضغط المسار
- الضم حسب الرتبة والمكوّنات
- شجرة Kruskal الممتدة الدنيا
- MST لخوارزمية Prim باستخدام كومة