في علوم الكمبيوتر، الشجرة الحمراء والسوداء هي بنية بيانات شجرة بحث ثنائية ذاتية التوازن تتميز بالتخزين السريع واسترجاع المعلومات المنظمة. تحتوي العقد الموجودة في الشجرة ذات اللونين الأحمر والأسود على جزء "لون" إضافي، يتم رسمه غالبًا باللونين الأحمر والأسود، مما يساعد على ضمان أن الشجرة متوازنة دائمًا تقريبًا.
عندما يتم تعديل الشجرة، يتم إعادة ترتيب الشجرة الجديدة وإعادة طلائها لاستعادة خصائص التلوين التي تحد من مدى عدم التوازن الذي يمكن أن تصبح عليه الشجرة في أسوأ الحالات. تم تصميم الخصائص بحيث يمكن تنفيذ عملية إعادة الترتيب وإعادة التلوين بكفاءة.
إن إعادة التوازن ليست مثالية، ولكنها تضمن البحث في
O
(
log
n
)
{\displaystyle O(\log n)}
الوقت، حيث
n
{\displaystyle n}
هو عدد الإدخالات في الشجرة. يتم تنفيذ عمليات الإدراج والحذف، إلى جانب إعادة ترتيب الشجرة وإعادة تلوينها، أيضًا
O
(
log
n
)
{\displaystyle O(\log n)}
الوقت.
يتطلب تتبع لون كل عقدة بت واحد فقط من المعلومات لكل عقدة لأنه يوجد لونين فقط (بسبب محاذاة الذاكرة الموجودة في بعض لغات البرمجة، قد يختلف استهلاك الذاكرة الحقيقي). لا تحتوي الشجرة على أي بيانات أخرى محددة كونها شجرة حمراء-سوداء، وبالتالي فإن بصمة الذاكرة الخاصة بها متطابقة تقريبًا مع بصمة شجرة البحث الثنائية الكلاسيكية (غير الملونة). في بعض الحالات، يمكن تخزين المعلومات المضافة دون أي تكلفة إضافية للذاكرة.