الفصل CH4-2: الأشجار الثنائية للبحث (ABR) – الخوارزميات وهياكل المعطيات – Algorithmique et structure de données (S3)

تتناول هذه المحاضرة مفهوم الأشجار الثنائية للبحث (ABR) باعتبارها بنية بيانات تعتمد على وجود علاقة ترتيب بين المفاتيح، وتهدف إلى تسريع عمليات البحث مع المحافظة على سهولة الإدراج والحذف. تبدأ بعرض الدوافع لاستخدام هذه البنية ثم تقدم تعريفها الرسمي والخاصية الأساسية التي تفرض أن تكون جميع قيم الفرع الأيسر أصغر أو تساوي قيمة العقدة، بينما تكون قيم الفرع الأيمن أكبر أو تساويها. تعرض الوثيقة أمثلة توضيحية لبناء أشجار البحث الثنائية، ثم تنتقل إلى طرق تمثيلها سواء بالتمثيل الساكن باستخدام الجداول أو بالتمثيل الديناميكي باستعمال المؤشرات مع مثال لتعريف العقدة في الخوارزمية وبلغة C/C++. كما تستعرض العمليات الأساسية على الشجرة مثل الاجتياز، والبحث عن مفتاح، وإدراج مفتاح جديد، وإيجاد الخلف، وحذف عقدة، بالإضافة إلى فكرة موازنة الشجرة وأثرها على الأداء. تمثل هذه المحاضرة أساساً مهماً لفهم هياكل البيانات الشجرية وتطبيقاتها في تنظيم البيانات وتحسين كفاءة الخوارزميات، كما تعد مرجعاً مباشراً للتحضير للأعمال الموجهة والاختبارات المتعلقة بالأشجار الثنائية للبحث.