شجرة حمراء وسوداء

تصغير|يسار|275px|مثال على شجرة حمراء سوداء

في علوم الكمبيوتر، **الشجرة الحمراء والسوداء** هي بنية بيانات شجرة بحث ثنائية ذاتية التوازن تتميز بالتخزين السريع واسترجاع المعلومات المنظمة. تحتوي العقد الموجودة في الشجرة ذات اللونين الأحمر والأسود على جزء "لون" إضافي، يتم رسمه غالبًا باللونين الأحمر والأسود، مما يساعد على ضمان أن الشجرة متوازنة دائمًا تقريبًا.

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

إن إعادة التوازن ليست مثالية، ولكنها تضمن البحث في O(\log n) الوقت، حيث n هو عدد الإدخالات في الشجرة. يتم تنفيذ عمليات الإدراج والحذف، إلى جانب إعادة ترتيب الشجرة وإعادة تلوينها، أيضًا O(\log n) الوقت.

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

## التاريخ
في عام 1972، اخترع رودولف باير بنية بيانات كانت عبارة عن حالة خاصة من الدرجة الرابعة لشجرة B. حافظت هذه الأشجار على جميع المسارات من الجذر إلى الورقة بنفس عدد العقد، مما أدى إلى إنشاء أشجار متوازنة تمامًا. ومع ذلك، فإنها لم تكن أشجار بحث *ثنائية*. أطلق باير عليهم اسم "شجرة B الثنائية المتماثلة" في ورقته البحثية، وفي وقت لاحق أصبحت شائعة  أو حتى 2-3 أشجار.

في ورقة بحثية عام 1978 بعنوان "إطار ثنائي اللون للأشجار المتوازنة"، استنتج ليونيداس جيه. جويباس  الشجرة الحمراء والسوداء من شجرة B الثنائية المتماثلة. تم اختيار اللون "الأحمر" لأنه كان اللون الأفضل مظهرًا الذي أنتجته طابعة الليزر الملونة المتاحة للمؤلفين أثناء العمل في زيروكس بارك. رد آخر من غيباس ينص على أن ذلك كان بسبب الأقلام الحمراء والسوداء المتاحة لهم لرسم الأشجار.

في عام 1993، قدم أرن أندرسون فكرة الشجرة ذات الميل الأيمن لتبسيط عمليات الإدراج والحذف.

في عام 1999، أظهر  كيفية جعل عملية الإدخال عملية وظيفية بحتة. كانت وظيفة التوازن الخاصة بها بحاجة إلى الاهتمام بأربع حالات غير متوازنة وحالة متوازنة افتراضية واحدة فقط.

استخدمت الخوارزمية الأصلية 8 حالات غير متوازنة، لكن كورمن وآخرون (2001) قلصوا ذلك إلى 6 حالات غير متوازنة. أظهر سيدجويك أن عملية الإدراج يمكن تنفيذها في 46 سطرًا فقط من جافا. في عام 2008، اقترح سيدجويك ، مستفيدًا من فكرة أندرسون التي قامت بتبسيط عمليات الإدراج والحذف. سمح سيدجويك في البداية بالعقد التي يكون طفليها باللون الأحمر، مما يجعل أشجاره أشبه بـ 2-3-4 أشجار، ولكن في وقت لاحق تمت إضافة هذا القيد، مما يجعل الأشجار الجديدة أشبه بـ 2-3 أشجار. قام سيدجويك بتنفيذ خوارزمية الإدراج في 33 سطرًا فقط، مما أدى إلى تقصير 46 سطرًا من الكود الأصلي بشكل كبير.

## المصطلحات

يتم تعريف **العمق الأسود** للعقدة على أنه عدد العقد السوداء من الجذر إلى تلك العقدة (أي عدد الأسلاف السود). **الارتفاع الأسود** لشجرة حمراء-سوداء هو عدد العقد السوداء في أي مسار من الجذر إلى الأوراق، والذي، وفقًا للمتطلب 4، يكون ثابتًا (بدلاً من ذلك، يمكن تعريفه على أنه العمق الأسود لأي عقدة ورقة). الارتفاع الأسود للعقدة هو الارتفاع الأسود للشجرة الفرعية التي تتبعها. في هذه المقالة، يجب تعيين الارتفاع الأسود للعقدة الفارغة إلى 0، لأن شجرتها الفرعية فارغة كما يقترح الشكل التوضيحي، وارتفاع شجرتها هو 0 أيضًا.

## الخصائص
بالإضافة إلى المتطلبات المفروضة على شجرة البحث الثنائية، يجب استيفاء المتطلبات التالية بواسطة 

# كل عقدة تكون إما حمراء أو سوداء.
# تعتبر جميع العقد الفارغة سوداء.
# العقدة الحمراء ليس لها طفل أحمر.
# كل مسار من عقدة معينة إلى أي من عقد أوراقها يمر عبر نفس عدد العقد السوداء.
# (الاستنتاج) إذا كان للعقدة **N** طفل واحد فقط، فيجب أن يكون الطفل باللون الأحمر. إذا كان الطفل أسود اللون، فإن أوراقه ستجلس على عمق أسود مختلف عن عقدة **N**' null (والتي تعتبر سوداء وفقًا للقاعدة 2)، مما ينتهك المتطلب 4.

يزعم بعض المؤلفين، مثل كورمن وآخرون، أن "الجذر أسود" كمتطلب خامس؛ ولكن ليس ميلهورن وساندرز أو سيدجويك وواين. نظرًا لأنه يمكن دائمًا تغيير الجذر من الأحمر إلى الأسود، فإن هذه القاعدة لها تأثير ضئيل على التحليل. تغفل هذه المقالة أيضًا هذه النقطة، لأنها تزعج الخوارزميات التكرارية والإثباتات قليلاً.

على سبيل المثال، كل شجرة ثنائية مثالية تتكون فقط من عقد سوداء هي شجرة حمراء-سوداء.

لا تؤثر عمليات القراءة فقط، مثل البحث أو عبور الشجرة، على أي من المتطلبات. على النقيض من ذلك، فإن عمليات التعديل الإدراج والحذف تحافظ بسهولة على المتطلبات 1 و2، ولكن فيما يتعلق بالمتطلبات الأخرى يجب بذل بعض الجهد الإضافي، لتجنب إدخال انتهاك للمتطلب 3، والذي يسمى **انتهاكًا أحمر**، أو للمتطلب 4، والذي يسمى **انتهاكًا أسود**.

تفرض المتطلبات خاصية أساسية للأشجار ذات اللونين الأحمر والأسود: *المسار من الجذر إلى أبعد ورقة لا يزيد عن ضعف طول المسار من الجذر إلى أقرب ورقة*. النتيجة هي أن الشجرة متوازنة الارتفاع. نظرًا لأن العمليات مثل الإدراج والحذف والبحث عن القيم تتطلب أسوأ وقت يتناسب مع الارتفاع h من الشجرة، هذا الحد الأعلى للارتفاع يسمح للأشجار الحمراء والسوداء بأن تكون فعالة في أسوأ الحالات، أي اللوغاريتمية في العدد n من الإدخالات، أي  (خاصية مشتركة بين جميع الأشجار المتوازنة ذاتيا، على سبيل المثال، شجرة إيه في إل أو شجرة B، ولكن ليس أشجار البحث الثنائية العادية). للحصول على دليل رياضي، راجع قسم إثبات الحدود.

