ما هي الشجرة الثنائية المكتملة (Complete Binary Tree)؟ شرح مبسّط بالأمثلة
الشجرة الثنائية المكتملة (Complete Binary Tree) هي شجرة ثنائية تُملأ فيها جميع المستويات بالكامل باستثناء المستوى الأخير، على أن يُملأ هذا المستوى الأخير من اليسار إلى اليمين دون ترك فراغات في المنتصف. بعبارة أبسط: مسموح أن ينقص المستوى الأخير عقدًا، لكن العقد الموجودة فيه يجب أن تكون مرصوصة في أقصى اليسار بلا "ثقوب". هذا الانضباط في الشكل هو بالضبط ما يجعلها الأساس العملي للأكوام الثنائية (Heaps) وطوابير الأولوية، ويسمح بتخزينها داخل مصفوفة بسيطة دون الحاجة إلى مؤشرات.
أشهر خطأ: الخلط بين Complete وFull وPerfect
معظم من يبحث عن هذا المصطلح يقع في فخ اللغة، لأن الكلمات الثلاث تُترجم غالبًا إلى "كاملة" أو "ممتلئة" فتختلط المفاهيم. الحقيقة أنها ثلاثة أنواع مختلفة تمامًا:
- الشجرة المكتملة (Complete): تشترط ترتيب الامتلاء (كل المستويات ممتلئة عدا الأخير، والأخير من اليسار). لا تشترط أن يكون لكل عقدة ابنان.
- الشجرة التامة (Full): تشترط أن يكون لكل عقدة إمّا ابنان أو لا شيء (صفر أو اثنان)، ولا تهتم بترتيب المستويات إطلاقًا.
- الشجرة المثالية (Perfect): تجمع الشرطين، فكل العقد الداخلية لها ابنان، وكل الأوراق في المستوى نفسه.
| الخاصية | مكتملة (Complete) | تامة (Full) | مثالية (Perfect) |
|---|---|---|---|
| كل المستويات ممتلئة عدا الأخير | نعم | ليست شرطًا | نعم |
| المستوى الأخير يُملأ من اليسار | نعم | ليست شرطًا | ممتلئ بالكامل |
| كل عقدة لها 0 أو 2 أبناء | ليست شرطًا | نعم | نعم |
| عدد العقد ثابت بصيغة واحدة | لا (مجال) | لا | نعم (2^(h+1) − 1) |
الخلاصة العملية: كل شجرة مثالية هي مكتملة وتامة في آن واحد، لكن العكس غير صحيح.
لماذا يهمّ الامتلاء من اليسار؟ سرّ التمثيل في مصفوفة
القيمة الحقيقية للشجرة المكتملة تظهر عند تخزينها. لأنها مرصوصة بلا فجوات، يمكن وضع عقدها في مصفوفة بالترتيب من الأعلى للأسفل ومن اليسار لليمين، ثم الانتقال بين العقد بالحساب بدل المؤشرات.
باستخدام فهرسة تبدأ من الصفر، وإذا كانت العقدة في الموضع i:
- الابن الأيسر في الموضع
2i + 1. - الابن الأيمن في الموضع
2i + 2. - العقدة الأب في الموضع
(i − 1) / 2(مع تقريب لأسفل).
هذا يوفّر الذاكرة ويجعل الوصول فوريًا، وهو تحديدًا السبب في أن أي شجرة فيها "ثقب" في المنتصف تفسد هذه الحسابات، ولهذا يشترط الترتيب من اليسار.
أين تُستخدم فعليًا؟
الشجرة المكتملة ليست مفهومًا نظريًا فقط، بل تقف خلف أدوات تستعملها يوميًا:
- الأكوام الثنائية (Binary Heaps): كل كومة صغرى أو كبرى هي في جوهرها شجرة ثنائية مكتملة، وعليها تُبنى طوابير الأولوية.
- خوارزمية HeapSort: تعتمد كليًا على هذا الشكل لضمان أداء ثابت.
- خوارزميات المسارات مثل Dijkstra وPrim: تستفيد من طابور الأولوية المبني على كومة لاختيار أقصر مسار بكفاءة.
- جدولة المهام في أنظمة التشغيل حين يلزم سحب أعلى أولوية بسرعة.
كم عقدة تحتوي؟ (تصحيح صيغة منتشرة خاطئة)
كثير من الشروحات يقول إن عدد العقد يساوي 2^n − 1، وهذا خطأ شائع: هذه الصيغة تخص الشجرة المثالية لا المكتملة. الشجرة المكتملة يتغير عدد عقدها لأن مستواها الأخير قد يكون ناقصًا، لذا يقع عددها ضمن مجال لا قيمة واحدة.
لشجرة مكتملة ارتفاعها h (بجعل الجذر عند الارتفاع صفر)، يتراوح عدد العقد بين 2^h كحد أدنى و2^(h+1) − 1 كحد أقصى. والمهم أن ارتفاعها يبقى دائمًا ⌊log₂ n⌋ تقريبًا، ولهذا تبقى عمليات البحث والإدراج والحذف في الكومة بزمن O(log n)، بينما بناء كومة كاملة من مصفوفة يتم بزمن O(n).
نصيحة عملية وخطأ يقع فيه المبتدئون
الفخ الأكبر أثناء البرمجة هو الخلط بين الفهرسة التي تبدأ من صفر وتلك التي تبدأ من واحد. إذا بدأت المصفوفة من الفهرس 1، تتغير المعادلات إلى: الابن الأيسر 2i، الأيمن 2i + 1، والأب ⌊i / 2⌋. اختلاط الصيغتين يسبب أخطاء صامتة يصعب تتبعها.
والتنبيه الثاني: كون الشجرة "مكتملة" لا يعني أنها "مرتبة". الاكتمال وصف للشكل فقط، أما ترتيب القيم فهو شرط منفصل (كما في أشجار البحث الثنائية أو خاصية الكومة). لا تفترض أبدًا أن شجرة مكتملة تعني بيانات مرتّبة.
الأسئلة الشائعة
هل كل شجرة كومة (Heap) هي شجرة مكتملة؟ نعم، الكومة الثنائية دائمًا شجرة مكتملة من حيث الشكل، لكنها تضيف فوق ذلك شرط ترتيب القيم بين الأب وأبنائه.
ما الفرق سريعًا بين المكتملة والتامة؟ المكتملة تهتم بترتيب امتلاء المستويات من اليسار، والتامة تهتم بأن يكون لكل عقدة صفر أو ابنان دون النظر للترتيب.
لماذا نخزّن الشجرة المكتملة في مصفوفة بدل المؤشرات؟ لأن انتظامها يسمح بحساب مواضع الأبناء والآباء رياضيًا، فنوفّر الذاكرة ونحصل على وصول أسرع.
هل الشجرة المثالية حالة خاصة من المكتملة؟ نعم، كل شجرة مثالية هي مكتملة (وتامة أيضًا)، لكن ليست كل مكتملة مثالية لأن مستواها الأخير قد يكون ناقصًا.