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

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

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

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

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

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

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

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

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

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

يتم تعريف العمق الأسود للعقدة على أنه عدد العقد السوداء من الجذر إلى تلك العقدة (أي عدد الأسلاف السود). الارتفاع الأسود لشجرة حمراء-سوداء هو عدد العقد السوداء في أي مسار من الجذر إلى الأوراق، والذي، وفقًا للمتطلب 4، يكون ثابتًا (بدلاً من ذلك، يمكن تعريفه على أنه العمق الأسود لأي عقدة ورقة).^{[17]:154–165} الارتفاع الأسود للعقدة هو الارتفاع الأسود للشجرة الفرعية التي تتبعها. في هذه المقالة، يجب تعيين الارتفاع الأسود للعقدة الفارغة إلى 0، لأن شجرتها الفرعية فارغة كما يقترح الشكل التوضيحي، وارتفاع شجرتها هو 0 أيضًا.

بالإضافة إلى المتطلبات المفروضة على شجرة البحث الثنائية، يجب استيفاء المتطلبات التالية بواسطة شجرة حمراء وسوداء:^[18]

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

يزعم بعض المؤلفين، مثل كورمن وآخرون،^[18] أن "الجذر أسود" كمتطلب خامس؛ ولكن ليس ميلهورن وساندرز^[17] أو سيدجويك وواين.^{[16]:432–447} نظرًا لأنه يمكن دائمًا تغيير الجذر من الأحمر إلى الأسود، فإن هذه القاعدة لها تأثير ضئيل على التحليل. تغفل هذه المقالة أيضًا هذه النقطة، لأنها تزعج الخوارزميات التكرارية والإثباتات قليلاً.

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

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

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

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

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

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

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

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

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

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

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

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

لا تتطلب العمليات للقراءة فقط، مثل البحث أو عبور الشجرة، على شجرة حمراء سوداء أي تعديل عن تلك المستخدمة لأشجار البحث الثنائية، لأن كل شجرة حمراء سوداء هي حالة خاصة من شجرة بحث ثنائية بسيطة. ومع ذلك، فإن النتيجة المباشرة للإدراج أو الإزالة قد تنتهك خصائص الشجرة الحمراء والسوداء، والتي تسمى عملية استعادتها بإعادة التوازن بحيث تصبح الأشجار الحمراء والسوداء متوازنة ذاتيا. إن إعادة التوازن (أي تغييرات اللون) لها أسوأ تعقيد زمني ${\displaystyle O(\log n)}$ ومتوسط ${\displaystyle O(1)}$،^{[28]:310[17]:158} على الرغم من أن هذه سريعة جدًا في الممارسة العملية. بالإضافة إلى ذلك، لا تستغرق عملية إعادة التوازن أكثر من ثلاث دورات للشجرة^[29] (اثنتان للإدراج).

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

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;
}

الإدراج

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

// 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 ) في جميع أنحاء الشجرة.

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

قبل

الحالة

rotation

assign­ment

بعد

التالي

Δh

P

G

U

x

P

G

U

x

I1

I2

N:=G

؟

؟

2

—

I3

—

I4

i

I5

P↶N

N:=P

o

I6

0

o

I6

P↷G

Insertion This synopsis shows in its before columns, that all possible cases[32] of constellations are covered.

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

أدخل الحالة 1

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

أدخل الحالة 2

first iteration

تكرار أعلى

Insert Case 2

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

أدخل الحالة 3

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

أدخل الحالة 4

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

أدخل الحالة 5

first iteration

تكرار أعلى

Insert Case 5

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

first iteration

تكرار أعلى

أدخل الحالة 6

أدخل الحالة 6

من المؤكد الآن أن العقدة الحالية N هي حفيدة "خارجية" لـ G (يسار الطفل الأيسر أو يمين الطفل الأيمن). الآن (1-dir)-rotate عند 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.

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 هي عقدة سوداء حقيقية في التكرارات الأعلى.
• عدد العقد السوداء على المسارات عبر N أقل بواحدة مما كان عليه قبل الحذف، في حين أنه لم يتغير في جميع المسارات الأخرى، بحيث يكون هناك انتهاك للون الأسود عند P إذا كانت هناك مسارات أخرى موجودة.
• يتم استيفاء جميع الخصائص الأخرى (بما في ذلك المتطلب 3 ) في جميع أنحاء الشجرة.

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

حذف الحالة 1

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

حذف الحالة 2

→ Explanation of symbols

first iteration

تكرار أعلى

Delete case D2

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

حذف الحالة 3

first iteration

تكرار أعلى

Delete case D3

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

حذف الحالة 4

first iteration

تكرار أعلى

Delete case D4

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

حذف الحالة 5

first iteration

تكرار أعلى

Delete case D5

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

حذف الحالة 6

first iteration

تكرار أعلى

Delete case D6

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

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

ل ${\displaystyle h\in \mathbb {N} }$ هناك شجرة حمراء سوداء عالية ${\displaystyle h}$ مع