تسمح الأشجار الحمراء والسوداء، مثل جميع أشجار البحث الثنائية، بالوصول المتسلسل الفعال (على سبيل المثال، التنقل بالترتيب، أي: بالترتيب من اليسار إلى الجذر إلى اليمين) لعناصرها. لكنها تدعم أيضًا الوصول المباشر الأمثل تقريبًا عبر الانتقال من الجذر إلى الورقة، مما يؤدي إلى O(\log n) وقت البحث.

## تشبيه بالأشجار 2-3-4
alt=A 2-node maps to a single black node. A 3-node maps to a black node with a red child. A 4-node maps to a black node with two red children.|تصغير|الشكل 1: أوجه التشابه بين الأشجار 2-3-4 والأشجار الحمراء والسوداء

تتشابه الأشجار الحمراء والسوداء في بنيتها مع الأشجار 2-3-4، وهي أشجار B من الرتبة 4. في الأشجار 2-3-4، يمكن أن تحتوي كل عقدة على ما بين 1 و3 قيم ويكون لديها ما بين 2 و4 أطفال. تتوافق هذه العقد 2-3-4 مع مجموعات العقد السوداء - الأطفال الحمراء في الأشجار الحمراء-السوداء، كما هو موضح في الشكل 1. إنها ليست مطابقة 1 إلى 1، لأن العقد الثلاث لها تمثيلان متكافئان: الطفل الأحمر قد يكون إما على اليسار أو اليمين. يجعل متغير الشجرة الأحمر والأسود المائل إلى اليسار هذه العلاقة 1 إلى 1 تمامًا، من خلال السماح بتمثيل الطفل الأيسر فقط. نظرًا لأن كل عقدة 2-3-4 لها عقدة سوداء مقابلة، فإن الثابت 4 للأشجار الحمراء والسوداء يعادل القول بأن أوراق شجرة 2-3-4 تقع جميعها على نفس المستوى.

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

## التطبيقات وهياكل البيانات ذات الصلة
توفر الأشجار الحمراء والسوداء أسوأ الضمانات لوقت الإدراج، ووقت الحذف، ووقت البحث. لا يجعلها هذا ذات قيمة في التطبيقات الحساسة للوقت مثل تطبيقات الوقت الفعلي فحسب، بل يجعلها أيضًا لبنات بناء قيمة في هياكل البيانات الأخرى التي توفر ضمانات أسوأ الحالات. على سبيل المثال، تعتمد العديد من هياكل البيانات المستخدمة في الهندسة الحسابية على الأشجار الحمراء والسوداء، ويستخدم  ونداء نظام إيبول لنواة لينكس أشجارًا حمراء وسوداء. شجرة إيه في إل هي بنية أخرى تدعم O(\log n) البحث والإدراج والإزالة. يمكن تلوين أشجار إيه في إل باللون الأحمر والأسود، وبالتالي فهي مجموعة فرعية من الأشجار ذات اللون الأحمر والأسود. يبلغ أسوأ ارتفاع لإيه في إل 0.720 مرة أسوأ ارتفاع للأشجار ذات اللون الأحمر والأسود، وبالتالي فإن أشجار إيه في إل متوازنة بشكل أكثر صلابة. توصلت قياسات أداء بن فاف مع حالات اختبار واقعية في 79 جولة إلى أن نسبة إيه في إل إلى RB تتراوح بين 0.677 و1.077، والمتوسط عند 0.947، والمتوسط الهندسي 0.910. يقع أداء  بين أشجار إيه في إل والأشجار ذات اللون الأحمر والأسود.

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

لكل ، هناك أشجار حمراء-سوداء مقابلة مع عناصر بيانات بنفس الترتيب. إن عمليات الإدراج والحذف في الأشجار 2-3-4 تعادل أيضًا عكس الألوان والدوران في الأشجار الحمراء والسوداء. هذا يجعل الأشجار 2-3-4 أداة مهمة لفهم المنطق وراء الأشجار الحمراء-السوداء، وهذا هو السبب في أن العديد من نصوص الخوارزمية التمهيدية تقدم أشجار 2-3-4 قبل الأشجار الحمراء-السوداء مباشرة، على الرغم من أن أشجار 2-3-4 لا تُستخدم غالبًا في الممارسة العملية.

في عام 2008، قدم سيدجويك نسخة أبسط من شجرة الأحمر والأسود تسمى  من خلال إزالة درجة غير محددة مسبقًا من الحرية في التنفيذ. يحتفظ LLRB بثبات إضافي مفاده أن جميع الروابط الحمراء يجب أن تميل إلى اليسار باستثناء أثناء عمليات الإدراج والحذف. يمكن جعل الأشجار الحمراء والسوداء متساوية القياس إلى ، أو 2-3-4 أشجار، لأي تسلسل من العمليات. تم وصف شجرة القياس المتساوي 2-3-4 في عام 1978 بواسطة سيدجويك. مع وجود 2-3-4 أشجار، يتم حل التماثل اللوني عن طريق «انعكاس اللون»، وهو ما يتوافق مع الانقسام، حيث يترك اللون الأحمر لعقدتين تابعتين العقدتين وينتقل إلى العقدة الأصلية.

الوصف الأصلي ، وهو نوع من الأشجار المُحسّنة للبحث السريع، يستخدم أشجارًا حمراء وسوداء على وجه التحديد كجزء من بنية بياناتها.

اعتبارًا من Java 8، تم تعديل هاش ماب بحيث يتم استخدام شجرة حمراء-سوداء بدلاً من استخدام القائمة المرتبطة لتخزين عناصر مختلفة ذات أكواد تجزئة متضاربة. ويؤدي هذا إلى تحسين التعقيد الزمني للبحث عن مثل هذا العنصر من O(m) ل O(\log m) أين m هو عدد العناصر ذات التجزئات المتصادمة.

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

هذا مثال لتطبيق الإدراج والإزالة في لغة C. فيما يلي هياكل البيانات ودالة المساعدة `rotate_subtree` المستخدمة في أمثلة الإدراج والإزالة.


```c
enum Color { BLACK, RED };
enum Dir { LEFT, RIGHT };

// red-black tree node
struct Node {
	struct Node *parent; // null for the root node
	union {
		// Union so we can use ->left/->right or ->child[0]/->child[1]
		struct {
			struct Node *left;
			struct Node *right;
		};
		struct Node *child[2]؛
	};
	enum Color color;
	int key;
};

struct Tree {
	struct Node *root;
};

#define DIRECTION(N) (N == N->parent->right ? RIGHT : LEFT)

struct Node *rotate_subtree(struct Tree *tree, struct Node *sub, enum Dir dir) {

	struct Node *sub_parent = sub->parent;
	struct Node *new_root = sub->child[1 - dir]؛ // 1 - dir is the opposite direction
	struct Node *new_child = new_root->child[dir]؛

	sub->child[1 - dir] = new_child;

	if (new_child) new_child->parent = sub;

	new_root->child[dir] = sub;

	new_root->parent = sub_parent;
	sub->parent = new_root;
	if (sub_parent)
		sub_parent->child[sub == sub_parent->right] = new_root;
	else
		tree->root = new_root;

	return new_root;
}
```


