هيكلة بيانات المجموعات المنفصلة
في علم الحاسوب، المجموعة المنفصلة من هيكلة البيانات كما تسمى ايضًا هيكلة بيانات العثور المتحد أو مجموعة العثور المندمج، هيكلة البيانات هذه تضمن أن يكون تتابع العناصر فيها منفصل في عدد من الفروع المفككة (غير متداخلة.) كما تدعم هذه الهيكلة عمليتان مفيدتين هما:
1- الإيجاد (Find) : تحديد في أي الفروع يوجد العنصر، تعيد عملية الإيجاد بالعادة العنصر من هذه المجموعة عن طريق ممثله عبر مقارنة نتيجتي علميتي بحث، ليتم تحديد إذا كان العنصرين في نفس المجموعة ام لا.2- الاتحاد (Union) : حيث يقوم بجمع فرعين في فرع واحد.
أما العملية المهمة الأخرى وهي صناعة المجموعة (MakeSet) والتي تصنع مجموعة تحتوي على عنصر واحد عديم الأهمية بالعادة. مع هذه العمليات الثلاث، يمكن حل العديد من مشاكل التقسيم العملية.)

لكي يتم تحديد هذه العمليات بوضوح، يجب ان يكون هناك طريقة لتمثيل هذه البيانات، أحد هذه المناهج المتداول عليها هي اختيار عنصر ثابت من كل مجموعة يسمى الممثل، ليمثل المجموعة بأكملها.
إذًا Find(x) تعيد ممثل المجموعة التي ينتمي اليها x، وعملية الاتحاد Union تأخد ممثلي المجموعتين لدمجهما معا في مجموعة واحدة.

المجموعة المنفصلة ذات القوائم المترابطة 
هيكلة المجموعات المنفصلة للبيانات بصيغتها البسيطة تستخدم القوائم المترابطة لكل مجموعة، ويتم اختيار رأس هذه القائمة كممثل لهذه المجموعة.

MakeSet تقوم بصناعة قائمة تحتوي على عنصر واحد، أما Union تقوم بدمج قائمتين معًا بعملية ذات وقت ثابت إذا كان هناك مؤشر لذيل القائمة، أما العقبة في وجه هذا التطبيق هي عملية البحث Find فهي تتطلب O(n) أو زمن يزداد بشكل خطي ليمر عبر القائمة من الخلف إلى رأس القائمة.

لكن من الممكن تجاهل هذا بإضافة مؤشر يؤشر على رأس القائمة في كل عقدة (node) تابعة لهذه القائمة وبتالي ستأخذ عملية البحث وقت ثابت حيث يعود هذا المؤشر بشكل مباشر إلى الممثل لهذه القائمة لكن بهذه الحالة سنقع في مشكلة أخرى حيث سنصبح بحاجة إلى تعديل كل العقد ليؤشروا على رأس قائمة من القائمتين في حال استخدمنا عملية الاتحاد Union وهذا يتتطلب O(n) عملية.

عندما يكون طول القائمة معروف يمكن تقليل الوقت عبر إضافة القائمة الأصغر إلى القائمة الأكبر، باستخدام هذا الاتحاد الموزون سلسلة m من صنع المجموع وعمليتي الإيجاد والاتحاد على n من العناصر يتطلب O(m+nlogn) عملية. اما إذا اردنا أداء أفضل من هذا فعلينا التفكير بهيكلة بينات مختلفة عن القوائم المنفصلة.

غابات المجموعات المنفصلة 
غابات المجموعات المنفصلة هي هيكلة بينات حيث تكون كل مجموعة على شكل هيكلة بيانات شجرية بحيت تحتوي كل عقدة مؤشر للعقدة الأب.

في غابة المجموعة المنفصلة الممثل لكل مجموعة هو جذر شجرة المجموعة حيث تقوم عملية البحث بتتبع الأب لكل عقدة حتى تصل إلى جذر الشجرة وتقوم عملية الدمج بحيث يتم رفح جذر أحد الأشجار إلى الشجرة المراد الدمج اليها حيث يتم كتابة العمليات الثلاث بالشكل التالي:
 function MakeSet(x)
  x.parent := x

 function Find(x)
  if x.parent == x
   return x
  else
   return Find(x.parent)

 function Union(x, y)
  xRoot := Find(x)
  yRoot := Find(y)
  xRoot.parent := yRoot
بكل الأحوال هذا النظام ليس أفضل من القوائم المتصلة، لأنه من الممكن وبكل بساطة ان تكون الشجرة غير موزونة أي غير موزعة بالشكل الصحيح، لكن يمكن تحسينها بطريقتين.

