<![CDATA[
مقدمة
في علم الحاسوب، الشجرة الثنائية هي هيكل بيانات شجري تتكون فيه كل عقدة من عقدتين فرعيتين على الأكثر، يُشار إليهما عادةً بالفرع الأيسر والفرع الأيمن. تُستخدم الأشجار الثنائية لتمثيل البيانات الهرمية، وتنفيذ خوارزميات البحث والفرز، والتعبير عن التعابير الرياضية.
تتميز الأشجار الثنائية ببساطتها وفاعليتها، مما يجعلها هيكل بيانات أساسيًا في علوم الحاسوب. تُستخدم على نطاق واسع في مختلف التطبيقات، بما في ذلك قواعد البيانات، والمترجمات، ونظم التشغيل، والذكاء الاصطناعي.
المصطلحات الأساسية
لفهم الأشجار الثنائية بشكل كامل، من الضروري التعرف على بعض المصطلحات الأساسية:
- العقدة (Node): الوحدة الأساسية في الشجرة، تحتوي على بيانات ومؤشرات إلى العقد الفرعية.
- الجذر (Root): العقدة العليا في الشجرة، ليس لها عقدة أصل.
- الفرع (Branch): الرابط بين عقدتين، يمثل العلاقة بين الأصل والفرع.
- الورقة (Leaf): عقدة ليس لها أي عقد فرعية.
- الأصل (Parent): العقدة التي لديها فرع إلى عقدة أخرى.
- الفرع (Child): العقدة التي لديها أصل.
- العمق (Depth): عدد الفروع على طول المسار من الجذر إلى العقدة.
- الارتفاع (Height): عدد الفروع على طول أطول مسار من العقدة إلى ورقة. ارتفاع الشجرة هو ارتفاع جذرها.
- الشجرة الفرعية (Subtree): جزء من الشجرة يتكون من عقدة وأحفادها.
أنواع الأشجار الثنائية
توجد أنواع مختلفة من الأشجار الثنائية، تختلف في خصائصها واستخداماتها:
- الشجرة الثنائية الكاملة (Complete Binary Tree): شجرة ثنائية يتم فيها ملء جميع المستويات باستثناء ربما المستوى الأخير، والذي يتم ملؤه من اليسار إلى اليمين.
- الشجرة الثنائية التامة (Perfect Binary Tree): شجرة ثنائية يتم فيها ملء جميع المستويات بالكامل.
- الشجرة الثنائية المتوازنة (Balanced Binary Tree): شجرة ثنائية يكون فيها ارتفاع الأشجار الفرعية لكل عقدة متوازنًا بشكل معقول. تضمن هذه الخاصية أداءً فعالاً لعمليات البحث والإدراج والحذف.
- شجرة البحث الثنائية (Binary Search Tree – BST): نوع خاص من الأشجار الثنائية حيث تكون قيمة كل عقدة أكبر من قيم جميع العقد في شجرتها الفرعية اليسرى وأصغر من قيم جميع العقد في شجرتها الفرعية اليمنى. تسهل أشجار البحث الثنائية عمليات البحث والفرز الفعالة.
تمثيل الأشجار الثنائية
يمكن تمثيل الأشجار الثنائية بطريقتين رئيسيتين:
- التمثيل القائم على المؤشرات (Pointer-based Representation): تستخدم كل عقدة مؤشرات لتخزين عناوين العقد الفرعية اليمنى واليسرى. هذه هي الطريقة الأكثر شيوعًا لتمثيل الأشجار الثنائية.
- التمثيل القائم على المصفوفة (Array-based Representation): يتم تخزين العقد في مصفوفة، ويتم تحديد موقع العقد الفرعية باستخدام صيغ رياضية. هذه الطريقة أقل شيوعًا، ولكنها يمكن أن تكون مفيدة في بعض الحالات.
العمليات على الأشجار الثنائية
تتضمن العمليات الأساسية التي يمكن إجراؤها على الأشجار الثنائية:
- الإجتياز (Traversal): زيارة جميع العقد في الشجرة بترتيب معين. توجد ثلاث طرق رئيسية للإجتياز:
- الإجتياز الترتيبي (Inorder Traversal): تتم زيارة الشجرة الفرعية اليسرى أولاً، ثم العقدة الجذرية، ثم الشجرة الفرعية اليمنى.
- الإجتياز القبلي (Preorder Traversal): تتم زيارة العقدة الجذرية أولاً، ثم الشجرة الفرعية اليسرى، ثم الشجرة الفرعية اليمنى.
- الإجتياز البعدي (Postorder Traversal): تتم زيارة الشجرة الفرعية اليسرى أولاً، ثم الشجرة الفرعية اليمنى، ثم العقدة الجذرية.
- البحث (Search): البحث عن عقدة معينة في الشجرة.
- الإدراج (Insertion): إضافة عقدة جديدة إلى الشجرة.
- الحذف (Deletion): حذف عقدة من الشجرة.
تطبيقات الأشجار الثنائية
تستخدم الأشجار الثنائية في العديد من التطبيقات المختلفة، بما في ذلك:
- قواعد البيانات: تستخدم أشجار البحث الثنائية لإنشاء فهارس لتسريع عمليات البحث.
- المترجمات: تستخدم الأشجار الثنائية لتمثيل التعابير الرياضية وتحليل التعليمات البرمجية.
- نظم التشغيل: تستخدم الأشجار الثنائية لإدارة الملفات والعمليات.
- الذكاء الاصطناعي: تستخدم الأشجار الثنائية لتمثيل المعرفة وتنفيذ خوارزميات التعلم الآلي.
- ضغط البيانات: تستخدم أشجار هوفمان (Huffman trees)، وهي نوع من الأشجار الثنائية، في خوارزميات ضغط البيانات.
- التوجيه (Routing): تستخدم بعض بروتوكولات التوجيه هياكل بيانات شبيهة بالأشجار الثنائية لتحديد أفضل مسار لنقل البيانات.
مثال على شجرة بحث ثنائية (Binary Search Tree)
شجرة البحث الثنائية (BST) هي نوع خاص من الأشجار الثنائية حيث يتم تنظيم العقد بطريقة معينة لتسهيل عمليات البحث الفعالة. القاعدة الرئيسية لشجرة البحث الثنائية هي أن قيمة أي عقدة في الشجرة يجب أن تكون أكبر من جميع القيم في الشجرة الفرعية اليسرى وأصغر من جميع القيم في الشجرة الفرعية اليمنى. هذه الخاصية تسمح بإجراء بحث ثنائي (Binary Search) فعال على الشجرة.
مثال:
لنفترض أن لدينا مجموعة القيم التالية: 50, 30, 20, 40, 70, 60, 80. يمكننا بناء شجرة بحث ثنائية بهذه القيم على النحو التالي:
50
/ \
30 70
/ \ / \
20 40 60 80
في هذه الشجرة:
- 50 هي العقدة الجذرية.
- جميع القيم في الشجرة الفرعية اليسرى لـ 50 (وهي 30, 20, 40) أصغر من 50.
- جميع القيم في الشجرة الفرعية اليمنى لـ 50 (وهي 70, 60, 80) أكبر من 50.
- تتبع كل شجرة فرعية نفس القاعدة.
للبحث عن قيمة معينة في شجرة البحث الثنائية، نبدأ من الجذر ونقارن القيمة المراد البحث عنها بقيمة العقدة الحالية. إذا كانت القيمة المراد البحث عنها أصغر من قيمة العقدة الحالية، فإننا ننتقل إلى الشجرة الفرعية اليسرى. إذا كانت القيمة المراد البحث عنها أكبر من قيمة العقدة الحالية، فإننا ننتقل إلى الشجرة الفرعية اليمنى. نكرر هذه العملية حتى نجد القيمة المراد البحث عنها أو نصل إلى ورقة (Leaf). إذا وصلنا إلى ورقة ولم نجد القيمة المراد البحث عنها، فهذا يعني أن القيمة غير موجودة في الشجرة.
أداء العمليات على الأشجار الثنائية
يعتمد أداء العمليات على الأشجار الثنائية بشكل كبير على نوع الشجرة وما إذا كانت متوازنة أم لا. في شجرة البحث الثنائية المتوازنة (مثال: شجرة AVL أو شجرة أحمر-أسود)، يمكن أن يكون أداء عمليات البحث والإدراج والحذف فعالاً جداً، حيث يكون متوسط الوقت اللازم لإجراء هذه العمليات هو O(log n)، حيث n هو عدد العقد في الشجرة. أما في شجرة البحث الثنائية غير المتوازنة، فقد يصل أداء هذه العمليات إلى O(n) في أسوأ الحالات، وهو ما يعادل أداء البحث الخطي في قائمة غير مرتبة.
لذلك، من المهم استخدام الأشجار الثنائية المتوازنة في التطبيقات التي تتطلب أداءً عالياً لعمليات البحث والإدراج والحذف.
خاتمة
الشجرة الثنائية هي هيكل بيانات قوي ومتعدد الاستخدامات. فهم الأنواع المختلفة من الأشجار الثنائية، وكيفية تمثيلها، والعمليات التي يمكن إجراؤها عليها، أمر ضروري لأي عالم حاسوب أو مبرمج. تُستخدم الأشجار الثنائية في مجموعة واسعة من التطبيقات، وتوفر طريقة فعالة لتمثيل البيانات الهرمية وتنفيذ خوارزميات البحث والفرز.