160px|تصغير|يسار|الدوران إلى اليسار و<br/>الدوران إلى اليمين، متحرك.

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

* خط أساسي يرمز إلى عقدة حمراء وخط أساسي|13x13بك عقدة سوداء (غير فارغة) (ارتفاعها أسود ≥ 1)،خط أساسي يرمز إلى اللون الأحمر أو الأسود لعقدة غير فارغة، ولكن نفس اللون في نفس الرسم البياني. لا يتم تمثيل العقد NULL في المخططات.
* يشير المتغير **N** إلى العقدة الحالية، والتي تم تسميتها ن أو ن في المخططات.
* يحتوي الرسم التخطيطي على ثلاثة أعمدة واثنين إلى أربعة إجراءات. يُظهر العمود الأيسر التكرار الأول، ويُظهر العمود الأيمن التكرارات الأعلى، ويُظهر العمود الأوسط تقسيم الحالة إلى أفعالها المختلفة.

# يعرض إجراء "الإدخال" مجموعة العقد مع ألوانها والتي تحدد حالة وتنتهك في الغالب بعض المتطلبات. يحيط إطار أزرق بالعقدة الحالية **N** ويتم تسمية العقد الأخرى وفقًا لعلاقتها بـ **N.**
# إذا تم اعتبار الدوران مفيدًا، فسيتم تصويره في الإجراء التالي، والذي يسمى "الدوران".
# إذا تم اعتبار بعض إعادة التلوين مفيدًا، فسيتم تصوير ذلك في الإجراء التالي، والذي يُسمى "اللون".
# إذا كانت هناك حاجة إلى الإصلاح، فإن الحالات تستخدم كود الحالات الأخرى وهذا بعد إعادة تعيين العقدة الحالية **N**، والتي تحمل بدورها حلقة زرقاء والتي قد يتعين إعادة تعيين العقد الأخرى إليها أيضًا. يُسمى هذا الإجراء "إعادة التعيين". بالنسبة لكلا العمليتين، الإدراج والحذف، هناك حالة واحدة (بالضبط) تكرر مستوى أسود واحدًا أقرب إلى الجذر؛ ثم تلبي الكوكبة المعاد تعيينها الثوابت الحلقية المقابلة.

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

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

; ملاحظة
: من أجل التبسيط، يستخدم الكود النموذجي الفصل :
:: `U == NULL || U->color == BLACK ''// considered black''`
: والعطف :
:: `U !` `= NULL && U->color == RED&nbsp;''// not considered black''`
: لذلك، يجب أن نضع في الاعتبار أن كلا البيانين *لا* يتم تقييمهما بشكل إجمالي، إذا كان `U == NULL`. ثم في كلتا الحالتين لا يتم المساس `U->color` (انظر  ). (التعليق `considered black` يتوافق مع المتطلب 2. )
: يجب أن تحدث عبارات `if` ذات الصلة بشكل أقل تكرارًا إذا تم تحقيق الاقتراح.

