ما هي الشجرة الحمراء والسوداء (Red-Black Tree)؟ شرح مبسّط بأمثلة
الشجرة الحمراء والسوداء (Red-Black Tree) هي شجرة بحث ثنائية «تُوازن نفسها ذاتيًا»، أي أنها تُعيد ترتيب عُقدها تلقائيًا بعد كل إضافة أو حذف حتى يبقى ارتفاعها قريبًا من اللوغاريتمي. النتيجة العملية: عمليات البحث والإضافة والحذف تتم جميعها في زمن O(log n) في أسوأ الحالات، وليس فقط في المتوسط. تحقق هذا التوازن عبر إعطاء كل عقدة لونًا (أحمر أو أسود) وتطبيق مجموعة قواعد صارمة تمنع الشجرة من أن تصبح «طويلة ونحيلة» مثل قائمة مرتبطة.
لماذا نحتاج هذا التلوين أصلًا؟ لأن شجرة البحث الثنائية العادية قد تنهار في أداء. لو أدخلت أرقامًا مرتبة تصاعديًا (1، 2، 3، 4...) في شجرة عادية، فستتحول إلى ما يشبه السلسلة، ويصبح البحث فيها O(n) بدل O(log n). الألوان هنا ليست زينة، بل «عدّاد» ذكي يجبر الشجرة على البقاء متوازنة دون الحاجة لإعادة بنائها بالكامل.
القواعد الخمس التي تحكم الشجرة
كل شجرة حمراء وسوداء صحيحة تلتزم بخمس قواعد. من فهمها يفهم الفكرة كلها:
- كل عقدة إمّا حمراء أو سوداء.
- الجذر (Root) أسود دائمًا.
- كل ورقة فارغة (تُسمى NIL أو العقدة الخارجية) تُعتبر سوداء.
- لا يمكن أن تتجاور عقدتان حمراوان؛ أي أن ابنَي العقدة الحمراء يجب أن يكونا أسودَين (لا يوجد «أحمر فوق أحمر»).
- كل مسار من أي عقدة نزولًا إلى الأوراق يمر بالعدد نفسه من العقد السوداء (يُسمى هذا العدد «الارتفاع الأسود»).
القاعدتان الرابعة والخامسة هما جوهر السحر. تخيّل أنهما تقولان: «العُقد الحمراء مسموح بها لكن ممنوع أن تتكدّس، وعدد العُقد السوداء متساوٍ في كل الفروع». هذا وحده يضمن أن أطول مسار في الشجرة لا يتجاوز ضعف أقصر مسار، فيبقى الارتفاع تحت السيطرة.
كيف توازن الشجرة نفسها: التلوين والدوران
عند إضافة عقدة جديدة نلوّنها بالأحمر مبدئيًا، لأن الأحمر لا يزيد «الارتفاع الأسود» فلا يكسر القاعدة الخامسة فورًا. لكنه قد يكسر القاعدة الرابعة إذا كان أبوها أحمر أيضًا. عندها نستخدم إحدى أداتين لإصلاح الوضع:
- إعادة التلوين (Recoloring): نبدّل ألوان بعض العقد (مثلًا تحويل الأب والعم من أحمر إلى أسود والجد من أسود إلى أحمر) لاستعادة القواعد دون تحريك أي عقدة.
- الدوران (Rotation): نغيّر البنية فعليًا بتدوير مجموعة من ثلاث عقد يمينًا أو يسارًا، فتتبدل علاقات الأب والابن. الدوران عملية محلية سريعة جدًا لا تلمس إلا عُقدًا قليلة قرب موضع التغيير.
النقطة المهمة عمليًا: كل عملية إصلاح لا تحتاج سوى عدد محدود من الدورانات (دورانان كحد أقصى للإضافة، وثلاثة للحذف)، ولهذا تبقى التكلفة لوغاريتمية ولا تنفجر مع كبر البيانات.
أين تُستخدم فعليًا؟
هذه ليست بنية أكاديمية فقط؛ أنت تستخدمها يوميًا دون أن تدري:
- في لغة ++C: الحاويات
std::mapوstd::setمبنية غالبًا على شجرة حمراء وسوداء. - في جافا:
TreeMapوTreeSet. - داخل نواة لينكس: لجدولة العمليات (CFS Scheduler) وإدارة مناطق الذاكرة الافتراضية.
السبب في هذا الانتشار أن الشجرة الحمراء والسوداء تقدّم توازنًا «كافيًا» بتكلفة صيانة أقل من البدائل الأكثر صرامة، فهي حل وسط عملي ممتاز.
Red-Black Tree أم AVL Tree؟
كلاهما شجرة بحث ثنائية موازِنة ذاتيًا، والاختيار بينهما يعتمد على طبيعة الاستخدام:
| المعيار | الشجرة الحمراء والسوداء | شجرة AVL |
|---|---|---|
| صرامة التوازن | متوازنة تقريبًا (أقل صرامة) | متوازنة بدقة أعلى |
| سرعة البحث | جيدة | أسرع قليلًا (شجرة أقصر) |
| سرعة الإضافة/الحذف | أسرع (دورانات أقل) | أبطأ (توازن أكثر تكرارًا) |
| الأنسب لِـ | كثرة الإضافة والحذف | كثرة البحث والقراءة |
القاعدة العملية: إن كان تطبيقك يكثر فيه التعديل (إدخال وحذف مستمر) فالحمراء والسوداء أفضل؛ وإن كان يغلب عليه البحث فقد تتفوق AVL قليلًا.
نصيحة عملية وخطأ شائع
الخطأ الأكثر شيوعًا عند التعلّم هو حفظ القواعد الخمس صمّاء دون ربطها بهدفها. لا تحفظ القاعدة الخامسة كنص؛ افهمها كـ«ضمان أن كل الفروع متساوية في العُقد السوداء». وعند التنفيذ، لا تنسَ التعامل مع العُقد الفارغة NIL كعقد سوداء حقيقية — تجاهلها هو سبب أغلب الأخطاء في كتابة دوال الحذف. نصيحة أخيرة: ارسم الشجرة يدويًا على ورقة وأنت تُدخل 5 أو 6 أرقام وتُطبّق الدورانات؛ لا شيء يرسّخ الفهم مثل رؤية الدوران يحدث أمامك.
الأسئلة الشائعة
هل ألوان العقد لها معنى بصري حقيقي؟ لا، «الأحمر» و«الأسود» مجرد اسمين لبِتّ واحد (0 أو 1) يُخزَّن مع كل عقدة. اختير اللونان تاريخيًا لأنهما كانا متاحين في طابعات المجلات وقت نشر الفكرة عام 1978.
كم يبلغ ارتفاع الشجرة في أسوأ حالة؟ لا يتجاوز 2 × log₂(n+1) تقريبًا، أي إنه يبقى لوغاريتميًا مهما كثرت البيانات، وهذا ما يضمن كفاءة كل العمليات.
هل الشجرة الحمراء والسوداء أفضل من شجرة البحث الثنائية العادية دائمًا؟ من حيث ضمان الأداء نعم، لأنها تمنع الحالة السيئة O(n). لكنها أعقد في البرمجة وتستهلك بِتًّا إضافيًا لكل عقدة، فإن كانت بياناتك صغيرة أو ثابتة قد تكفيك شجرة أبسط.
من أين أبدأ لتطبيقها عمليًا؟
لا تعِد اختراع العجلة في مشروع إنتاجي؛ استخدم std::map أو TreeMap الجاهزة. اكتب التنفيذ من الصفر فقط لأغراض التعلّم وفهم الدورانات والتلوين خطوة بخطوة.