مفهوم الترابط (Threading)
الترابط، في سياق الأشجار الثنائية، يعني استبدال المؤشرات الفارغة في العقد بمؤشرات تشير إلى عقد أخرى في الشجرة. هذه المؤشرات “المترابطة” تسهل التنقل بين العقد دون الحاجة إلى استخدام مكدس (Stack) أو استدعاءات متكررة (Recursive Calls)، مما يقلل من استهلاك الذاكرة ويحسن الأداء.
هناك نوعان رئيسيان من الترابط:
- الترابط الأيسر (Left Threading): إذا كان المؤشر الأيسر لعقدة ما فارغًا، فإنه يشير إلى العقدة السابقة لها في ترتيب الاجتياز الداخلي (Inorder Predecessor).
- الترابط الأيمن (Right Threading): إذا كان المؤشر الأيمن لعقدة ما فارغًا، فإنه يشير إلى العقدة اللاحقة لها في ترتيب الاجتياز الداخلي (Inorder Successor).
أنواع الأشجار الثنائية المترابطة
توجد عدة أنواع من الأشجار الثنائية المترابطة، بناءً على كيفية تطبيق الترابط:
- الشجرة الثنائية المترابطة أحادية الاتجاه (One-way Threaded Binary Tree): في هذا النوع، يتم استخدام نوع واحد فقط من الترابط، إما الترابط الأيسر أو الترابط الأيمن.
- الشجرة الثنائية المترابطة ثنائية الاتجاه (Two-way Threaded Binary Tree): في هذا النوع، يتم استخدام كلا النوعين من الترابط، الترابط الأيسر والترابط الأيمن. وهذا يوفر سهولة أكبر في التنقل في كلا الاتجاهين.
- الشجرة الثنائية المترابطة الكاملة (Fully Threaded Binary Tree): في هذا النوع، جميع المؤشرات الفارغة يتم استبدالها بمؤشرات مترابطة.
مثال على شجرة ثنائية مترابطة ثنائية الاتجاه
لنفترض أن لدينا شجرة ثنائية بسيطة. في الشجرة الثنائية المترابطة ثنائية الاتجاه، إذا كانت العقدة ليس لديها ابن أيسر، فإن مؤشرها الأيسر يشير إلى العقدة السابقة في الترتيب الداخلي. وبالمثل، إذا كانت العقدة ليس لديها ابن أيمن، فإن مؤشرها الأيمن يشير إلى العقدة اللاحقة في الترتيب الداخلي.
مثال:
لنفترض أن لدينا الشجرة التالية:
D
/ \
B F
/ \ / \
A C E G
الترتيب الداخلي لهذه الشجرة هو: A, B, C, D, E, F, G.
في الشجرة الثنائية المترابطة المقابلة، ستكون الروابط كالتالي:
- العقدة A: مؤشرها الأيسر فارغ، ومؤشرها الأيمن يشير إلى B.
- العقدة B: مؤشرها الأيسر يشير إلى A، ومؤشرها الأيمن يشير إلى C.
- العقدة C: مؤشرها الأيسر يشير إلى B، ومؤشرها الأيمن يشير إلى D.
- العقدة D: مؤشرها الأيسر يشير إلى C، ومؤشرها الأيمن يشير إلى E.
- العقدة E: مؤشرها الأيسر يشير إلى D، ومؤشرها الأيمن يشير إلى F.
- العقدة F: مؤشرها الأيسر يشير إلى E، ومؤشرها الأيمن يشير إلى G.
- العقدة G: مؤشرها الأيسر يشير إلى F، ومؤشرها الأيمن فارغ.
فوائد استخدام الأشجار الثنائية المترابطة
توفر الأشجار الثنائية المترابطة العديد من المزايا مقارنة بالأشجار الثنائية التقليدية، ومن أهم هذه المزايا:
- كفاءة اجتياز الشجرة: يمكن اجتياز الشجرة الثنائية المترابطة في ترتيب معين (مثل الترتيب الداخلي) بكفاءة عالية دون الحاجة إلى استخدام مكدس أو استدعاءات متكررة. هذا يقلل من استهلاك الذاكرة ويحسن الأداء، خاصة في الأشجار الكبيرة.
- توفير الذاكرة: من خلال استغلال المؤشرات الفارغة لتخزين معلومات الترابط، يمكن توفير الذاكرة التي كانت ستستخدم لتخزين مكدس الاجتياز.
- سهولة التنقل: يسهل الترابط التنقل بين العقد في الشجرة، سواء كان ذلك في اتجاه واحد أو في كلا الاتجاهين (في حالة الأشجار الثنائية المترابطة ثنائية الاتجاه).
- الوصول السريع إلى العقد السابقة واللاحقة: يمكن الوصول بسرعة إلى العقدة السابقة أو اللاحقة لعقدة معينة في الترتيب المحدد دون الحاجة إلى اجتياز جزء كبير من الشجرة.
عيوب استخدام الأشجار الثنائية المترابطة
على الرغم من المزايا العديدة، توجد بعض العيوب لاستخدام الأشجار الثنائية المترابطة:
- التعقيد: تعتبر عمليات الإدراج والحذف في الأشجار الثنائية المترابطة أكثر تعقيدًا من الأشجار الثنائية التقليدية، حيث يجب تحديث المؤشرات المترابطة بشكل صحيح للحفاظ على سلامة الشجرة.
- زيادة استهلاك الذاكرة (بشكل طفيف): تحتاج كل عقدة إلى بت إضافي (Flag) للإشارة إلى ما إذا كان المؤشر الأيسر أو الأيمن هو مؤشر مترابط أم مؤشر إلى ابن. على الرغم من أن هذا يزيد من استهلاك الذاكرة، إلا أن الزيادة عادة ما تكون طفيفة مقارنة بالمزايا التي توفرها الشجرة المترابطة.
تطبيقات الأشجار الثنائية المترابطة
تستخدم الأشجار الثنائية المترابطة في مجموعة متنوعة من التطبيقات، بما في ذلك:
- تنفيذ المترجمات (Compilers): تستخدم في تحليل وتوليد التعليمات البرمجية.
- قواعد البيانات: تستخدم في فهرسة البيانات وتسريع عمليات البحث.
- معالجة النصوص: تستخدم في تمثيل النصوص وتنفيذ عمليات البحث والاستبدال.
- أنظمة التشغيل: تستخدم في إدارة الذاكرة وتنفيذ العمليات.
العمليات الأساسية على الأشجار الثنائية المترابطة
تشمل العمليات الأساسية على الأشجار الثنائية المترابطة:
- الإدراج (Insertion): إضافة عقدة جديدة إلى الشجرة مع الحفاظ على الترابط الصحيح.
- الحذف (Deletion): إزالة عقدة من الشجرة مع تحديث المؤشرات المترابطة للعقد المجاورة.
- البحث (Search): البحث عن عقدة معينة في الشجرة.
- الاجتياز (Traversal): زيارة جميع العقد في الشجرة بترتيب معين.
تتطلب عمليات الإدراج والحذف اهتمامًا خاصًا لضمان الحفاظ على المؤشرات المترابطة صحيحة. يجب تحديث المؤشرات المترابطة للعقد المجاورة لتعكس التغييرات في بنية الشجرة.
مثال على كود (بشكل مبسط) لتمثيل عقدة في شجرة ثنائية مترابطة (بلغة C++)
struct ThreadedNode {
int data;
ThreadedNode* left;
ThreadedNode* right;
bool leftThread; // true if left pointer is a thread
bool rightThread; // true if right pointer is a thread
};
في هذا المثال، يمثل المتغيران `leftThread` و `rightThread` أعلامًا منطقية تشير إلى ما إذا كان المؤشر الأيسر أو الأيمن هو مؤشر مترابط (يشير إلى العقدة السابقة أو اللاحقة) أم مؤشر إلى ابن.
خاتمة
الشجرة الثنائية المترابطة هي بنية بيانات قوية توفر كفاءة عالية في اجتياز الأشجار الثنائية. من خلال استغلال المؤشرات الفارغة لتخزين معلومات الترابط، يمكن تجنب الحاجة إلى استخدام مكدس أو استدعاءات متكررة، مما يقلل من استهلاك الذاكرة ويحسن الأداء. على الرغم من أن عمليات الإدراج والحذف أكثر تعقيدًا، إلا أن المزايا التي توفرها الأشجار الثنائية المترابطة تجعلها خيارًا جذابًا في العديد من التطبيقات، خاصة عندما يكون اجتياز الشجرة بكفاءة أمرًا بالغ الأهمية.