### الإدراج
تبدأ عملية الإدراج بوضع العقدة الجديدة (غير NULL)، على سبيل المثال **N**، في الموضع في شجرة البحث الثنائية لعقدة NULL التي يكون مفتاح سابقتها بالترتيب أقل من مفتاح العقدة الجديدة، والتي بدورها تكون أقل من مفتاح خليفتها بالترتيب. (في كثير من الأحيان، يكون هذا التموضع نتيجة لعملية بحث داخل الشجرة تسبق عملية الإدراج مباشرةً وتتكون من عقدة `P` مع اتجاه `dir` مع   يتم تلوين العقدة المدرجة حديثًا باللون الأحمر مؤقتًا حتى تحتوي جميع المسارات على نفس عدد العقد السوداء كما في السابق. ولكن إذا كان الوالد، على سبيل المثال **P**، أحمر أيضًا، فإن هذا الإجراء يؤدي إلى انتهاك اللون الأحمر.


```c
// parent is optional
void insert(struct Tree *tree, struct Node *node, struct Node *parent, enum Dir dir) {

	node->color = RED;
	node->parent = parent;

	if (!parent) {
		tree->root = node;
		return;
	}

	parent->child[dir] = node;

	// rebalance the tree 
	do {
		// Case #1
		if (parent->color == BLACK) return;

		struct Node *grandparent = parent->parent;

		if (!grandparent) {
			// Case #4
			parent->color = BLACK;
			return;
		}

		dir = DIRECTION(parent);
		struct Node *uncle = grandparent->child[1 - dir]؛
		if (!uncle || uncle->color == BLACK) {
			if (node == parent->child[1 - dir]) {
				// Case #5
				rotate_subtree(tree, parent, dir);
				node = parent;
				parent = grandparent->child[dir]؛
			}

			// Case #6
			rotate_subtree(tree, grandparent, 1 - dir);
			parent->color = BLACK;
			grandparent->color = RED;
			return;
		}

		// Case #2
		parent->color = BLACK;
		uncle->color = BLACK;
		grandparent->color = RED;
		node = grandparent;

	} while (parent = node->parent);

	// Case #3
	return;

}
```


تحتوي حلقة إعادة التوازن لعملية الإدراج على الثوابت التالية:

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

#### ملاحظات حول المخططات المدرجة

* في المخططات، يتم استخدام **P** لوالد **N**، **وG** لجدّه، و **U** لعمّه. في الجدول، يشير "—" إلى الجذر.
* تظهر المخططات العقدة الأصلية **P** باعتبارها الطفل الأيسر للعقدة الأصلية **G** على الرغم من أنه من الممكن أن تكون **P** على أي من الجانبين. يغطي كود العينة كلا الاحتمالين عن طريق المتغير الجانبي `dir`.
* تظهر المخططات الحالات التي يكون فيها **P** باللون الأحمر أيضًا، وهو انتهاك اللون الأحمر.
* يشير العمود *x* إلى التغيير في اتجاه الطفل، أي أن o (لـ "الخارجي") يعني أن **P** و **N** كلاهما طفلان أيسر أو كلاهما طفلان أيمن، بينما i (لـ "الداخلي") يعني أن اتجاه الطفل يتغير من **P** إلى **N.**
* مجموعة الأعمدة *السابقة* تحدد الحالة التي يتم إعطاء اسمها في *حالة* العمود. وبالتالي، سيتم تجاهل القيم المحتملة في الخلايا الفارغة. لذلك في الحالة **I2،** يغطي كود العينة كلا احتمالات الاتجاهات الفرعية لـ **N**، على الرغم من أن الرسم التخطيطي المقابل يظهر واحدًا فقط.
* تم ترتيب الصفوف في الملخص بحيث تكون تغطية جميع حالات RB المحتملة مفهومة بسهولة.
* يشير *دوران* العمود إلى ما إذا كان الدوران يساهم في إعادة التوازن.
* يُظهر *تعيين* العمود تعيين **N** قبل الدخول إلى خطوة لاحقة. من المحتمل أن يؤدي هذا إلى إعادة تعيين العقد الأخرى **P** و **G** و **U** أيضًا.
* إذا تم تغيير شيء ما بالحالة، فسيتم عرض ذلك في مجموعة الأعمدة *بعد*.
* أ13x13بك يشير تسجيل الدخول في العمود *التالي* إلى أن إعادة التوازن اكتملت بهذه الخطوة. إذا كان العمود *بعد* يحدد حالة واحدة فقط، فسيتم تقديم هذه الحالة باعتبارها الحالة اللاحقة، وإلا فسيتم وضع علامات استفهام.
* في الحالة **الثانية،** تتفاقم مشكلة إعادة التوازن \Delta h=2 مستويات الشجرة أو مستوى أسود واحد أعلى في الشجرة، بحيث يصبح الجد **G** هو العقدة الحالية الجديدة **N.** لذا يستغرق الأمر الحد الأقصى \tfrac{h}2 خطوات التكرار لإصلاح الشجرة (حيث **' هو ارتفاع الشجرة). نظرًا لأن احتمال التصعيد يتناقص بشكل كبير مع كل خطوة، فإن تكلفة إعادة التوازن الإجمالية تظل ثابتة في المتوسط، بل ثابتة عند الاستهلاك.
* تحدث الدورات في الحالات **I6** و **I5 + I6** – خارج الحلقة. لذلك، يحدث دورانان على الأكثر في المجموع.

==== أدخل الحالة 1 ====
العقدة الأصلية **P** للعقدة الحالية هي سوداء، لذا فإن المتطلب 3 صحيح. ينطبق المتطلب رقم 4 أيضًا وفقًا لثابت الحلقة.

==== أدخل الحالة 2 ====




إذا كان كل من الوالد **P** والعم **U** باللون الأحمر، فيمكن إعادة طلاء كليهما باللون الأسود ويصبح الجد **G** باللون الأحمر للحفاظ على المتطلب 4. نظرًا لأن أي مسار عبر الوالد أو العم يجب أن يمر عبر الجد، فإن عدد العقد السوداء على هذه المسارات لم يتغير. ومع ذلك، قد ينتهك الجد **G** الآن الشرط 3، إذا كان لديه أحد الوالدين باللون الأحمر. بعد إعادة تسمية **G** إلى **N**، يتم استيفاء ثابت الحلقة بحيث يمكن تكرار إعادة التوازن على مستوى أسود واحد (= مستويين للشجرة) أعلى.

==== أدخل الحالة 3 ====
تم تنفيذ الحالة 2 لإدراج <math>\tfrac{h-1}2</math> مرات وزاد الارتفاع الإجمالي للشجرة بمقدار 1، حيث أصبح الآن **' . العقدة الحالية **N** هي الجذر (الأحمر) للشجرة، وجميع خصائص RB مُرضية.

#### أدخل الحالة 4
الأصل **P** أحمر والجذر. نظرًا لأن **N** أيضًا أحمر، يتم انتهاك المتطلب 3. ولكن بعد تبديل لون **P** تصبح الشجرة على شكل RB. يزداد ارتفاع الشجرة السوداء بمقدار 1.

#### أدخل الحالة 5

الوالد **P** أحمر ولكن العم **U** أسود. الهدف النهائي هو تدوير العقدة الأصلية **P** إلى موضع الجد، ولكن هذا لن ينجح إذا كان **N** حفيدًا "داخليًا" لـ **G** (أي إذا كان **N** هو الطفل الأيسر للطفل الأيمن لـ **G** أو الطفل الأيمن للطفل الأيسر لـ **G** ). يؤدي  عند **P** إلى تبديل أدوار العقدة الحالية **N** وعقدتها الأم **P.** يضيف الدوران مسارات عبر **N** (تلك الموجودة في الشجرة الفرعية المسماة **2**، انظر الرسم التخطيطي) ويزيل المسارات عبر **P** (تلك الموجودة في الشجرة الفرعية المسماة **4** ). لكن كل من **P** و **N** أحمران، لذا يتم الحفاظ على المتطلب رقم 4. تم استعادة المتطلب 3 في الحالة 6.

#### أدخل الحالة 6
من المؤكد الآن أن العقدة الحالية **N** هي حفيدة "خارجية" لـ **G** (يسار الطفل الأيسر أو يمين الطفل الأيمن). الآن  عند **G**، ووضع **P** في مكان **G** وجعل **P** هو الأصل لـ **N** و **G.** **G** هو اللون الأسود وطفله السابق **P** هو اللون الأحمر، نظرًا لانتهاك المتطلب 3. بعد تبديل ألوان **P** و **G،** فإن الشجرة الناتجة تلبي المتطلب 3. يظل المتطلب رقم 4 مُلبى أيضًا، حيث أن جميع المسارات التي مرت عبر **G** الأسود تمر الآن عبر **P** الأسود.

نظرًا لأن الخوارزمية تقوم بتحويل المدخلات دون استخدام بنية بيانات مساعدة واستخدام كمية صغيرة فقط من مساحة التخزين الإضافية للمتغيرات المساعدة، فهي في مكانها.

### الإزالة

#### الحالات البسيطة

* عندما يكون للعقدة المحذوفة **طفلان** (غير فارغين)، فيمكننا تبديل قيمتها بخليفتها بالترتيب (الطفل الأيسر من الشجرة الفرعية اليمنى)، ثم حذف الخليفة بدلاً من ذلك. نظرًا لأن الخليفة هو أقصى اليسار، فلا يمكن أن يكون له سوى طفل أيمن (غير NULL) أو لا يمكن أن يكون له أي طفل على الإطلاق.
* عندما يكون للعقدة المحذوفة **طفل واحد فقط** (غير فارغ). في هذه الحالة، فقط استبدل العقدة بطفلها، وقم بتلوينها باللون الأسود.
** يجب أن يكون الطفل الفردي (غير NULL) باللون الأحمر وفقًا للاستنتاج 5، ويجب أن تكون العقدة المحذوفة باللون الأسود وفقًا للمتطلب 3.
* عندما **لا تحتوي العقدة المحذوفة على أطفال** (NULL) وتكون هي الجذر، استبدلها بـ NULL. الشجرة فارغة.
* عندما **لا تحتوي العقدة المحذوفة على أطفال** (كلاهما NULL)، وتكون **حمراء**، قم ببساطة بإزالة عقدة الورقة.
* عندما **لا تحتوي العقدة المحذوفة على أطفال** (كلاهما NULL)، وتكون **سوداء**، فإن حذفها سيؤدي إلى إنشاء اختلال في التوازن، ويتطلب إعادة التوازن، كما هو موضح في القسم التالي.

#### إزالة ورقة سوداء غير جذرية
الحالة المعقدة هي عندما لا يكون **N** هو الجذر، ملونًا باللون الأسود وليس له طفل مناسب (⇔ أطفال NULL فقط). في التكرار الأول، تم استبدال **N** بـ NULL.


```c
void remove(struct Tree *tree, struct Node *node) {
	struct Node *parent = node->parent;

	struct Node *sibling;
	struct Node *close_nephew;
	struct Node *distant_nephew;

	enum Dir dir = DIRECTION(node);

	parent->child[dir] = NULL;
	goto start_balance;

	do {
		dir = DIRECTION(node);
start_balance:
		sibling = parent->child[1 - dir]؛
		distant_nephew = sibling->child[1 - dir]؛
		close_nephew = sibling->child[dir]؛
		if (sibling->color == RED) {
			// Case #3
			rotate_subtree(tree, parent, dir);
			parent->color = RED;
			sibling->color = BLACK;
			sibling = close_nephew;

			distant_nephew = sibling->child[1 - dir]؛
			if (distant_nephew && distant_nephew->color == RED)
				goto case_6;
			close_nephew = sibling->child[dir]؛
			if (close_nephew && close_nephew->color == RED)
				goto case_5;

			// Case #4
			sibling->color = RED;
			parent->color = BLACK;
			return;
		}

		if (distant_nephew && distant_nephew->color == RED)
			goto case_6;

		if (close_nephew && close_nephew->color == RED)
			goto case_5;

		if (parent->color == RED) {
			// Case #4
			sibling->color = RED;
			parent->color = BLACK;
			return;
		}

		// Case #1
		if (!parent) return;

		// Case #2
		sibling->color = RED;
		node = parent;

	} while (parent = node->parent);

case_5:

	rotate_subtree(tree, sibling, 1 - dir);
	sibling->color = RED;
	close_nephew->color = BLACK;
	distant_nephew = sibling;
	sibling = close_nephew;

case_6:

	rotate_subtree(tree, parent, dir);
	sibling->color = parent->color;
	parent->color = BLACK;
	distant_nephew->color = BLACK;
	return;
}
```


تحتوي حلقة إعادة التوازن لعملية الحذف على الثابت التالي:

* في بداية كل تكرار، يكون ارتفاع اللون الأسود لـ **N** مساويًا لرقم التكرار ناقص واحد، مما يعني أنه في التكرار الأول يكون صفرًا وأن **N** هي عقدة سوداء حقيقية13x13بك في التكرارات الأعلى.
* عدد العقد السوداء على المسارات عبر **N** أقل بواحدة مما كان عليه قبل الحذف، في حين أنه لم يتغير في جميع المسارات الأخرى، بحيث يكون هناك انتهاك للون الأسود عند **P** إذا كانت هناك مسارات أخرى موجودة.
* يتم استيفاء جميع الخصائص الأخرى (بما في ذلك المتطلب 3 ) في جميع أنحاء الشجرة.

#### ملاحظات حول مخططات الحذف

#### حذف الحالة 1
العقدة الحالية **N** هي الجذر الجديد. تمت إزالة عقدة سوداء واحدة من كل مسار، لذلك يتم الحفاظ على خصائص RB. ينخفض ارتفاع الشجرة السوداء بمقدار 1.

#### حذف الحالة 2

أطفال **P** و **S** و **S** من السود. بعد طلاء **S** باللون الأحمر، فإن جميع المسارات التي تمر عبر **S**، والتي هي على وجه التحديد المسارات *التي لا* تمر عبر **N**، تحتوي على عقدة سوداء أقل. الآن تحتوي جميع المسارات في الشجرة الفرعية التي يتجذرها **P** على نفس عدد العقد السوداء، ولكن أقل بعقدة واحدة من المسارات التي لا تمر عبر **P**، لذلك لا يزال من الممكن انتهاك المتطلب 4. بعد إعادة تسمية **P** إلى **N**، يتم استيفاء ثابت الحلقة بحيث يمكن تكرار إعادة التوازن على مستوى أسود واحد (= مستوى شجرة واحد) أعلى.

#### حذف الحالة 3

الأخ **S** أحمر اللون، لذلك يجب على **P** وأبناء الأخ **C** و **D** أن يكونوا أسود اللون. يؤدي  عند **P** إلى تحويل **S** إلى جد **N.** ثم بعد عكس ألوان **P** و **S**، فإن المسار عبر **N** لا يزال قصيرًا بعقدة سوداء واحدة. لكن **N** لديه الآن أحد الوالدين الأحمر **P** وبعد إعادة التعيين لديه شقيق أسود **S**، وبالتالي فإن التحولات في الحالات 4 أو 5 أو 6 قادرة على استعادة شكل RB.

#### حذف الحالة 4

أطفال الأخوين **S** و **S** هم من السود، ولكن **P** هو أحمر. لا يؤثر تبادل ألوان **S** و **P** على عدد العقد السوداء على المسارات التي تمر عبر **S**، ولكنه يضيف واحدًا إلى عدد العقد السوداء على المسارات التي تمر عبر **N**، مما يعوض العقدة السوداء المحذوفة على تلك المسارات.

#### حذف الحالة 5

الأخ **S** أسود اللون، والطفل المقرب لـ **S** **C** أحمر اللون، والطفل البعيد لـ **S** **D** أسود اللون. بعد  في **S،** يصبح ابن الأخ **C** والد **S** وشقيق **N** الجديد. يتم تبادل ألوان **S** و **C.** لا تزال جميع المسارات تحتوي على نفس عدد العقد السوداء، ولكن الآن أصبح لدى **N** شقيق أسود يكون طفله البعيد أحمر، وبالتالي تكون الكوكبة مناسبة للحالة D6. لا يتأثر **N** ولا أصله **P** بهذا التحويل، وقد يكون **P** أحمر أو أسود (ملف:RedOrBlackNode.svg في الرسم التخطيطي).

#### حذف الحالة 6

الأخ **S** أسود اللون، **والطفل** البعيد **D** أحمر اللون. بعد  عند **P،** يصبح الأخ **S** هو والد الطفل البعيد **D** لـ **P** و **S.** يتم تبادل ألوان **P** و **S**، ويصبح **D** أسود. لا تزال الشجرة الفرعية بأكملها تحمل نفس اللون عند جذرها **S**، أي إما أحمر أو أسود (ملف:RedOrBlackNode.svg في الرسم التخطيطي، والذي يشير إلى نفس اللون قبل وبعد التحويل. بهذه الطريقة يتم الحفاظ على المتطلب رقم 3. إن المسارات الموجودة في الشجرة الفرعية التي لا تمر عبر **N** (أي تمر عبر **D** والعقدة **3** في الرسم التخطيطي) تمر عبر نفس عدد العقد السوداء كما في السابق، ولكن **N** لديه الآن سلف أسود إضافي: إما أن **P** أصبح أسود، أو كان أسودًا وتمت إضافة **S** كجد أسود. وبالتالي، تمر المسارات التي تمر عبر **N** عبر عقدة سوداء إضافية، بحيث يتم استعادة المتطلب 4 وتصبح الشجرة الإجمالية على شكل RB.

نظرًا لأن الخوارزمية تقوم بتحويل المدخلات دون استخدام بنية بيانات مساعدة واستخدام كمية صغيرة فقط من مساحة التخزين الإضافية للمتغيرات المساعدة، فهي في مكانها.

## إثبات الحدود
تصغير|320px|الشكل 2: أشجار حمراء-سوداء RB <sub>''h''</sub> بارتفاعات ''h'' =1،2،3،4،5،كل منها مع الحد الأدنى من الرقم 1،2،4،6 على التوالي. 10 من العقد.
ل h\in\N هناك شجرة حمراء سوداء عالية h مع
:
العقد ( \lfloor \, \rfloor هي دالة الأرضية ) ولا يوجد شجرة حمراء-سوداء بهذا الارتفاع مع عدد أقل من العقد - وبالتالي فهي **ضئيلة**. ارتفاعه الأسود هو \lceil h/2\rceil (مع الجذر الأسود) أو للفردية h (ثم مع الجذر الأحمر) أيضا (h-1)/2~.

;الدليل
لكي تحتوي شجرة حمراء-سوداء ذات ارتفاع معين على أقل عدد من العقد، يجب أن يكون لها مسار واحد فقط طويل يحتوي على أقصى عدد من العقد الحمراء، وذلك لتحقيق أقصى ارتفاع للشجرة مع أدنى ارتفاع للعقد السوداء. بالإضافة إلى هذا المسار، يجب أن تكون جميع العقد الأخرى سوداء. إذا أُزيلت عقدة من هذه الشجرة، فإنها إما تفقد ارتفاعها أو إحدى خصائص RB.

لكي تحتوي شجرة حمراء-سوداء ذات ارتفاع معين على عدد أدنى من العقد، يجب أن يكون لديها مسار واحد طويل مع أقصى عدد من العقد الحمراء، لتحقيق أقصى ارتفاع للشجرة مع أدنى ارتفاع للأسود. بالإضافة إلى هذا المسار، يجب أن تكون جميع العقد الأخرى باللون الأسود. إذا تمت إزالة عقدة من هذه الشجرة فإنها تفقد ارتفاعها أو بعض خصائص RB.

شجرة ارتفاع RB h=1 مع الجذر الأحمر هو الحد الأدنى. وهذا يتفق مع
: m_1 = 2^{\lfloor (1+1)/2\rfloor} \!+\!2^{\lfloor 1/2 \rfloor} \!\!-\!\!2 = 2^1\!+\!2^0\!\!-\!\!2 = 1~.

شجرة RB صغيرة (RB *h* في الشكل 2) بارتفاع h>1 يحتوي على جذر حيث أن شجرتيه الفرعيتين مختلفتين في الارتفاع. الشجرة الفرعية الأعلى هي أيضًا شجرة RB دنيا،  وتحتوي أيضًا على أطول مسار يحدد ارتفاعها  m_{h-1} العقد والارتفاع الأسود \lfloor(h\!\!-\!\!1)/2\rfloor =: s . الشجرة الفرعية الأخرى هي شجرة ثنائية مثالية ذات ارتفاع (أسود) s وجود 2^s\!\!-\!\!1=2^{\lfloor(h-1)/2\rfloor}\!\!-\!\!1 العقد السوداء - ولا يوجد عقدة حمراء. ثم عدد العقد عن طريق الاستقراء

رسم بياني للدالة m_h محدب  مع نقاط توقف عند (h=2k\;|\;m_{2k}=2 \cdot 2^k\!-\!2) أين k \in \N . تمت جدولة الوظيفة على النحو التالي m_h= A027383( *h* –1) لـ h\geq 1 

;; حل الدالة لـ h
عدم المساواة 9>8=2^3 يؤدي إلى 3 > 2^{3/2}، والتي بالنسبة للأعداد الفردية h يؤدي إلى
: m_h = 3 \cdot 2^{(h-1)/2}-2 = \bigl(3\cdot 2^{-3/2}\bigr) \cdot 2^{(h+2)/2}-2 > 2 \cdot 2^{h/2}-2.
لذا في كلتا الحالتين، الزوجية والفردية، h هو في الفاصل الزمني

مع n  كونه عدد العقد.

;الخاتمة
شجرة حمراء سوداء اللون n العقد (المفاتيح) لها ارتفاع شجرة h \in O(\log n) .

## عمليات المجموعة والعمليات المجمعة
بالإضافة إلى عمليات الإدراج والحذف والبحث لعنصر واحد، تم تعريف العديد من عمليات المجموعة على  الاتحاد والتقاطع وفرق المجموعة. ومن ثم يمكن تنفيذ عمليات سريعة *مجمعة* للإدراج أو الحذف استنادًا إلى هذه الوظائف المحددة. تعتمد عمليات المجموعة هذه على عمليتين مساعدتين، *التقسيم* *والانضمام*. بفضل العمليات الجديدة، يمكن أن يصبح تنفيذ الأشجار الحمراء والسوداء أكثر كفاءة وقابلية للتوازي بدرجة كبيرة. من أجل تحقيق تعقيدات الوقت، يتطلب هذا التنفيذ أن يُسمح للجذر بأن يكون أحمر أو أسود، وأن تخزن كل عقدة **ارتفاعها الأسود** الخاص بها.
* *الانضمام* : تعمل دالة *الانضمام* على شجرتين   مع مفتاح **'، حيث ، أي أن جميع المفاتيح  أصغر من **'، وجميع المفاتيح  أكبر من **'. تُرجع هذه الدالة شجرة تحتوي على جميع العناصر في   وكذلك **'.

: إذا كان للشجرتين نفس الارتفاع الأسود، *فإن جوين* يقوم ببساطة بإنشاء عقدة جديدة مع شجرة فرعية يسارية  وجذر **' وشجرة فرعية يمينية . إذا كان كل من  و  لهما جذر أسود، فاضبط **' ليكون أحمر. وإلا فسيتم تعيين **' باللون الأسود.
: إذا كانت ارتفاعات اللون الأسود غير متساوية، افترض أن ارتفاع اللون  أكبر من ارتفاع اللون  (الحالة الأخرى تكون متماثلة). ''ينضم'' العمود الفقري الأيمن لـ  حتى العقدة السوداء **'، والتي تكون متوازنة مع . في هذه المرحلة، تُنشأ عقدة جديدة مع الابن الأيسر **'، والجذر **' (مُعَيَّن ليكون أحمر)، والابن الأيمن  لتحل محل c. قد تُبطل العقدة الجديدة ثابت الأحمر-الأسود، إذ لا يمكن ظهور أكثر من ثلاث عقد حمراء في صف واحد. يمكن إصلاح ذلك من خلال الدوران المزدوج. إذا انتشرت المشكلة الحمراء المزدوجة إلى الجذر، فسيتم بعد ذلك تعيين الجذر ليكون أسود، واستعادة الخصائص. تكلفة هذه الوظيفة هي الفرق بين ارتفاعات اللون الأسود بين شجرتي الإدخال.
: إذا كان للشجرتين نفس الارتفاع الأسود، *فإن جوين* يقوم ببساطة بإنشاء عقدة جديدة مع شجرة فرعية يسارية  وجذر **' وشجرة فرعية يمينية . إذا كان كل من  و  لهما جذر أسود، فاضبط **' ليكون أحمر. وإلا فسيتم تعيين **' باللون الأسود.
: إذا كانت ارتفاعات اللون الأسود غير متساوية، افترض أن ارتفاع اللون  أكبر من ارتفاع اللون  (الحالة الأخرى تكون متماثلة). ''ينضم'' العمود الفقري الأيمن لـ  حتى العقدة السوداء **'، والتي تكون متوازنة مع . في هذه المرحلة، تُنشأ عقدة جديدة مع الابن الأيسر **'، والجذر **' (مُعَيَّن ليكون أحمر)، والابن الأيمن  لتحل محل c. قد تُبطل العقدة الجديدة ثابت الأحمر-الأسود، إذ لا يمكن ظهور أكثر من ثلاث عقد حمراء في صف واحد. يمكن إصلاح ذلك من خلال الدوران المزدوج. إذا انتشرت المشكلة الحمراء المزدوجة إلى الجذر، فسيتم بعد ذلك تعيين الجذر ليكون أسود، واستعادة الخصائص. تكلفة هذه الوظيفة هي الفرق بين ارتفاعات اللون الأسود بين شجرتي الإدخال.
: *تقسيم* : لتقسيم شجرة حمراء-سوداء إلى شجرتين أصغر، تلك الأصغر من المفتاح **'، وتلك الأكبر من المفتاح **'، ارسم أولاً مسارًا من الجذر عن طريق إدخال **' في الشجرة الحمراء-السوداء. بعد هذا الإدراج، سيتم العثور على جميع القيم الأقل من **' على يسار المسار، وسيتم العثور على جميع القيم الأكبر من **' على اليمين. من خلال تطبيق ''جوين''، يتم دمج جميع الأشجار الفرعية على الجانب الأيسر من الأسفل إلى الأعلى باستخدام المفاتيح الموجودة على المسار كعقد وسيطة من الأسفل إلى الأعلى لتشكيل الشجرة اليسرى، والجزء الأيمن متماثل.
: بالنسبة لبعض التطبيقات، تقوم ''Split'' أيضًا بإرجاع قيمة منطقية تشير إلى ما إذا كان **' يظهر في الشجرة. تكلفة *الانقسام* هي O(\log n) , ترتيب ارتفاع الشجرة. في الواقع، لا علاقة لهذه الخوارزمية بأي خصائص خاصة لشجرة حمراء-سوداء، ويمكن استخدامها على أي شجرة باستخدام عملية *ربط*، مثل شجرة إيه في إل.

خوارزمية الانضمام هي كما يلي:
 **function** joinRightRB(TL, k, TR):
     **if** (TL.color=black) and (TL.blackHeight=TR.blackHeight):
         **return** Node(TL,⟨k,red⟩,TR)
     T'=Node(TL.left,⟨TL.key,TL.color⟩,joinRightRB(TL.right,k,TR))
     **if** (TL.color=black) and (T'.right.color=T'.right.right.color=red):
         T'.right.right.color=black;
         **return** rotateLeft(T')
     **return** T' /* T[recte T'] */
 
 **function** joinLeftRB(TL, k, TR):
   /* symmetric to joinRightRB */
 
 **function** join(TL, k, TR):
     **if** TL.blackHeight>TR.blackHeight:
         T'=joinRightRB(TL,k,TR)
         **if** (T'.color=red) and (T'.right.color=red):
             T'.color=black
         **return** T'
     **if** TR.blackHeight>TL.blackHeight:
         /* symmetric */
     **if** (TL.color=black) and (TR.color=black):
         **return** Node(TL,⟨k,red⟩,TR)
     **return** Node(TL,⟨k,black⟩,TR)
خوارزمية التقسيم هي كما يلي:
 **function** split(T, k):
     **if** (T = NULL) **return** (NULL, false, NULL)
     **if** (k = T.key) **return** (T.left, true, T.right)
     **if** (k 1, t2):
     **if** t1 = NULL **return** t2
     **if** t2 = NULL **return** t1
     (L1,b,R1)=split(t1,t2.key)
     proc1=**start**:
         TL=union(L1,t2.left)
     proc2=**start**:
         TR=union(R1,t2.right)
     **wait all** proc1,proc2
     **return** join(TL, t2.key, TR)

هنا، من المفترض أن يقوم *الانقسام* بإرجاع شجرتين: واحدة تحتوي على المفاتيح أقل من مفتاح الإدخال الخاص بها، والأخرى تحتوي على المفاتيح الأكبر. (الخوارزمية ، ولكن هناك أيضًا نسخة مدمرة في مكانها.)

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

تعقيد كل من الاتحاد والتقاطع والاختلاف هو O\left(m \log \left({n\over m}+1\right)\right) لشجرتين حمراء وسوداء بأحجام m و n(\ge m). يعد هذا التعقيد مثاليًا من حيث عدد المقارنات. الأمر الأكثر أهمية هو أنه نظرًا لأن المكالمات المتكررة إلى الاتحاد أو التقاطع أو الاختلاف مستقلة عن بعضها البعض، فيمكن تنفيذها بالتوازي مع  O(\log m \log n). متى m=1، يتضمن التنفيذ القائم على الانضمام نفس الرسم البياني غير الدوري الموجه حسابيًا (DAG) مثل الإدراج والحذف لعنصر واحد إذا تم استخدام جذر الشجرة الأكبر لتقسيم الشجرة الأصغر.

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

تُعد  للأشجار الحمراء والسوداء متوازية للعمليات الشاملة، بما في ذلك الاتحاد، والتقاطع، والإنشاء، والتصفية، والاختزال بالخريطة، وما إلى ذلك.

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

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

#### الانضمام القائم
يمكن تطبيق هذا النهج على كل بنية بيانات تسلسلية مرتبة تدعم عمليات الانضمام والتقسيم الفعالة. الفكرة العامة هي تقسيم **' و **' إلى أجزاء متعددة وإجراء الإدخالات على هذه الأجزاء بالتوازي.

# أولاً يجب فرز **' الأكبر من العناصر المراد إدراجها.
# بعد ذلك، تقوم الخوارزمية بتقسيم **' إلى k \in \mathbb{N}^+ أجزاء \langle I_1, \cdots, I_k \rangle بأحجام متساوية تقريبًا.
# بعد ذلك يجب تقسيم الشجرة **' إلى **' أجزاء \langle T_1, \cdots, T_k \rangle بطريقة ما، بحيث يكون لكل j \in \mathbb{N}^+ | \, 1 \leq j  تنطبق القيود التالية:
## \text{last}(I_j) 
## \text{last}(T_j) 
# الآن تقوم الخوارزمية بإدراج كل عنصر من I_j داخل T_j بالتتابع. يجب تنفيذ هذه الخطوة لكل **'، ويمكن القيام بذلك بواسطة ما يصل إلى **' معالج بالتوازي.
# وأخيرًا، سيتم ضم الأشجار الناتجة لتشكيل النتيجة النهائية للعملية بأكملها.

لاحظ أنه في الخطوة 3، القيود المفروضة على التقسيم أؤكد أنه في الخطوة 5، يمكن ضم الأشجار مرة أخرى وفرز التسلسل الناتج.

BulkInsert JoinBased InitialTree.svg|initial tree
BulkInsert JoinBased SplitTree.svg|split I and T
BulkInsert JoinBased SplitTreeInserted.svg|أدخل في الانقسام T
BulkInsert JoinBased JoinedTree.svg|انضم إلى T


يُظهر الكود الزائف تنفيذًا بسيطًا لتقسيم وغزو لخوارزمية تعتمد على الانضمام للإدراج بالجملة. يمكن تنفيذ كلا النداءين المتكررين بالتوازي. تختلف عملية الانضمام المستخدمة هنا عن الإصدار الموضح في هذه المقالة، حيث يتم استخدام join2 بدلاً من ذلك، والذي يفتقد المعلمة الثانية k.

 **bulkInsert**(T, I, k):
     I.sort()
     bulklInsertRec(T, I, k)
 
 **bulkInsertRec**(T, I, k):
     **if** k = 1:
         **forall** e **in** I: T.insert(e)
     **else**
         m := ⌊size(I) / 2⌋
         (T1, _, T2) := split(T, I[m])
         bulkInsertRec(T1, I[0.. m], ⌈k / 2⌉)
             || bulkInsertRec(T2, I[m + 1.. size(I) - 1], ⌊k / 2⌋)
         T ← join2(T1, T2)

##### وقت التنفيذ
لم يتم أخذ الفرز **' في الاعتبار في هذا التحليل.
:
يمكن تحسين ذلك باستخدام خوارزميات متوازية للتقسيم والانضمام. في هذه الحالة يكون وقت التنفيذ هو <math>\in O\left(\log |T| + \frac{k} \log |T|\right)</math>.

===== العمل =====
:

==== خطوط الأنابيب ====
هناك طريقة أخرى لتنفيذ العمليات المجمعة بالتوازي وهي استخدام نهج [[توارد (حوسبة)|الأنابيب]]. يمكن القيام بذلك عن طريق تقسيم مهمة معالجة عملية أساسية إلى سلسلة من المهام الفرعية. بالنسبة للعمليات الأساسية المتعددة، يمكن معالجة المهام الفرعية بالتوازي عن طريق تعيين كل مهمة فرعية إلى معالج منفصل.

# أولاً يجب فرز الجزء الأكبر من العناصر المراد إدراجها.
# لكل عنصر في ، تحدد الخوارزمية موضع الإدراج المقابل في . يمكن إجراء ذلك بالتوازي لكل عنصر <math>\in I</math> لأن  لن يتعرض للطفرات في هذه العملية. الآن، يجب تقسيم  إلى متتاليات فرعية  وفقًا لموضع إدراج كل عنصر. على سبيل المثال، <math>s_{n, \mathit{left}}</math> هي المتتالية الفرعية لـ التي تحتوي على العناصر التي يكون موضع إدراجها على يسار العقدة .
# سيتم إدراج العنصر الأوسط <math>m_{n, \mathit{dir}}</math> من كل متتالية فرعية <math>s_{n, \mathit{dir}}</math> في  كعقدة جديدة <math>n'</math>. يمكن إجراء ذلك بالتوازي لكل <math>m_{n, \mathit{dir}}</math> حيث أن موضع إدراج كل <math>m_{n, \mathit{dir}}</math> فريد، بحكم التعريف. إذا احتوى <math>s_{n, \mathit{dir}}</math> على عناصر على يسار أو يمين <math>m_{n, \mathit{dir}}</math>، فسيتم تضمينها في مجموعة جديدة من المتتاليات الفرعية S مثل <math>s_{n', \mathit{left}}</math> أو <math>s_{n', \mathit{right}}</math>.
# من المحتمل أن تحتوي  على عقدتين حمراوين متتاليتين في نهاية المسارات من الجذر إلى الأوراق، والتي تحتاج إلى إصلاح. لاحظ أنه أثناء الإصلاح <math>\in S</math> يجب تحديث موضع إدراج العناصر 𝑆، إذا تأثرت العقد المقابلة بالدوران.
#* إذا كان لعقدتين أسلاف سوداء أقرب مختلفة، فيمكن إصلاحهما بالتوازي. وبما أنه لا يمكن أن يكون لأربع عقد على الأكثر نفس السلف الأسود الأقرب، فيمكن إصلاح العقد في المستوى الأدنى بعدد ثابت من الخطوات المتوازية.
#* سيتم تطبيق هذه الخطوة بالتتابع على مستويات السواد أعلاه حتى يتم إصلاح  بالكامل.
# تُكرر الخطوات من 3 إلى 5 على المتتاليات الجزئية الجديدة حتى تصبح  فارغة. عند هذه النقطة، يكون كل عنصر <math>\in I</math> قد أُضيف. يُسمى كل تطبيق لهذه الخطوات مرحلة. بما أن طول المتتاليات الجزئية في  هو <math>\in O(|I|)</math> وفي كل مرحلة تُقسّم المتتاليات الجزئية إلى النصف، فإن عدد المراحل هو <math>\in O(\log |I|)</math>.
#* بما أن جميع المراحل تتحرك صعودًا عبر مستويات الظلام في الشجرة، فيمكن ربطها بالتوازي في خط أنابيب. بمجرد انتهاء كل مرحلة من معالجة مستوى أسود واحد، تتمكن المرحلة التالية من التحرك صعودًا والاستمرار على هذا المستوى.
<gallery perrow="3" widths="250px" heights="180px">
BulkInsert Pipelining InitialTree.svg|Initial tree
BulkInsert Pipelining InsertPositions.svg|Find insert positions
BulkInsert Pipelining Stage1Insert.svg|Stage 1 inserts elements
BulkInsert Pipelining Stage1Repair.svg|Stage 1 begins to repair nodes
BulkInsert Pipelining Stage2Insert.svg|Stage 2 inserts elements
BulkInsert Pipelining Stage2Repair.svg|Stage 2 begins to repair nodes
BulkInsert Pipelining Stage3Insert.svg|Stage 3 inserts elements
BulkInsert Pipelining Stage3Repair1.svg|Stage 3 begins to repair nodes
BulkInsert Pipelining Stage3Repair2.svg|Stage 3 continues to repair nodes
</gallery>

===== وقت التنفيذ =====
لم يتم أخذ الفرز **' في الاعتبار في هذا التحليل. أيضًا، |I| من المفترض أن يكون أصغر من |T| وإلا فسيكون من الأكثر كفاءة إنشاء الشجرة الناتجة من الصفر.
:

##### العمل
:

## انظر أيضًا
* شجرة (هياكل بيانات)
* شجرة أدلسن فالسكي ولانديس
* شجرة بي (, , شجرة بي بلس، شجرة بي, )

## المراجع والملاحظات

## للقراءة الإضافية
* Mathworld: Red–Black Tree
* San Diego State University: CS 660: Red–Black tree notes, by Roger Whitney
*  

## وصلات خارجية
* Ben Pfaff: *An Introduction to Binary Search Trees and Balanced Trees.* Free Software Foundation, Boston 2004, ftp.gnu.org (PDF gzip; 1662&nbsp;kB)
* [A complete and working implementation in C](https://web.archive.org/web/20140328232325/http://en.literateprograms.org/Red-black_tree_(C))
* OCW MIT Lecture on Red-black Trees by Erik Demaine
*  – Visualization of random and pre-sorted data insertions, in elementary binary search trees, and left-leaning red–black trees
* An intrusive red–black tree written in C++
* Red–black BSTs in 3.3 Balanced Search Trees
* Red–black BST Demo

تصنيف:أشجار اثنانية
تصنيف:علم الحاسوب في 1972
تصنيف:مقالات تحوي براهين