الطريقة الأولى، وهي الدمج حسب المرتبة أي دمج الشجرة الأصخر اليى الشجرة الأكبر، حيث عمق الشجرة هو من يتحكم بمقدار جودة الشجرة وبالتالي لن يزداد العمق الا بحالة كان العمقين متساووين.
يتم استخدام المرتبة عوضًا عن العمق لأن عمق قد لا يساوي المرتبة حيث تكون الشجرة ذات العنصر الواحد ذات مرتبة تساوي صفر.
 function MakeSet(x)
  x.parent := x
  x.rank := 0

 function Union(x, y)
  xRoot := Find(x)
  yRoot := Find(y)
  if xRoot == yRoot
   return

  // x and y are not already in same set. Merge them.
  if xRoot.rank < yRoot.rank
   xRoot.parent := yRoot
  else if xRoot.rank > yRoot.rank
   yRoot.parent := xRoot
  else
   yRoot.parent := xRoot
   xRoot.rank := xRoot.rank + 1
اما الطريقة الثانية تسمى ضغط الطريق، وهي محاولة تقصير طريق عند استخدام عملية الإيجاد بحيث يمكن رفع كل عقدة مباشرة إلى الجذر بحيث يتم تغير الالعقدة الأب لكل العقد بحيث تؤشر على الجذر.
 function Find(x)
  if x.parent != x
   x.parent := Find(x.parent)
  return x.parent

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

تاريخ 
رغم أن الأفكار المستخدمة في المجموعات المنفصلة ومعروفة منذ زمن، كان روبرت ترجان أول من أثبت الحد الأعلى والنسخة المقيدة من الحد الأدنى بعكس وظيفة اركمان عام 1975، حتى هذا الوقت كان أفضل حد مكتشف عر هوبكرافت ويلمان حيث كان O(logn)، الخوارزمية المعادة ل n، معادلة أخرى تنمو ببطء.

كما طور ترجان وفان لوين خوارزمية البحث تقوم باعادة النتيجة بمرور واحد أكثر دقة.

في عام 2007 قام سلفيان كونكون وو جين كريستوف فليتر طور نسخة متكررة من هيكلة المجموعة المنفصلة بحيث يسمح للهيكل السابق بالحفاظ على كفائته بستخدام اثبات مساعد كوك

مراجع 