${\displaystyle m_{h}}$	${\displaystyle =2^{\lfloor (h+1)/2\rfloor }+2^{\lfloor h/2\rfloor }-2}$
	${\displaystyle ={\Biggl \{}}$	${\displaystyle 2\cdot 2^{\tfrac {h}{2}}-2=2^{{\tfrac {h}{2}}+1}-2}$		if ${\displaystyle h}$ even
	${\displaystyle 3\cdot 2^{\tfrac {h-1}{2}}-2}$		if ${\displaystyle h}$ odd

العقد ( ${\displaystyle \lfloor \,\rfloor }$ هي دالة الأرضية ) ولا يوجد شجرة حمراء-سوداء بهذا الارتفاع مع عدد أقل من العقد - وبالتالي فهي ضئيلة. ارتفاعه الأسود هو ${\displaystyle \lceil h/2\rceil }$ (مع الجذر الأسود) أو للفردية ${\displaystyle h}$ (ثم مع الجذر الأحمر) أيضا ${\displaystyle (h-1)/2~.}$

الدليل

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

لكي تحتوي شجرة حمراء-سوداء ذات ارتفاع معين على عدد أدنى من العقد، يجب أن يكون لديها مسار واحد طويل مع أقصى عدد من العقد الحمراء، لتحقيق أقصى ارتفاع للشجرة مع أدنى ارتفاع للأسود. بالإضافة إلى هذا المسار، يجب أن تكون جميع العقد الأخرى باللون الأسود.^{[16]:444 Proof sketch} إذا تمت إزالة عقدة من هذه الشجرة فإنها تفقد ارتفاعها أو بعض خصائص RB.

شجرة ارتفاع RB ${\displaystyle h=1}$ مع الجذر الأحمر هو الحد الأدنى. وهذا يتفق مع

${\displaystyle m_{1}=2^{\lfloor (1+1)/2\rfloor }\!+\!2^{\lfloor 1/2\rfloor }\!\!-\!\!2=2^{1}\!+\!2^{0}\!\!-\!\!2=1~.}$

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

	${\displaystyle m_{h}}$	${\displaystyle =}$	${\displaystyle (m_{h-1})}$	${\displaystyle +}$	${\displaystyle (1)}$	${\displaystyle +}$	${\displaystyle (2^{\lfloor (h-1)/2\rfloor }-1)}$
			(شجرة فرعية أعلى)		(جذر)		(الشجرة الفرعية الثانية)
مما أدى إلى
	${\displaystyle m_{h}}$	${\displaystyle =}$	${\displaystyle (2^{\lfloor h/2\rfloor }+2^{\lfloor (h-1)/2\rfloor }-2)}$	${\displaystyle +}$	${\displaystyle 2^{\lfloor (h-1)/2\rfloor }}$
		${\displaystyle =}$	${\displaystyle 2^{\lfloor h/2\rfloor }+2^{\lfloor (h+1)/2\rfloor }-2}$  ■

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

حل الدالة لـ ${\displaystyle h}$

عدم المساواة ${\displaystyle 9>8=2^{3}}$ يؤدي إلى ${\displaystyle 3>2^{3/2}}$، والتي بالنسبة للأعداد الفردية ${\displaystyle h}$ يؤدي إلى

${\displaystyle 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}$.

لذا في كلتا الحالتين، الزوجية والفردية، ${\displaystyle h}$ هو في الفاصل الزمني

	${\displaystyle \log _{2}(n+1)}$	${\displaystyle \leq h\leq }$	${\displaystyle 2\log _{2}(n+2)-2=2\log _{2}(n/2+1)}$	${\displaystyle {\bigl [}<2\log _{2}(n+1)\;{\bigr ]}}$
	(شجرة ثنائية مثالية)		(شجرة صغيرة حمراء-سوداء)

مع ${\displaystyle n}$ كونه عدد العقد.^[33]

الخاتمة

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

بالإضافة إلى عمليات الإدراج والحذف والبحث لعنصر واحد، تم تعريف العديد من عمليات المجموعة على red–black trees: الاتحاد والتقاطع وفرق المجموعة. ومن ثم يمكن تنفيذ عمليات سريعة مجمعة للإدراج أو الحذف استنادًا إلى هذه الوظائف المحددة. تعتمد عمليات المجموعة هذه على عمليتين مساعدتين، التقسيم والانضمام. بفضل العمليات الجديدة، يمكن أن يصبح تنفيذ الأشجار الحمراء والسوداء أكثر كفاءة وقابلية للتوازي بدرجة كبيرة.^[34] من أجل تحقيق تعقيدات الوقت، يتطلب هذا التنفيذ أن يُسمح للجذر بأن يكون أحمر أو أسود، وأن تخزن كل عقدة ارتفاعها الأسود الخاص بها.

• الانضمام : تعمل دالة الانضمام على شجرتين t₁ t₂ مع مفتاح k، حيث t₁ < k < t₂، أي أن جميع المفاتيح t₁ أصغر من k، وجميع المفاتيح t₂ أكبر من k. تُرجع هذه الدالة شجرة تحتوي على جميع العناصر في t₁ t₂ وكذلك k.

إذا كان للشجرتين نفس الارتفاع الأسود، فإن جوين يقوم ببساطة بإنشاء عقدة جديدة مع شجرة فرعية يسارية t₁ وجذر k وشجرة فرعية يمينية t₂. إذا كان كل من t₁ و t₂ لهما جذر أسود، فاضبط k ليكون أحمر. وإلا فسيتم تعيين k باللون الأسود.

إذا كانت ارتفاعات اللون الأسود غير متساوية، افترض أن ارتفاع اللون t₁ أكبر من ارتفاع اللون t₂ (الحالة الأخرى تكون متماثلة). ينضم العمود الفقري الأيمن لـ t₁ حتى العقدة السوداء c، والتي تكون متوازنة مع t₂. في هذه المرحلة، تُنشأ عقدة جديدة مع الابن الأيسر c، والجذر k (مُعَيَّن ليكون أحمر)، والابن الأيمن t₂ لتحل محل c. قد تُبطل العقدة الجديدة ثابت الأحمر-الأسود، إذ لا يمكن ظهور أكثر من ثلاث عقد حمراء في صف واحد. يمكن إصلاح ذلك من خلال الدوران المزدوج. إذا انتشرت المشكلة الحمراء المزدوجة إلى الجذر، فسيتم بعد ذلك تعيين الجذر ليكون أسود، واستعادة الخصائص. تكلفة هذه الوظيفة هي الفرق بين ارتفاعات اللون الأسود بين شجرتي الإدخال.

إذا كان للشجرتين نفس الارتفاع الأسود، فإن جوين يقوم ببساطة بإنشاء عقدة جديدة مع شجرة فرعية يسارية t₁ وجذر k وشجرة فرعية يمينية t₂. إذا كان كل من t₁ و t₂ لهما جذر أسود، فاضبط k ليكون أحمر. وإلا فسيتم تعيين k باللون الأسود.

إذا كانت ارتفاعات اللون الأسود غير متساوية، افترض أن ارتفاع اللون t₁ أكبر من ارتفاع اللون t₂ (الحالة الأخرى تكون متماثلة). ينضم العمود الفقري الأيمن لـ t₁ حتى العقدة السوداء c، والتي تكون متوازنة مع t₂. في هذه المرحلة، تُنشأ عقدة جديدة مع الابن الأيسر c، والجذر k (مُعَيَّن ليكون أحمر)، والابن الأيمن t₂ لتحل محل c. قد تُبطل العقدة الجديدة ثابت الأحمر-الأسود، إذ لا يمكن ظهور أكثر من ثلاث عقد حمراء في صف واحد. يمكن إصلاح ذلك من خلال الدوران المزدوج. إذا انتشرت المشكلة الحمراء المزدوجة إلى الجذر، فسيتم بعد ذلك تعيين الجذر ليكون أسود، واستعادة الخصائص. تكلفة هذه الوظيفة هي الفرق بين ارتفاعات اللون الأسود بين شجرتي الإدخال.

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

بالنسبة لبعض التطبيقات، تقوم Split أيضًا بإرجاع قيمة منطقية تشير إلى ما إذا كان x يظهر في الشجرة. تكلفة الانقسام هي ${\displaystyle 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 < T.key):
        (L',b,R') = split(T.left, k)
        return (L',b,join(R',T.key,T.right))
    (L',b,R') = split(T.right, k)
    return (join(T.left,T.key,L'),b,T.right)

اتحاد شجرتين حمراوين t₁ و t₂ تمثلان المجموعتين A و B، هو شجرة حمراوين t تمثل A ∪ B تحسب الدالة التكرارية التالية هذا الاتحاد:

function union(t1, 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 يستدعي جوين ولكنه لا يتعامل مع معايير موازنة الأشجار الحمراء والسوداء بشكل مباشر، فإن مثل هذا التنفيذ يُطلق عليه عادةً اسم خوارزميات الشجرة القائمة على الانضمام ‏.

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

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

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

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)

• شجرة (هياكل بيانات)
• شجرة أدلسن فالسكي ولانديس
• شجرة بي (شجرة 2–3, شجرة 2–3–4, شجرة بي بلس، شجرة بي, شجرة يو بي)

• Mathworld: Red–Black Tree
• San Diego State University: CS 660: Red–Black tree notes, by Roger Whitney
• Pfaff، Ben (يونيو 2004). "Performance Analysis of BSTs in System Software" (PDF). جامعة ستانفورد. مؤرشف من الأصل (PDF) في 2017-08-09.

• Ben Pfaff: An Introduction to Binary Search Trees and Balanced Trees. Free Software Foundation, Boston 2004, ftp.gnu.org (PDF gzip; 1662 kB)
• A complete and working implementation in C
• OCW MIT Lecture on Red-black Trees by Erik Demaine
• Binary Search Tree Insertion Visualization على يوتيوب – 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