ما هي الشجرة الثنائية (Binary Tree)؟ شرح مبسّط مع أمثلة وأنواع
الشجرة الثنائية (Binary Tree) هي هيكل بيانات هرمي تتفرّع فيه كل عقدة إلى عقدتين فرعيتين على الأكثر: واحدة يسرى وواحدة يمنى. هذا القيد البسيط ("اثنتان كحد أقصى") هو ما يميّزها ويجعلها الأساس لكثير من الخوارزميات الفعّالة في البحث والفرز وتمثيل البيانات المتفرّعة. إن كنت تتعلّم علوم الحاسب أو تستعدّ لمقابلة برمجية، فهذا الهيكل من أول ما يُطلب منك فهمه فعليًا لا حفظه.
في هذا الشرح سنبني الفكرة من الصفر: ما العقدة، وكيف تتكوّن الشجرة، وما أنواعها، وأهم نقطة يخطئ فيها المبتدئون: الفرق بين الشجرة الثنائية العادية وشجرة البحث الثنائية.
المكوّنات الأساسية للشجرة الثنائية
لفهم الشجرة، تخيّلها كعائلة مقلوبة رأسًا على عقب: الجذر في الأعلى، والفروع تنزل للأسفل.
- العقدة (Node): الوحدة الأساسية، وتحمل قيمة (بيانات) ومؤشرين: واحد إلى الابن الأيسر وآخر إلى الابن الأيمن. إذا لم يوجد ابن، يكون المؤشر فارغًا (null).
- الجذر (Root): العقدة الأولى في القمة التي تبدأ منها الشجرة. للشجرة جذر واحد فقط.
- الأبناء والأب (Children / Parent): كل عقدة متفرّعة من عقدة أعلى منها تُسمى ابنًا، والأعلى أبًا.
- الورقة (Leaf): عقدة ليس لها أبناء، أي نهاية الفرع.
- العمق والارتفاع (Depth / Height): العمق هو بُعد العقدة عن الجذر، والارتفاع هو أطول مسار من الجذر إلى أبعد ورقة. الارتفاع مهم جدًا لأنه يحدّد سرعة العمليات.
نقطة يغفل عنها كثيرون: كلمة "ثنائية" لا تعني أن كل عقدة يجب أن يكون لها ابنان، بل أنه يُسمح لها بابنين كحدٍّ أقصى. فقد يكون لعقدة ابن واحد فقط، أو لا أبناء إطلاقًا.
أنواع الأشجار الثنائية
تختلف التسميات حسب شكل امتلاء الشجرة، وهذا جدول يوضّح الفروق بإيجاز:
| النوع | الوصف المختصر | ملاحظة عملية |
|---|---|---|
| ممتلئة (Full) | كل عقدة إما لها ابنان أو لا أبناء لها إطلاقًا | لا وجود لعقدة بابن واحد |
| كاملة (Complete) | كل المستويات ممتلئة عدا الأخير، ويُملأ من اليسار | الأساس الذي يُبنى عليه الـ Heap |
| مثالية (Perfect) | كل المستويات ممتلئة تمامًا حتى الأخير | عدد الأوراق = ضعف بقية العقد تقريبًا |
| متوازنة (Balanced) | فرق الارتفاع بين الجانبين محدود (غالبًا ≤ 1) | تضمن كفاءة البحث بمنع "تدهور" الشجرة |
| منحرفة (Skewed) | كل العقد تميل لجهة واحدة | أسوأ حالة، تتحوّل عمليًا إلى قائمة |
النوع المتوازن هو الأهم عمليًا، لأن الشجرة غير المتوازنة قد "تنحرف" فتصبح كسلسلة خطية طويلة، فتضيع كل ميزة السرعة.
الفرق بين الشجرة الثنائية وشجرة البحث الثنائية
هنا يقع الخلط الأكثر شيوعًا. الاثنان ليسا الشيء نفسه:
- الشجرة الثنائية (Binary Tree): مجرّد قيد على العدد — عقدتان كحد أقصى لكل عقدة، دون أي شرط على ترتيب القيم.
- شجرة البحث الثنائية (Binary Search Tree - BST): شجرة ثنائية بقاعدة ترتيب صارمة: كل قيمة في الفرع الأيسر أصغر من العقدة، وكل قيمة في الفرع الأيمن أكبر منها.
هذا الترتيب هو مصدر القوة: للبحث عن قيمة، تقارنها بالجذر ثم تنزل يسارًا أو يمينًا، فتستبعد نصف الشجرة في كل خطوة. لهذا يكون البحث بمتوسط تعقيد O(log n) في الشجرة المتوازنة، مقابل O(n) في الشجرة الثنائية العادية التي تُجبرك على فحص كل عقدة.
باختصار: كل شجرة بحث ثنائية هي شجرة ثنائية، لكن العكس غير صحيح.
كيف تُقرأ الشجرة؟ طرق التنقّل (Traversal)
لا فائدة من هيكل بيانات لا تستطيع المرور على عناصره. للأشجار الثنائية ثلاث طرق تنقّل عمقية شائعة:
- In-order (يسار ← جذر ← يمين): في شجرة البحث الثنائية تُخرج القيم مرتّبة تصاعديًا — خدعة مفيدة جدًا.
- Pre-order (جذر ← يسار ← يمين): مفيدة لنسخ الشجرة أو حفظ بنيتها.
- Post-order (يسار ← يمين ← جذر): مفيدة لحذف الشجرة أو حساب قيم من الأسفل للأعلى.
وهناك أيضًا التنقّل المستوى تلو الآخر (Level-order) باستخدام الطابور (Queue)، ويُستعمل حين تريد معالجة الشجرة أفقيًا.
أين تُستخدم عمليًا؟
الأشجار الثنائية ليست تمرينًا نظريًا فقط:
- قواعد البيانات ومحرّكات البحث: فهرسة سريعة للوصول للسجلات (وإن كانت أنظمة كبرى تستخدم أشجارًا أوسع مثل B-Tree).
- الضغط: خوارزمية Huffman لضغط الملفات تبني شجرة ثنائية لترميز الحروف.
- أولويات المهام: الـ Heap (شجرة ثنائية كاملة) يدير طوابير الأولوية في أنظمة التشغيل والجدولة.
- تحليل التعابير الرياضية والبرمجية: المترجمات تمثّل المعادلات كأشجار.
نصيحة عملية وخطأ شائع
الخطأ الأكثر تكرارًا عند المبتدئين هو إهمال التوازن. إن أدخلت قيمًا مرتّبة أصلًا (1، 2، 3، 4...) في شجرة بحث ثنائية عادية، ستحصل على شجرة منحرفة تعمل بسرعة القائمة الخطية، وتضيع ميزة O(log n) بالكامل. الحل في التطبيقات الجادة هو استخدام أشجار متوازنة ذاتيًا مثل AVL أو Red-Black Tree، فهي تعيد ترتيب نفسها تلقائيًا عند كل إدخال أو حذف لتبقى قصيرة وسريعة.
نصيحة للفهم: ارسم الشجرة على ورقة وأنت تنفّذ الإدخال يدويًا خطوة بخطوة. هذا التمرين البسيط يرسّخ الفكرة أسرع من قراءة عشرة شروح.
الأسئلة الشائعة
هل كل شجرة ثنائية هي شجرة بحث ثنائية؟ لا. الشجرة الثنائية تحدّد فقط عدد الأبناء الأقصى (اثنان)، أما شجرة البحث فتضيف شرط الترتيب (الأصغر يسارًا والأكبر يمينًا).
ما تعقيد البحث في الشجرة الثنائية؟ في شجرة البحث المتوازنة يكون البحث بمتوسط O(log n). أما في شجرة عادية غير مرتّبة فقد تضطر لفحص كل العقد، أي O(n).
ما الفرق بين الشجرة "الكاملة" و"المثالية"؟ المثالية (Perfect) ممتلئة في كل مستوياتها بلا استثناء. الكاملة (Complete) ممتلئة في كل المستويات عدا الأخير الذي يُملأ من اليسار وقد يبقى ناقصًا.
بأي لغة أتعلّم الأشجار الثنائية؟ أي لغة تدعم المؤشرات أو الكائنات تكفي (Python، Java، C++، JavaScript). ركّز على الفكرة والتنفيذ اليدوي أولًا، فالمفهوم واحد بغضّ النظر عن اللغة.