هيكلة بيانات المجموعات المنفصلة
في علم الحاسوب، المجموعة المنفصلة من هيكلة البيانات كما تسمى ايضًا هيكلة بيانات العثور المتحد أو مجموعة العثور المندمج، هيكلة البيانات هذه تضمن أن يكون تتابع العناصر فيها منفصل في عدد من الفروع المفككة (غير متداخلة.) كما تدعم هذه الهيكلة عمليتان مفيدتين هما:
أما العملية المهمة الأخرى وهي صناعة المجموعة (MakeSet) والتي تصنع مجموعة تحتوي على عنصر واحد عديم الأهمية بالعادة. مع هذه العمليات الثلاث، يمكن حل العديد من مشاكل التقسيم العملية.)
لكي يتم تحديد هذه العمليات بوضوح، يجب ان يكون هناك طريقة لتمثيل هذه البيانات، أحد هذه المناهج المتداول عليها هي اختيار عنصر ثابت من كل مجموعة يسمى الممثل، ليمثل المجموعة بأكملها.
إذًا Find(x) تعيد ممثل المجموعة التي ينتمي اليها x ، وعملية الاتحاد Union تأخد ممثلي المجموعتين لدمجهما معا في مجموعة واحدة.
هيكلة المجموعات المنفصلة للبيانات بصيغتها البسيطة تستخدم القوائم المترابطة لكل مجموعة، ويتم إختيار رأس هذه القائمة كممثل لهذه المجموعة.
MakeSet تقوم بصناعة قائمة تحتوي على عنصر واحد، أما Union تقوم بدمج قائمتين معًا بعملية ذات وقت ثابت إذا كان هناك مؤشر لذيل القائمة، أما العقبة في وجه هذا التطبيق هي عملية البحث Find فهي تتطلب O(n) او زمن يزداد بشكل خطي ليمر عبر القائمة من الخلف إلى رأس القائمة.
لكن من الممكن تجاهل هذا بإضافة مؤشر يؤشر على رأس القائمة في كل عقدة (node) تابعة لهذه القائمة وبتالي ستأخذ عملية البحث وقت ثابت حيث يعود هذا المؤشر بشكل مباشر إلى الممثل لهذه القائمة لكن بهذه الحالة سنقع في مشكلة أخرى حيث سنصبح بحاجة إلى تعديل كل العقد ليؤشروا على رأس قائمة من القائمتين في حال استخدمنا عملية الاتحاد Union وهذا يتتطلب O(n) عملية.
عندما يكون طول القائمة معروف يمكن تقليل الوقت عبر اضافة القائمة الأصغر إلى القائمة الأكبر، بإستخدام هذا الاتحاد الموزون سلسلة m من صنع المجموع وعمليتي الإيجاد و الاتحاد على n من العناصر يتطلب O(m+nlogn) عملية. اما إذا اردنا أداء أفضل من هذا فعلينا التفكير بهيكلة بينات مختلفة عن القوائم المنفصلة.
غابات المجموعات المنفصلة هي هيكلة بينات حيث تكون كل مجموعة على شكل هيكلة بيانات شجرية بحيت تحتوي كل عقدة مؤشر للعقدة الأب.
في غابة المجموعة المنفصلة الممثل لكل مجموعة هو جذر شجرة المجموعة حيث تقوم عملية البحث بتتبع الأب لكل عقدة حتى تصل إلى جذر الشجرة وتقوم عملية الدمج بحيث يتم رفح جذر أحد الأشجار إلى الشجرة المراد الدمج اليها حيث يتم كتابة العمليات الثلاث بالشكل التالي:
بكل الأحوال هذا النظام ليس أفضل من القوائم المتصلة، لأنه من الممكن وبكل بساطة ان تكون الشجرة غير موزونة اي غير موزعة بالشكل الصحيح، لكن يمكن تحسينها بطريقتين.
الطريقة الأولى، وهي الدمج حسب المرتبة اي دمج الشجرة الأصخر اليى الشجرة الأكبر، حيث عمق الشجرة هو من يتحكم بمقدار جودة الشجرة وبالتالي لن يزداد العمق الا بحالة كان العمقين متساووين.
يتم استخدام المرتبة عوضًا عن العمق لأن عمق قد لا يساوي المرتبة حيث تكون الشجرة ذات العنصر الواحد ذات مرتبة تساوي صفر.
اما الطريقة الثانية تسمى ضغط الطريق، وهي محاولة تقصير طريق عند استخدام عملية الإيجاد بحيث يمكن رفع كل عقدة مباشرة إلى الجذر بحيث يتم تغير الالعقدة الأب لكل العقد بحيث تؤشر على الجذر.
هيكلة المجموعات المنفصلة للبيانات نموذج لتقسيم المجموعة على سبيل المثال يمكن استخدام هذه الهيكيلة لمعرفة اذا كان الرأسين تابعين لنفس العنصر او اذا كان هناك دائرة مكتملة في الرسوم غير الموجهة، وتستخدم في مكتبة دفع الرسومات لتنفيذ وظائف المكونات المتصلة المتزايدة، كما تستخدم ايضًا في تطبيق خوارزمية كروسكال .
رغم أن الأفكار المستخدمة في المجموعات المنفصلة ومعروفة منذ زمن، كان روبرت ترجان أول من أثبت الحد الأعلى والنسخة المقيدة من الحد الأدنى بعكس وظيفة اركمان عام 1975، حتى هذا الوقت كان أفضل حد مكتشف عر هوبكرافت ويلمان حيث كان O(logn)، الخوارزمية المعادة ل n ، معادلة اخرى تنمو ببطء.
كما طور ترجان وفان لوين خوارزمية البحث تقوم باعادة النتيجة بمرور واحد أكثر دقة.
في عام 2007 قام سلفيان كونكون و و جين كريستوف فليتر طور نسخة متكررة من هيكلة المجموعة المنفصلة بحيث يسمح للهيكل السابق بالحفاظ على كفائته بستخدام اثبات مساعد كوك