ما معنى Centroid في الخوارزميات وهياكل البيانات؟ المركز الهندسي ومركز الشجرة

كلمة Centroid في علوم الحاسب لها معنيان مختلفان تمامًا، والخلط بينهما هو سبب الحيرة الأكبر. المعنى الأول هندسي وإحصائي: هو "النقطة المركزية" التي تمثّل متوسط مجموعة من النقاط، وتُستخدم أساسًا في خوارزميات التجميع مثل K-means. المعنى الثاني بنيوي وخاص بهياكل البيانات: هو مركز الشجرة (Tree Centroid)، أي العقدة التي إذا حذفناها انقسمت الشجرة إلى أجزاء لا يتجاوز حجم أكبرها نصف عدد العقد. إذا كنت طالب علوم حاسب تدرس الأشجار والخوارزميات التنافسية، فالمعنى الذي تبحث عنه على الأرجح هو الثاني، وهو ما تتجاهله معظم الشروحات المبسّطة.

في ما يلي نفصّل المعنيين بدقة حتى تعرف أيهما يخصّ مسألتك.

المعنى الأول: المركز الهندسي (النقطة المتوسطة)

في الرياضيات وتحليل البيانات، الـ centroid هو النقطة الواقعة في "مركز الكتلة" لمجموعة من النقاط، ويُحسب بأخذ متوسط الإحداثيات. في بُعدين، إذا كان لدينا نقاط (x1,y1)…(xn,yn)، فإن:

• x = (x1 + x2 + … + xn) / n
• y = (y1 + y2 + … + yn) / n

والقاعدة نفسها تمتد إلى أي عدد من الأبعاد بحساب المتوسط لكل مُحوَر على حدة. لاحظ أن المركز ليس بالضرورة إحدى نقاط المجموعة؛ فهو غالبًا نقطة جديدة تقع بينها.

أين يظهر هذا؟ خوارزمية K-means

أشهر استخدام لهذا المعنى هو خوارزمية K-means لتجميع البيانات، وتسير كالتالي:

1. اختَر عدد المجموعات k وحدّد k مراكز ابتدائية.
2. أسنِد كل نقطة إلى أقرب مركز إليها (عادةً بالمسافة الإقليدية).
3. أعِد حساب كل مركز ليصبح متوسط النقاط المنتمية إليه.
4. كرّر الخطوتين حتى تستقر المراكز ولا تتغير مواضعها.

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

المعنى الثاني: مركز الشجرة (Tree Centroid)

هنا ننتقل إلى قلب "هياكل البيانات". في شجرة تحوي n عقدة، المركز هو عقدة تحقّق شرطًا واحدًا: عند حذفها تنقسم الشجرة إلى مكوّنات (subtrees) لا يتجاوز حجم أكبرها n/2. بعبارة أخرى، هي أكثر عقدة "توازنًا" في الشجرة.

حقائق مهمة يجب حفظها:

• لكل شجرة مركز واحد على الأقل، وقد يكون لها مركزان متجاوران (يحدث ذلك في الأشجار ذات العدد الزوجي المتوازن).
• المركز يختلف عن الجذر (root)؛ الجذر تختاره أنت، بينما المركز خاصية بنيوية للشجرة نفسها.
• المركز يختلف أيضًا عن قطر الشجرة (diameter) رغم قربهما في الحدس.

خطوات إيجاد مركز الشجرة

1. اختر أي عقدة جذرًا مؤقتًا وشغّل بحثًا بالعمق (DFS).
2. احسب size[v] لكل عقدة، أي عدد العقد في الشجرة الفرعية المتجذرة عندها.
3. لكل عقدة v، احسب حجم أكبر مكوّن ينتج عن حذفها: إما إحدى شجراتها الفرعية size[child]، أو الجزء العلوي n - size[v].
4. العقدة التي يكون فيها أكبر مكوّن ≤ n/2 هي المركز.

الزمن الكلي لهذه العملية هو O(n)، أي خطي وسريع جدًا حتى للأشجار الكبيرة.

تفكيك المركز (Centroid Decomposition)

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

1. جِد مركز الشجرة الحالية.
2. اجعله عقدة في "شجرة المراكز" (centroid tree).
3. احذفه، فتتفكك الشجرة إلى مكوّنات أصغر.
4. كرّر العملية على كل مكوّن، واربط مراكزه الجديدة كأبناء للمركز السابق.

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

جدول المقارنة بين المعنيين

الجانب	المركز الهندسي (K-means)	مركز الشجرة (Tree Centroid)
المجال	تحليل البيانات والتعلم الآلي	الأشجار وهياكل البيانات
ماذا يكون؟	نقطة (إحداثيات متوسطة)	عقدة داخل الشجرة
هل هو من عناصر المجموعة؟	ليس بالضرورة	نعم، عقدة موجودة فعلًا
العدد	مركز واحد لكل مجموعة	مركز أو مركزان للشجرة
الاستخدام الأبرز	التجميع (Clustering)	تفكيك المركز واستعلامات المسارات

نصيحة عملية وخطأ شائع

الخطأ الأكثر تكرارًا عند إيجاد مركز الشجرة هو نسيان الجزء "العلوي" في الحساب. كثيرون يقارنون فقط أحجام الشجرات الفرعية للأبناء وينسون المكوّن n - size[v] الذي يمثل بقية الشجرة فوق العقدة. تجاهُل هذا الطرف يعطي إجابة خاطئة في معظم الأشكال غير المتناظرة. القاعدة الذهبية: عقدة تكون مركزًا إذا وفقط إذا كان كل مكوّن ناتج عن حذفها ≤ n/2، بما في ذلك الجزء العلوي.

الأسئلة الشائعة

هل مركز الشجرة هو نفسه جذرها؟ لا. الجذر اختيار حرّ منك لتنظيم الشجرة، أما المركز فخاصية ثابتة تعتمد على شكل الشجرة نفسها بغضّ النظر عن الجذر الذي بدأت منه.

هل يمكن أن يكون للشجرة مركزان؟ نعم. بعض الأشجار لها مركزان متجاوران يحقّق كلاهما شرط أن أكبر مكوّن بعد الحذف ≤ n/2. في هذه الحالة يمكنك اختيار أيّهما في معظم الخوارزميات.

هل centroid و centroid decomposition مرتبطان بـ K-means؟ لا، رغم تشابه الاسم. K-means يستخدم المركز بمعناه الهندسي (نقطة متوسطة)، بينما تفكيك المركز مفهوم منفصل تمامًا في نظرية الأشجار.

ما فائدة تفكيك المركز عمليًا؟ يسرّع الاستعلامات المتعلقة بالمسافات والمسارات داخل الأشجار الكبيرة من زمن خطي لكل استعلام إلى O(log n) تقريبًا، وهو أساسي في المسابقات البرمجية وبعض تطبيقات الشبكات.