بنى البيانات
خوارزميات بحث
في علم الحاسوب ، المجموعة المنفصلة من هيكلة البيانات كما تسمى ايضًا هيكلة بيانات العثور المتحد أو مجموعة العثور المندمج ، هيكلة البيانات هذه تضمن أن يكون تتابع العناصر في ها منفصل في عدد من الفروع المفككة ( غير متداخلة . ) كما تدعم هذه ال هيكلة عمليتان مفيدتين هما : 1 - ال إيجاد ( Find ) \ : تحديد في أي الفروع يوجد العنصر ، تعيد عملية ال إيجاد ب العادة العنصر من هذه المجموعة عن طريق ممثل ه عبر مقارنة نتيجة ي علميتي بحث ، ل يتم تحديد إذا كان العنصرين في نفس المجموعة ام لا .2 - الاتحاد ( Union ) \ : حيث يقوم ب جمع فرعين في فرع واحد . أما العملية المهمة الأخرى و هي صناعة المجموعة ( MakeSet ) و التي تصنع مجموعة تحتوي على عنصر واحد عديم الأهمية ب العادة . مع هذه العمليات الثلاث ، يمكن حل العديد من مشاكل التقسيم العملية . ) لكي يتم تحديد هذه العمليات ب وضوح ، يجب ان يكون هناك طريقة ل تمثيل هذه البيانات ، أحد هذه المناهج المتداول علي ها هي اختيار عنصر ثابت من كل مجموعة يسمى الممثل ، ل يمثل المجموعة ب أكمل ها . إذًا Find ( x ) تعيد ممثل المجموعة التي ينتمي إلي ها x ، و عملية الاتحاد Union تأخد ممثلي المجموعتين ل دمج هما معا في مجموعة واحدة . المجموعة المنفصلة ذات القوائم المت رابطة هيكلة المجموعات المنفصلة للبيانات بصيغة ها البسيطة تستخدم القوائم المت رابطة ل كل مجموعة ، و يتم اختيار رأس هذه القائمة كممثل ل هٰذه المجموعة . MakeSet تقوم بصناعة قائمة تحتوي على عنصر واحد ، أما Union تقوم بدمج قائمتين معًا ب عملية ذات وقت ثابت إذا كان هناك مؤشر لذيل القائمة ، أما العقبة في وجه هذا التطبيق هي عملية البحث Find ف هي تتطلب O ( n ) أو زمن يزداد ب شكل خطي ل يمر عبر القائمة من الخلف إلى رأس القائمة . لكن من الممكن تجاهل هذا ب إضافة مؤشر يؤشر على رأس القائمة في كل عقدة ( node ) تابعة ل هٰذه القائمة وبتالي س تأخذ عملية البحث وقت ثابت حيث يعود هذا المؤشر ب شكل مباشر إلى الممثل ل هٰذه القائمة لكن ب هٰذه الحالة سنقع في مشكلة أخرى حيث سنصبح ب حاجة إلى تعديل كل العقد ليؤشروا على رأس قائمة من القائمتين في حال استخدمنا عملية الاتحاد Union و هٰذا ي تتطلب O ( n ) عملية . عندما يكون طول القائمة معروف يمكن تقليل الوقت عبر إضافة القائمة الأصغر إلى القائمة الأكبر ، ب استخدام هذا الاتحاد الموزون سلسلة m من صنع ال مجموع وعمليتي ال إيجاد و الاتحاد على n من العناصر يتطلب O ( m + nlogn ) عملية . اما إذا ارد نا أداء أفضل من هذا ف علي نا التفكير ب هيكلة بينات مختلفة عن القوائم المنفصلة . غابات المجموعات المنفصلة غابات المجموعات المنفصلة هي هيكلة بينات حيث تكون كل مجموعة على شكل هيكلة بيانات شجرية بحيت تحتوي كل عقدة مؤشر للعقدة الأب . في غابة المجموعة المنفصلة الممثل ل كل مجموعة هو جذر شجرة المجموعة حيث تقوم عملية البحث ب تتبع الأب ل كل عقدة حتى تصل إلى جذر الشجرة و تقوم عملية الدمج ب حيث يتم رفح جذر أحد الأشجار إلى الشجرة المراد الدمج إلي ها حيث يتم كتابة العمليات الثلاث ب الشكل التالي : function MakeSe t ( x ) x.parent \ : = x function Find ( x ) if x.parent = = x return x else return Find ( x.parent ) function Unio n ( x , y ) xRoot\ : = Find ( x ) yRoot\ : = Find ( y ) xRoot.parent \ : = yRoot ب كل الأحوال هذا النظام ليس أفضل من القوائم المتصلة ، لأن ه من الممكن وبكل بساطة ان تكون الشجرة غير موزونة أي غير موزعة ب الشكل الصحيح ، لكن يمكن تحسين ها بطريقتين . الطريقة الأولى ، و هي الدمج حسب المرتبة أي دمج الشجرة الأصخر اليى الشجرة الأكبر ، حيث عمق الشجرة هو من يتحكم ب مقدار جودة الشجرة و ب التالي لن يزداد العمق الا ب حالة كان العمقين متساووين . يتم استخدام المرتبة عوضًا عن العمق لأن عمق قد لا يساوي المرتبة حيث تكون الشجرة ذات العنصر الواحد ذات مرتبة تساوي صفر . function MakeSe t ( x ) x.parent \ : = x x.rank \ : = 0 function Unio n ( x , y ) xRoot\ : = Find ( x ) yRoot\ : = Find ( y ) if xRoot = = yRoot return / / x and y are not already in same set . Merge them . if xRoot.rank < yRoot.rank xRoot.parent \ : = yRoot else if xRoot.rank > yRoot.rank yRoot.parent \ : = xRoot else yRoot.parent \ : = xRoot xRoot.rank \ : = xRoot.rank + 1 اما الطريقة الثانية تسمى ضغط الطريق ، و هي محاولة تقصير طريق عند استخدام عملية ال إيجاد ب حيث يمكن رفع كل عقدة مباشرة إلى الجذر ب حيث يتم تغير الالعقدة الأب ل كل العقد ب حيث تؤشر على الجذر . function Find ( x ) if x.parent ! = x x.parent \ : = Find ( x.parent ) return x.parent تطبيقات هيكلة المجموعات المنفصلة للبيانات نموذج لتقسيم المجموعة على سبيل المثال يمكن استخدام هذه الهيكيلة ل معرفة إذا كان الرأسين تابعين ل نفس العنصر أو إذا كان هناك دائرة مكتملة في الرسوم غير الموجهة ، و تستخدم في مكتبة دفع ال رسومات ل تنفيذ وظائف المكونات المتصلة المتزايدة ، كما تستخدم ايضًا في تطبيق خوارزمية كروسكال . تاريخ رغم أن الأفكار المستخدمة في المجموعات المنفصلة ومعروفة منذ زمن ، كان روبرت ترجان أول من أثبت الحد الأعلى والنسخة المقيدة من الحد الأدنى ب عكس وظيفة اركمان عام حتى هذا الوقت كان أفضل حد مكتشف عر هوبكرافت ويلمان حيث كان O ( logn ) ، الخوارزمية المعادة ل n ، معادلة أخرى تنمو ب بطء . كما طور ترجان وفان لوين خوارزمية البحث تقوم ب إعادة النتيجة بمرور واحد أكثر دقة . في عامقام سلفيان كونكون وو جين كريستوف فليتر طور نسخة متكررة من هيكلة المجموعة المنفصلة ب حيث يسمح للهيكل السابق ب الحفاظ على كفائته بستخدام اثبات مساعد كوك مراجع بنى البيانات خوارزميات بحث