ملخص

مراجعة النقاط الرئيسية

• الشجرة الثنائية بنية بيانات غير خطية تجسّد منطق التقسيم والتغلب القائم على الانقسام إلى قسمين. وتحتوي كل عقدة في الشجرة الثنائية على قيمة ومؤشرين يشيران إلى ابنيها الأيسر والأيمن.
• بالنسبة إلى عقدة معينة في شجرة ثنائية، تُسمّى الشجرة المكوّنة من ابنها الأيسر (الأيمن) وجميع العقد الواقعة تحته الشجرة الفرعية اليسرى (اليمنى) لتلك العقدة.
• تشمل المصطلحات المتعلقة بالأشجار الثنائية العقدة الجذر والعقدة الورقة والمستوى والدرجة والضلع والارتفاع والعمق.
• عمليات تهيئة الشجرة الثنائية وإدراج العقد وحذفها مشابهة لتلك الخاصة بالقوائم المترابطة.
• تشمل الأنواع الشائعة من الأشجار الثنائية الأشجار الثنائية التامة، والأشجار الثنائية الكاملة، والأشجار الثنائية الممتلئة، والأشجار الثنائية المتوازنة. والشجرة الثنائية التامة هي الشكل المثالي، بينما تمثّل القائمة المترابطة أسوأ حالة متدهورة.
• يمكن تمثيل الشجرة الثنائية بمصفوفة عبر ترتيب قيم العقد والخانات الفارغة وفق تسلسل الاجتياز حسب المستوى، وتنفيذ المؤشرات اعتماداً على علاقة تعيين الفهارس بين العقدة الأب وأبنائها.
• الاجتياز حسب المستوى لشجرة ثنائية طريقة بحث بالعرض أولاً تتقدّم مستوى بعد مستوى، وتُنفَّذ عادةً باستخدام طابور.
• تنتمي الاجتيازات المسبق والوسطي واللاحق جميعاً إلى البحث بالعمق أولاً، الذي يتقدّم بالمضي إلى أبعد عمق ممكن ثم التراجع، ويستخدم التعاود عادةً.
• شجرة البحث الثنائية بنية بيانات فعّالة للبحث عن العناصر، إذ يكون التعقيد الزمني لعمليات البحث والإدراج والحذف جميعاً $O(\log n)$. وعندما تتدهور شجرة البحث الثنائية إلى قائمة مترابطة، تتدهور جميع التعقيدات الزمنية إلى $O(n)$.
• شجرة AVL، وتُعرف أيضاً بشجرة البحث الثنائية المتوازنة، تضمن بقاء الشجرة متوازنة بعد عمليات إدراج العقد وحذفها المتواصلة عبر عمليات الدوران.
• تشمل عمليات الدوران في أشجار AVL الدوران الأيمن والدوران الأيسر والدوران الأيمن ثم الأيسر والدوران الأيسر ثم الأيمن. وبعد إدراج العقد أو حذفها، تُجري أشجار AVL عمليات دوران من الأسفل إلى الأعلى لاستعادة التوازن.

أسئلة وأجوبة

س: في شجرة ثنائية تحتوي على عقدة واحدة فقط، هل يساوي كل من ارتفاع الشجرة وعمق العقدة الجذر $0$؟

نعم، لأن الارتفاع والعمق يُعرَّفان عادةً بأنهما عدد الأضلاع على المسار.

س: يتم الإدراج والحذف في الشجرة الثنائية عموماً عبر مجموعة من العمليات. فماذا تعني «مجموعة من العمليات» هنا؟ وهل تعني تحرير موارد العقد الأبناء؟

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

س: لماذا يحتوي الاجتياز بالعمق أولاً للأشجار الثنائية على ثلاثة ترتيبات: المسبق والوسطي واللاحق، وما استخداماتها؟

على غرار الاجتياز الأمامي والعكسي للمصفوفات، فإن الاجتيازات المسبق والوسطي واللاحق ثلاث طرق لاجتياز الشجرة الثنائية تتيح لنا الحصول على نتيجة اجتياز بترتيب معين. فمثلاً في شجرة البحث الثنائية، وبما أن العقد تحقق العلاقة left child node value < root node value < right child node value، لا نحتاج إلا إلى اجتياز الشجرة بأولوية «اليسار $\rightarrow$ الجذر $\rightarrow$ اليمين» للحصول على تسلسل عقد مرتب.

س: في عملية الدوران الأيمن التي تعالج العلاقة بين العقد غير المتوازنة node وchild وgrand_child، ألا تُفقد الصلة بين node وعقدة أبيه بعد الدوران الأيمن؟

علينا النظر إلى هذه المسألة من منظور تعاودي. فعملية الدوران الأيمن right_rotate(root) تمرّر عقدة الجذر للشجرة الفرعية، وتعيد في النهاية عقدة جذر الشجرة الفرعية بعد الدوران عبر return child. وتكتمل الصلة بين عقدة جذر الشجرة الفرعية وعقدة أبيه بعد عودة الدالة، وهي ليست ضمن نطاق صيانة عملية الدوران الأيمن.

س: في C++، تُقسَّم الدوال إلى أقسام private وpublic. فما الاعتبارات وراء ذلك؟ ولماذا وُضعت الدالة height() والدالة updateHeight() في public وprivate على الترتيب؟

يعتمد الأمر أساساً على نطاق استخدام الدالة. فإذا كانت دالة تُستخدم داخل الفئة فقط، فإنها تُصمَّم كـ private. فمثلاً لا معنى لاستدعاء المستخدم updateHeight() منفردة، إذ هي مجرد خطوة في عمليات الإدراج أو الحذف. أما height() فتُستخدم للوصول إلى ارتفاع العقدة، على غرار vector.size()، لذا ضُبطت كـ public تسهيلاً للاستخدام.

س: كيف تبني شجرة بحث ثنائية من مجموعة بيانات إدخال؟ وهل اختيار العقدة الجذر مهم جداً؟

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

س: في Java، هل يجب دائماً استخدام الدالة equals() لمقارنة السلاسل النصية؟

في Java، تُستخدم == لأنواع البيانات الأولية لمقارنة ما إذا كانت قيم متغيرين متساوية. أما لأنواع المراجع، فمبدأ عمل الرمزين مختلف.

• ==: تُستخدم لمقارنة ما إذا كان متغيران يشيران إلى الكائن نفسه، أي ما إذا كان موضعهما في الذاكرة نفسه.
• equals(): تُستخدم لمقارنة ما إذا كانت قيم كائنين متساويتين.

لذلك، إذا أردنا مقارنة القيم، ينبغي استخدام equals(). غير أن السلاسل النصية المُهيَّأة عبر String a = "hi"; String b = "hi"; تُخزَّن في مجمّع ثوابت السلاسل النصية وتشير إلى الكائن نفسه، لذا يمكن أيضاً استخدام a == b لمقارنة محتوى السلسلتين.

س: قبل الوصول إلى المستوى السفلي، هل عدد العقد في الطابور $2^h$ في الاجتياز بالعرض أولاً؟

نعم، فمثلاً شجرة ثنائية ممتلئة ارتفاعها $h = 2$ فيها إجمالاً $n = 7$ عقدة، وعندها يكون في المستوى السفلي $4 = 2^h = (n + 1) / 2$ عقدة.