شجرة حمراء وسوداء
المحتويات
- ل هناك شجرة حمراء سوداء عالية مع
- حل الدالة لـ
- return T' /* T[recte T'] */
- union {
- node = parent;
- Mathworld: Red–Black Tree
- التطبيقات وهياكل البيانات ذات الصلة
- ملاحظات حول المخططات المدرجة
- if t2 = NULL return t1
- أدخل الحالة 2
- /* symmetric to joinRightRB */
- أدخل الحالة 3
- أدخل الحالة 1
- I.sort
- حذف الحالة 5
- أدخل الحالة 4
- حذف الحالة 2
- إزالة ورقة سوداء غير جذرية
- الخوارزميات المتوازية
- goto case_6;
- شجرة أدلسن فالسكي ولانديس
- } while (parent = node->parent);
- الحالات البسيطة
- وقت التنفيذ
- أدخل الحالة 6
- حذف الحالة 6
- A complete and working implementation in C
- الانضمام القائم
- ملاحظات حول الكود النموذجي ومخططات الإدراج والإزالة
- struct Node {
- عمليات الجملة المتوازية
- // parent is optional
- التنفيذ
- خطوط الأنابيب
- goto case_6;
- sibling = close_nephew;
- المصطلحات
- T'.right.right.color=black;
- الخاتمة
- ملاحظة
- sub->parent = new_root;
- m := ⌊size(I) / 2⌋
- }
- التاريخ
- تشبيه بالأشجار 2-3-4
- وقت التنفيذ
- حذف الحالة 1
- dir = DIRECTION(parent);
- حذف الحالة 4
- sibling = close_nephew;
- }
- الإدراج
- dir = DIRECTION(node);
- حذف الحالة 3
- return T'
- أدخل الحالة 5
- عمليات المجموعة والعمليات المجمعة
- }
- الدليل
- };
- wait all proc1,proc2
- الخصائص
- struct Node *sub_parent = sub->parent;
- };
- /* symmetric */

على سبيل التعريف، في علوم الكمبيوتر، الشجرة الحمراء والسوداء هي بنية بيانات شجرة بحث ثنائية ذاتية التوازن تتميز بالتخزين السريع واسترجاع المعلومات المنظمة. تحتوي العقد الموجودة في الشجرة ذات اللونين الأحمر والأسود على جزء "لون" إضافي، يتم رسمه غالبًا باللونين الأحمر والأسود، مما يساعد على ضمان أن الشجرة متوازنة دائمًا على وجه التقريب. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
كذلك، عندما يتم تعديل الشجرة، يتم إعادة ترتيب الشجرة الجديدة وإعادة طلائها لاستعادة خصائص التلوين التي تحد من مدى عدم التوازن الذي يمكن أن تصبح عليه الشجرة في أسوأ الحالات. تم تصميم الخصائص بحيث يمكن تنفيذ عملية إعادة الترتيب وإعادة التلوين بكفاءة.
ومن ناحية أخرى، يتطلب تتبع لون كل عقدة بت واحد فقط من المعلومات لكل عقدة لأنه يوجد لونين فقط (بسبب محاذاة الذاكرة الموجودة في بعض لغات البرمجة، قد يختلف استهلاك الذاكرة الحقيقي). لا تحتوي الشجرة على أي بيانات أخرى محددة كونها شجرة حمراء-سوداء، وبالتالي فإن بصمة الذاكرة الخاصة بها متطابقة على وجه التقريب مع بصمة شجرة البحث الثنائية الكلاسيكية (غير الملونة). في بعض الحالات، يمكن تخزين المعلومات المضافة دون أي تكلفة إضافية للذاكرة.
من جانب آخر، إن إعادة التوازن ليست مثالية، ولكنها تضمن البحث في الوقت، حيث هو عدد الإدخالات في الشجرة. يتم تنفيذ عمليات الإدراج والحذف، إلى جانب إعادة ترتيب الشجرة وإعادة تلوينها، كذلك الوقت.
ل هناك شجرة حمراء سوداء عالية مع
كذلك، العقد ( هي دالة الأرضية ) ولا يوجد شجرة حمراء-سوداء بهذا الارتفاع مع عدد أقل من العقد - وبالتالي فهي ضئيلة. ارتفاعه الأسود هو (مع الجذر الأسود) أو للفردية (ثم مع الجذر الأحمر) كذلك
حل الدالة لـ
- عدم المساواة يؤدي إلى ، والتي بالنسبة للأعداد الفردية يؤدي إلى
- .
- لذا في كلتا الحالتين، الزوجية والفردية، هو في الفاصل الزمني
- مع كونه عدد العقد.
return T' /* T[recte T'] */
function joinLeftRB(TL, k, TR):
union {
- // Union so we can use ->left/->right or ->child[0]/->child[1]
- struct {
- struct Node *left;
- struct Node *right;
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;
Mathworld: Red–Black Tree
وفي هذا السياق، San Diego State University: CS 660: Red–Black tree notes, by Roger Whitney
التطبيقات وهياكل البيانات ذات الصلة
ومن ناحية أخرى، في عام 2008، قدم سيدجويك نسخة أبسط من شجرة الأحمر والأسود تسمى من خلال إزالة درجة غير محددة مسبقًا من الحرية في التنفيذ. يحتفظ LLRB بثبات إضافي مفاده أن جميع الروابط الحمراء يجب أن تميل إلى اليسار باستثناء أثناء عمليات الإدراج والحذف. يمكن جعل الأشجار الحمراء والسوداء متساوية القياس إلى ، أو 2-3-4 أشجار، لأي تسلسل من العمليات. تم وصف شجرة القياس المتساوي 2-3-4 في عام 1978 بواسطة سيدجويك. مع وجود 2-3-4 أشجار، يتم حل التماثل اللوني عن طريق «انعكاس اللون»، وهو ما يتوافق مع الانقسام، حيث يترك اللون الأحمر لعقدتين تابعتين العقدتين وينتقل إلى العقدة الأصلية.
كذلك، تُعد الأشجار الحمراء والسوداء ذات قيمة خاصة كذلك في البرمجة الوظيفية، حيث تُعتبر واحدة من أكثر ، والتي تُستعمل لبناء المصفوفات والمجموعات الترابطية التي يمكنها الاحتفاظ بالإصدارات السابقة بعد الطفرات. تتطلب النسخة المستمرة من الأشجار ذات اللون الأحمر والأسود مساحة لكل إدراج أو حذف، إلى جانب الوقت.
من جانب آخر، اعتبارًا من Java 8، تم تعديل هاش ماب بحيث يتم استخدام شجرة حمراء-سوداء بدلاً من استخدام القائمة المرتبطة لتخزين عناصر مختلفة ذات أكواد تجزئة متضاربة. ويؤدي هذا إلى تحسين التعقيد الزمني للبحث عن مثل هذا العنصر من ل أين هو عدد العناصر ذات التجزئات المتصادمة.
ومن ناحية أخرى، الوصف الأصلي ، وهو نوع من الأشجار المُحسّنة للبحث السريع، يستعمل أشجارًا حمراء وسوداء على وجه التحديد كجزء من بنية بياناتها.
وفي السياق ذاته، لكل ، هناك أشجار حمراء-سوداء مقابلة مع عناصر بيانات بنفس الترتيب. إن عمليات الإدراج والحذف في الأشجار 2-3-4 تعادل كذلك عكس الألوان والدوران في الأشجار الحمراء والسوداء. هذا يجعل الأشجار 2-3-4 أداة مهمة لفهم المنطق وراء الأشجار الحمراء-السوداء، وهذا هو السبب في أن الكثير من نصوص الخوارزمية التمهيدية تقدم أشجار 2-3-4 قبل الأشجار الحمراء-السوداء مباشرة، على الرغم من أن أشجار 2-3-4 لا تُستعمل غالبًا في الممارسة العملية.
إضافةً إلى ذلك، توفر الأشجار الحمراء والسوداء أسوأ الضمانات لوقت الإدراج، ووقت الحذف، ووقت البحث. لا يجعلها هذا ذات قيمة في التطبيقات الحساسة للوقت مثل تطبيقات الوقت الفعلي فحسب، بل يجعلها كذلك لبنات بناء قيمة في هياكل البيانات الأخرى التي توفر ضمانات أسوأ الحالات. مثلًا، تعتمد الكثير من هياكل البيانات المستعملة في الهندسة الحسابية على الأشجار الحمراء والسوداء، ويستعمل ونداء نظام إيبول لنواة لينكس أشجارًا حمراء وسوداء. شجرة إيه في إل هي بنية أخرى تدعم البحث والإدراج والإزالة. يمكن تلوين أشجار إيه في إل باللون الأحمر والأسود، وبالتالي فهي مجموعة فرعية من الأشجار ذات اللون الأحمر والأسود. يبلغ أسوأ ارتفاع لإيه في إل 0.720 مرة أسوأ ارتفاع للأشجار ذات اللون الأحمر والأسود، وبالتالي فإن أشجار إيه في إل متوازنة بشكل أكثر صلابة. توصلت قياسات أداء بن فاف مع حالات اختبار واقعية في 79 جولة إلى أن نسبة إيه في إل إلى RB تتراوح بين 0.677 و1.077، والمتوسط عند 0.947، والمتوسط الهندسي 0.910. يقع أداء بين أشجار إيه في إل والأشجار ذات اللون الأحمر والأسود.
ملاحظات حول المخططات المدرجة
من جانب آخر، تحدث الدورات في الحالات I6 و I5 + I6 – خارج الحلقة. لذلك، يحدث دورانان على الأكثر في المجموع.
في هذا الإطار، أ يشير تسجيل الدخول في العمود التالي إلى أن إعادة التوازن اكتملت بهذه الخطوة. إذا كان العمود بعد يحدد حالة واحدة فقط، فسيتم تقديم هذه الحالة باعتبارها الحالة اللاحقة، وإلا فسيتم وضع علامات استفهام.
ومن ناحية أخرى، تم ترتيب الصفوف في الملخص بحيث تكون تغطية جميع حالات RB المحتملة مفهومة بسهولة.
ومن ناحية أخرى، تظهر المخططات العقدة الأصلية P باعتبارها الطفل الأيسر للعقدة الأصلية G على الرغم من أنه من الممكن أن تكون P على أي من الجانبين. يغطي كود العينة كلا الاحتمالين عن طريق المتغير الجانبي dir.
وفي السياق ذاته، في الحالة الثانية، تتفاقم مشكلة إعادة التوازن مستويات الشجرة أو مستوى أسود واحد أعلى في الشجرة، بحيث يصبح الجد G هو العقدة الحالية الجديدة N. لذا يستغرق الأمر الحد الأقصى خطوات التكرار لإصلاح الشجرة (حيث هو ارتفاع الشجرة). نظرًا لأن احتمال التصعيد يتناقص بدرجة كبيرة مع كل خطوة، فإن تكلفة إعادة التوازن الإجمالية تظل ثابتة في المتوسط، بل ثابتة عند الاستهلاك.
وعلى صعيد آخر، في المخططات، يتم استخدام P لوالد N، وG لجدّه، و U لعمّه. في الجدول، يشير "—" إلى الجذر.
وفي هذا الصدد، تظهر المخططات الحالات التي يكون فيها P باللون الأحمر كذلك، وهو انتهاك اللون الأحمر.
وفي السياق ذاته، يشير دوران العمود إلى ما إذا كان الدوران يساهم في إعادة التوازن.
إضافةً إلى ذلك، إذا تم تغيير شيء ما بالحالة، فسيتم عرض ذلك في مجموعة الأعمدة بعد.
ومن جهة أخرى، يُظهر تعيين العمود تعيين N قبل الدخول إلى خطوة لاحقة. من المحتمل أن يؤدي هذا إلى إعادة تعيين العقد الأخرى P و G و U كذلك.
من جانب آخر، يشير العمود x إلى التغيير في اتجاه الطفل، أي أن o (لـ "الخارجي") يعني أن P و N كلاهما طفلان أيسر أو كلاهما طفلان أيمن، بينما i (لـ "الداخلي") يعني أن اتجاه الطفل يتغير من P إلى N.
وعلى صعيد آخر، مجموعة الأعمدة السابقة تحدد الحالة التي يتم إعطاء اسمها في حالة العمود. وبالتالي، سيتم تجاهل القيم المحتملة في الخلايا الفارغة. لذلك في الحالة I2، يغطي كود العينة كلا احتمالات الاتجاهات الفرعية لـ N، على الرغم من أن الرسم التخطيطي المقابل يظهر واحدًا فقط.
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)
أدخل الحالة 2
وفي هذا السياق، إذا كان كل من الوالد P والعم U باللون الأحمر، فيمكن إعادة طلاء كليهما باللون الأسود ويصبح الجد G باللون الأحمر للحفاظ على المتطلب 4. نظرًا لأن أي مسار عبر الوالد أو العم يجب أن يمر عبر الجد، فإن عدد العقد السوداء على هذه المسارات لم يتغير. ومع ذلك، قد ينتهك الجد G الآن الشرط 3، إذا كان لديه أحد الوالدين باللون الأحمر. بعد إعادة تسمية G إلى N، يتم استيفاء ثابت الحلقة بحيث يمكن تكرار إعادة التوازن على مستوى أسود واحد (= مستويين للشجرة) أعلى.
/* 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
أدخل الحالة 3
علاوةً على ذلك، تم تنفيذ الحالة 2 لإدراج مرات وزاد الارتفاع الإجمالي للشجرة بمقدار 1، حيث أصبح الآن . العقدة الحالية N هي الجذر (الأحمر) للشجرة، وجميع خصائص RB مُرضية.
أدخل الحالة 1
ومن ناحية أخرى، العقدة الأصلية P للعقدة الحالية هي سوداء، لذا فإن المتطلب 3 صحيح. ينطبق المتطلب رقم 4 كذلك بحسب ثابت الحلقة.
I.sort
- bulklInsertRec(T, I, k)
- bulkInsertRec(T, I, k):
- if k = 1:
- forall e in I: T.insert(e)
- else
حذف الحالة 5
ومن جهة أخرى، الأخ S أسود اللون، والطفل المقرب لـ S C أحمر اللون، والطفل البعيد لـ S D أسود اللون. بعد في S، يصبح ابن الأخ C والد S وشقيق N الجديد. يتم تبادل ألوان S و C. لا تزال جميع المسارات تحتوي على نفس عدد العقد السوداء، ولكن الآن أصبح لدى N شقيق أسود يكون طفله البعيد أحمر، وبالتالي تكون الكوكبة مناسبة للحالة D6. لا يتأثر N ولا أصله P بهذا التحويل، وقد يكون P أحمر أو أسود ( في الرسم التخطيطي).
أدخل الحالة 4
ومن ناحية أخرى، الأصل P أحمر والجذر. نظرًا لأن N كذلك أحمر، يتم انتهاك المتطلب 3. ولكن بعد تبديل لون P تصبح الشجرة على شكل RB. يزداد ارتفاع الشجرة السوداء بمقدار 1.
حذف الحالة 2
وفي هذا السياق، أطفال P و S و S من السود. بعد طلاء S باللون الأحمر، فإن جميع المسارات التي تمر عبر S، والتي هي على وجه التحديد المسارات التي لا تمر عبر N، تحتوي على عقدة سوداء أقل. الآن تحتوي جميع المسارات في الشجرة الفرعية التي يتجذرها P على نفس عدد العقد السوداء، ولكن أقل بعقدة واحدة من المسارات التي لا تمر عبر P، لذلك لا يزال من الممكن انتهاك المتطلب 4. بعد إعادة تسمية P إلى N، يتم استيفاء ثابت الحلقة بحيث يمكن تكرار إعادة التوازن على مستوى أسود واحد (= مستوى شجرة واحد) أعلى.
إزالة ورقة سوداء غير جذرية
من جانب آخر، الحالة المعقدة هي عندما لا يكون 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 {
الخوارزميات المتوازية
ومن جهة أخرى، يمكن تشغيل الخوارزميات المتوازية لبناء أشجار حمراء وسوداء من قوائم مرتبة من العناصر في وقت ثابت أو الوقت، اعتمادًا على طراز الكمبيوتر، إذا كان عدد المعالجات المتاحة متناسبًا بشكل مقارب مع عدد من العناصر حيث . ومن المعروف كذلك أن خوارزميات البحث السريع والإدراج والحذف المتوازية معروفة كذلك.
ومن ناحية أخرى، تُعد للأشجار الحمراء والسوداء متوازية للعمليات الشاملة، بما في ذلك الاتحاد، والتقاطع، والإنشاء، والتصفية، والاختزال بالخريطة، وما إلى ذلك.
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;
شجرة أدلسن فالسكي ولانديس
- شجرة بي (, , شجرة بي بلس، شجرة بي, )
- المراجع والملاحظات
- للقراءة الإضافية
} while (parent = node->parent);
- case_5:
- rotate_subtree(tree, sibling, 1 - dir);
- sibling->color = RED;
- close_nephew->color = BLACK;
- distant_nephew = sibling;
الحالات البسيطة
إضافةً إلى ذلك، عندما يكون للعقدة المحذوفة طفل واحد فقط (غير فارغ). في هذه الحالة، فقط استبدل العقدة بطفلها، وقم بتلوينها باللون الأسود.
ومن ناحية أخرى، عندما لا تحتوي العقدة المحذوفة على أطفال (كلاهما NULL)، وتكون حمراء، قم ببساطة بإزالة عقدة الورقة.
من جانب آخر، عندما لا تحتوي العقدة المحذوفة على أطفال (NULL) وتكون هي الجذر، استبدلها بـ NULL. الشجرة فارغة.
ومن جهة أخرى، يجب أن يكون الطفل الفردي (غير NULL) باللون الأحمر بحسب الاستنتاج 5، ويجب أن تكون العقدة المحذوفة باللون الأسود بحسب المتطلب 3.
وفي السياق ذاته، عندما يكون للعقدة المحذوفة طفلان (غير فارغين)، فيمكننا تبديل قيمتها بخليفتها بالترتيب (الطفل الأيسر من الشجرة الفرعية اليمنى)، ثم حذف الخليفة بدلاً من ذلك. نظرًا لأن الخليفة هو أقصى اليسار، فلا يمكن أن يكون له سوى طفل أيمن (غير NULL) أو لا يمكن أن يكون له أي طفل على الإطلاق.
علاوةً على ذلك، عندما لا تحتوي العقدة المحذوفة على أطفال (كلاهما NULL)، وتكون سوداء، فإن حذفها سيؤدي إلى إنشاء اختلال في التوازن، ويتطلب إعادة التوازن، كما هو موضح في القسم التالي.
وقت التنفيذ
من جانب آخر، لم يتم أخذ الفرز في الاعتبار في هذا التحليل. كذلك، من المفترض أن يكون أصغر من وإلا فسيكون من الأكثر كفاءة إنشاء الشجرة الناتجة من الصفر.
العمل
أدخل الحالة 6
الإزالة
ومن جهة أخرى، من المؤكد الآن أن العقدة الحالية N هي حفيدة "خارجية" لـ G (يسار الطفل الأيسر أو يمين الطفل الأيمن). الآن عند G، ووضع P في مكان G وجعل P هو الأصل لـ N و G. G هو اللون الأسود وطفله السابق P هو اللون الأحمر، نظرًا لانتهاك المتطلب 3. بعد تبديل ألوان P و G، فإن الشجرة الناتجة تلبي المتطلب 3. يظل المتطلب رقم 4 مُلبى كذلك، حيث أن جميع المسارات التي مرت عبر G الأسود تمر الآن عبر P الأسود.
وفي السياق ذاته، نظرًا لأن الخوارزمية تقوم بتحويل المدخلات دون استخدام بنية بيانات مساعدة واستخدام كمية صغيرة فقط من مساحة التخزين الإضافية للمتغيرات المساعدة، فهي في مكانها.
حذف الحالة 6
وعلى صعيد آخر، الأخ S أسود اللون، والطفل البعيد D أحمر اللون. بعد عند P، يصبح الأخ S هو والد الطفل البعيد D لـ P و S. يتم تبادل ألوان P و S، ويصبح D أسود. لا تزال الشجرة الفرعية بأكملها تحمل نفس اللون عند جذرها S، أي إما أحمر أو أسود ( في الرسم التخطيطي، والذي يشير إلى نفس اللون قبل وبعد التحويل. بهذه الطريقة يتم الحفاظ على المتطلب رقم 3. إن المسارات الموجودة في الشجرة الفرعية التي لا تمر عبر N (أي تمر عبر D والعقدة 3 في الرسم التخطيطي) تمر عبر نفس عدد العقد السوداء كما في السابق، ولكن N لديه الآن سلف أسود إضافي: إما أن P أصبح أسود، أو كان أسودًا وتمت إضافة S كجد أسود. وبالتالي، تمر المسارات التي تمر عبر N عبر عقدة سوداء إضافية، بحيث يتم استعادة المتطلب 4 وتصبح الشجرة الإجمالية على شكل RB.
في هذا الإطار، نظرًا لأن الخوارزمية تقوم بتحويل المدخلات دون استخدام بنية بيانات مساعدة واستخدام كمية صغيرة فقط من مساحة التخزين الإضافية للمتغيرات المساعدة، فهي في مكانها.
إثبات الحدود
A complete and working implementation in C
وفي هذا الصدد، – Visualization of random and pre-sorted data insertions, in elementary binary search trees, and left-leaning red–black trees
OCW MIT Lecture on Red-black Trees by Erik Demaine
Red–black BSTs in 3.3 Balanced Search Trees
An intrusive red–black tree written in C++
الانضمام القائم
ومن جهة أخرى، لاحقًا يجب تقسيم الشجرة إلى أجزاء بطريقة ما، بحيث يكون لكل تنطبق القيود التالية:
ومن ناحية أخرى، الآن تقوم الخوارزمية بإدراج كل عنصر من داخل بالتتابع. يجب تنفيذ هذه الخطوة لكل ، ويمكن القيام بذلك بواسطة ما يصل إلى معالج بالتوازي.
في هذا الإطار، يمكن تطبيق هذا النهج على كل بنية بيانات تسلسلية مرتبة تدعم عمليات الانضمام والتقسيم الفعالة. الفكرة العامة هي تقسيم و إلى أجزاء متعددة وإجراء الإدخالات على هذه الأجزاء بالتوازي.
bulkInsert(T, I, k):
علاوةً على ذلك، وأخيرًا، سيتم ضم الأشجار الناتجة لتشكيل النتيجة النهائية للعملية بأكملها.
أولاً يجب فرز الأكبر من العناصر المراد إدراجها.
وعلى صعيد آخر، لاحقًا، تقوم الخوارزمية بتقسيم إلى أجزاء بأحجام متساوية على وجه التقريب.
إضافةً إلى ذلك، لاحظ أنه في الخطوة 3، القيود المفروضة على التقسيم أؤكد أنه في الخطوة 5، يمكن ضم الأشجار مرة أخرى وفرز التسلسل الناتج.
وعلى صعيد آخر، يُظهر الكود الزائف تنفيذًا بسيطًا لتقسيم وغزو لخوارزمية تعتمد على الانضمام للإدراج بالجملة. يمكن تنفيذ كلا النداءين المتكررين بالتوازي. تختلف عملية الانضمام المستعملة هنا عن الإصدار الموضح في هذه المقالة، حيث يتم استخدام join2 بدلاً من ذلك، والذي يفتقد المعلمة الثانية k.
ملاحظات حول الكود النموذجي ومخططات الإدراج والإزالة
وفي هذا السياق، مثلث مرقم ربما يمثل شجرة فرعية حمراء-سوداء ذات ارتفاع أسود أقل بمقدار واحد، أي أن الشجرة الأصلية لها ارتفاع أسود يساوي صفرًا في التكرار الثاني.
ومن ناحية أخرى، يرمز إلى عقدة حمراء و عقدة سوداء (غير فارغة) (ارتفاعها أسود ≥ 1)، يرمز إلى اللون الأحمر أو الأسود لعقدة غير فارغة، ولكن نفس اللون في نفس الرسم البياني. لا يتم تمثيل العقد NULL في المخططات.
إضافةً إلى ذلك، يعرض إجراء "الإدخال" مجموعة العقد مع ألوانها والتي تحدد حالة وتنتهك في الغالب بعض المتطلبات. يحيط إطار أزرق بالعقدة الحالية N ويتم تسمية العقد الأخرى بحسب علاقتها بـ N.
وفي هذا السياق، يقوم الاقتراح بتقسيم كل من الإدراج والإزالة (ناهيك عن بعض الحالات البسيطة للغاية) إلى ستة مجموعات من العقد والحواف والألوان، والتي تسمى الحالات. يتضمن الاقتراح، لكل من الإدراج والإزالة، حالة واحدة فقط تعمل على تقدم مستوى أسود واحد أقرب إلى الجذر والحلقات، بينما تعمل الحالات الخمس الأخرى على إعادة توازن الشجرة الخاصة بها. يتم تصوير الحالات الأكثر تعقيدًا في الرسم التخطيطي.
وعلى صعيد آخر، يحتوي الرسم التخطيطي على ثلاثة أعمدة واثنين إلى أربعة إجراءات. يُظهر العمود الأيسر التكرار الأول، ويُظهر العمود الأيمن التكرارات الأعلى، ويُظهر العمود الأوسط تقسيم الحالة إلى أفعالها المختلفة.
ومن جهة أخرى، إذا كانت هناك حاجة إلى الإصلاح، فإن الحالات تستعمل كود الحالات الأخرى وهذا بعد إعادة تعيين العقدة الحالية N، والتي تحمل بدورها حلقة زرقاء والتي قد يتعين إعادة تعيين العقد الأخرى إليها كذلك. يُسمى هذا الإجراء "إعادة التعيين". بالنسبة لكلا العمليتين، الإدراج والحذف، هناك حالة واحدة (بالضبط) تكرر مستوى أسود واحدًا أقرب إلى الجذر؛ ثم تلبي الكوكبة المعاد تعيينها الثوابت الحلقية المقابلة.
وفي هذا الصدد، مثلث مرقم ربما به دائرة سوداء في الأعلى يمثل شجرة فرعية حمراء-سوداء (متصلة بوالدها بحسب المتطلب 3 ) بارتفاع أسود يساوي مستوى التكرار ناقص واحد، أي صفر في التكرار الأول. قد يكون جذره أحمر أو أسود.
كذلك، إذا تم اعتبار الدوران مفيدًا، فسيتم تصويره في الإجراء التالي، والذي يسمى "الدوران".
في هذا الإطار، يشير المتغير N إلى العقدة الحالية، والتي تم تسميتها ن أو ن في المخططات.
علاوةً على ذلك، إذا تم اعتبار بعض إعادة التلوين مفيدًا، فسيتم تصوير ذلك في الإجراء التالي، والذي يُسمى "اللون".
struct Node {
struct Node *parent; // null for the root node
عمليات الجملة المتوازية
وعلى صعيد آخر، لا تنطبق الخوارزميات الخاصة بالعمليات المجمعة على الشجرة الحمراء والسوداء فحسب، بل يمكن تكييفها مع هياكل بيانات متسلسلة مرتبة أخرى كذلك، مثل ، ، وشجرة (أ، ب). سيتم شرح الخوارزميات المختلفة للإدراج بالجملة فيما يلي، ولكن يمكن كذلك تطبيق نفس الخوارزميات للإزالة والتحديث. الإدراج المجمع هو عملية تقوم بإدراج كل عنصر من التسلسل في شجرة .
من جهة ثانية، يمكن تنفيذ عمليات أساسية، مثل الإدراج والإزالة والتحديث، بالتوازي من خلال تحديد عمليات لمعالجة كميات كبيرة من عناصر متعددة. كما يمكن معالجة كميات كبيرة من خلال عدة عمليات أساسية، مثلًا، قد تحتوي الكميات الكبيرة على عناصر لإدراجها وعناصر لإزالتها من الشجرة.
// parent is optional
- 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;
- }
وفي هذا الصدد، void insert(struct Tree *tree, struct Node *node, struct Node *parent, enum Dir dir) {
التنفيذ
وعلى صعيد آخر، هذا مثال لتطبيق الإدراج والإزالة في لغة C. فيما يلي هياكل البيانات ودالة المساعدة rotate_subtree المستعملة في أمثلة الإدراج والإزالة.
وفي السياق ذاته، لا تتطلب العمليات للقراءة فقط، مثل البحث أو عبور الشجرة، على شجرة حمراء سوداء أي تعديل عن تلك المستعملة لأشجار البحث الثنائية، لأن كل شجرة حمراء سوداء هي حالة خاصة من شجرة بحث ثنائية بسيطة. ومع ذلك، فإن النتيجة المباشرة للإدراج أو الإزالة قد تنتهك خصائص الشجرة الحمراء والسوداء، والتي تسمى عملية استعادتها بإعادة التوازن بحيث تصبح الأشجار الحمراء والسوداء متوازنة ذاتيا. إن إعادة التوازن (أي تغييرات اللون) لها أسوأ تعقيد زمني ومتوسط ، على الرغم من أن هذه سريعة جدًا في الممارسة العملية. فضلًا عن ذلك، لا تستغرق عملية إعادة التوازن أكثر من ثلاث دورات للشجرة (اثنتان للإدراج).
- enum Color { BLACK, RED };
- enum Dir { LEFT, RIGHT };
- // red-black tree node
خطوط الأنابيب
ومن جهة أخرى، هناك طريقة أخرى لتنفيذ العمليات المجمعة بالتوازي وهي استخدام نهج الأنابيب. يمكن القيام بذلك عن طريق تقسيم مهمة معالجة عملية أساسية إلى سلسلة من المهام الفرعية. بالنسبة للعمليات الأساسية المتعددة، يمكن معالجة المهام الفرعية بالتوازي عن طريق تعيين كل مهمة فرعية إلى معالج منفصل.
ومن ناحية أخرى، إذا كان لعقدتين أسلاف سوداء أقرب مختلفة، فيمكن إصلاحهما بالتوازي. وبما أنه لا يمكن أن يكون لأربع عقد على الأكثر نفس السلف الأسود الأقرب، فيمكن إصلاح العقد في المستوى الأدنى بعدد ثابت من الخطوات المتوازية.
أولاً يجب فرز الجزء الأكبر من العناصر المراد إدراجها.
علاوةً على ذلك، من المحتمل أن تحتوي على عقدتين حمراوين متتاليتين في نهاية المسارات من الجذر إلى الأوراق، والتي تحتاج إلى إصلاح. لاحظ أنه أثناء الإصلاح يجب تحديث موضع إدراج العناصر 𝑆، إذا تأثرت العقد المقابلة بالدوران.
وفي هذا الصدد، تُكرر الخطوات من 3 إلى 5 على المتتاليات الجزئية الجديدة حتى تصبح فارغة. عند هذه النقطة، يكون كل عنصر قد أُضيف. يُسمى كل تطبيق لهذه الخطوات مرحلة. بما أن طول المتتاليات الجزئية في هو وفي كل مرحلة تُقسّم المتتاليات الجزئية إلى النصف، فإن عدد المراحل هو .
من جهة ثانية، بما أن جميع المراحل تتحرك صعودًا عبر مستويات الظلام في الشجرة، فيمكن ربطها بالتوازي في خط أنابيب. بمجرد انتهاء كل مرحلة من معالجة مستوى أسود واحد، تتمكن المرحلة التالية من التحرك صعودًا والاستمرار على هذا المستوى.
وعلى صعيد آخر، لكل عنصر في ، تحدد الخوارزمية موضع الإدراج المقابل في . يمكن إجراء ذلك بالتوازي لكل عنصر لأن لن يتعرض للطفرات في هذه العملية. الآن، يجب تقسيم إلى متتاليات فرعية بحسب موضع إدراج كل عنصر. مثلًا، هي المتتالية الفرعية لـ التي تحتوي على العناصر التي يكون موضع إدراجها على يسار العقدة .
في هذا الإطار، سيتم إدراج العنصر الأوسط من كل متتالية فرعية في كعقدة جديدة . يمكن إجراء ذلك بالتوازي لكل حيث أن موضع إدراج كل فريد، بحكم التعريف. إذا احتوى على عناصر على يسار أو يمين ، فسيتم تضمينها في مجموعة جديدة من المتتاليات الفرعية S مثل أو .
إضافةً إلى ذلك، سيتم تطبيق هذه الخطوة بالتتابع على مستويات السواد أعلاه حتى يتم إصلاح بالكامل.
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;
sibling = close_nephew;
distant_nephew = sibling->child[1 - dir]؛
if (distant_nephew && distant_nephew->color == RED)
المصطلحات
ومن ناحية أخرى، يتم تعريف العمق الأسود للعقدة على أنه عدد العقد السوداء من الجذر إلى تلك العقدة (أي عدد الأسلاف السود). الارتفاع الأسود لشجرة حمراء-سوداء هو عدد العقد السوداء في أي مسار من الجذر إلى الأوراق، والذي، بحسب المتطلب 4، يكون ثابتًا (بدلاً من ذلك، يمكن تعريفه على أنه العمق الأسود لأي عقدة ورقة). الارتفاع الأسود للعقدة هو الارتفاع الأسود للشجرة الفرعية التي تتبعها. في هذه المقالة، يجب تعيين الارتفاع الأسود للعقدة الفارغة إلى 0، لأن شجرتها الفرعية فارغة كما يقترح الشكل التوضيحي، وارتفاع شجرتها هو 0 كذلك.
T'.right.right.color=black;
return rotateLeft(T')
الخاتمة
شجرة حمراء سوداء اللون العقد (المفاتيح) لها ارتفاع شجرة
ملاحظة
إضافةً إلى ذلك، يجب أن تحدث عبارات if ذات الصلة بشكل أقل تكرارًا إذا تم تحقيق الاقتراح.
وعلى صعيد آخر، لذلك، يجب أن نضع في الاعتبار أن كلا البيانين لا يتم تقييمهما بشكل إجمالي، إذا كان U == NULL. ثم في كلتا الحالتين لا يتم المساس U->color (انظر ). (التعليق considered black يتوافق مع المتطلب 2. )
- من أجل التبسيط، يستعمل الكود النموذجي الفصل :
- والعطف :
- U ! = NULL && U->color == RED // not considered black
sub->parent = new_root;
- if (sub_parent)
- sub_parent->child[sub == sub_parent->right] = new_root;
- else
- tree->root = new_root;
- return new_root;
- }
m := ⌊size(I) / 2⌋
- (T1, _, T2) := split(T, I[m])
- bulkInsertRec(T1, I[0.. m], ⌈k / 2⌉)
- T ← join2(T1, T2)
}
من جانب آخر، في بداية كل تكرار، يكون ارتفاع اللون الأسود لـ N مساويًا لرقم التكرار ناقص واحد، مما يعني أنه في التكرار الأول يكون صفرًا وأن N هي عقدة سوداء حقيقية في التكرارات الأعلى.
ملاحظات حول مخططات الحذف
في هذا الإطار، عدد العقد السوداء على المسارات عبر N أقل بواحدة مما كان عليه قبل الحذف، في حين أنه لم يتغير في جميع المسارات الأخرى، بحيث يكون هناك انتهاك للون الأسود عند P إذا كانت هناك مسارات أخرى موجودة.
تحتوي حلقة إعادة التوازن لعملية الحذف على الثابت التالي:
من جانب آخر، يتم استيفاء جميع الخصائص الأخرى (بما في ذلك المتطلب 3 ) في جميع أنحاء الشجرة.
التاريخ
إضافةً إلى ذلك، في ورقة بحثية عام 1978 بعنوان "إطار ثنائي اللون للأشجار المتوازنة"، استنتج ليونيداس جيه. جويباس الشجرة الحمراء والسوداء من شجرة B الثنائية المتماثلة. تم اختيار اللون "الأحمر" لأنه كان اللون الأفضل مظهرًا الذي أنتجته طابعة الليزر الملونة المتاحة للمؤلفين أثناء العمل في زيروكس بارك. رد آخر من غيباس ينص على أن ذلك كان بسبب الأقلام الحمراء والسوداء المتاحة لهم لرسم الأشجار.
من جانب آخر، في عام 1999، أظهر كيفية جعل عملية الإدخال عملية وظيفية بحتة. كانت وظيفة التوازن الخاصة بها بحاجة إلى الاهتمام بأربع حالات غير متوازنة وحالة متوازنة افتراضية واحدة فقط.
من جهة ثانية، في سنة 1972، اخترع رودولف باير بنية بيانات كانت عبارة عن حالة خاصة من الدرجة الرابعة لشجرة B. حافظت هذه الأشجار على جميع المسارات من الجذر إلى الورقة بنفس عدد العقد، مما أدى إلى إنشاء أشجار متوازنة تمامًا. ومع ذلك، فإنها لم تكن أشجار بحث ثنائية. أطلق باير عليهم اسم "شجرة B الثنائية المتماثلة" في ورقته البحثية، وفي وقت لاحق أصبحت شائعة أو حتى 2-3 أشجار.
ومن ناحية أخرى، استعملت الخوارزمية الأصلية 8 حالات غير متوازنة، لكن كورمن وآخرون (2001) قلصوا ذلك إلى 6 حالات غير متوازنة. أظهر سيدجويك أن عملية الإدراج يمكن تنفيذها في 46 سطرًا فقط من جافا. في عام 2008، اقترح سيدجويك ، مستفيدًا من فكرة أندرسون التي قامت بتبسيط عمليات الإدراج والحذف. سمح سيدجويك في البداية بالعقد التي يكون طفليها باللون الأحمر، مما يجعل أشجاره أشبه بـ 2-3-4 أشجار، ولكن في وقت لاحق تمت إضافة هذا القيد، مما يجعل الأشجار الجديدة أشبه بـ 2-3 أشجار. قام سيدجويك بتنفيذ خوارزمية الإدراج في 33 سطرًا فقط، مما أدى إلى تقصير 46 سطرًا من الكود الأصلي بدرجة كبيرة.
ومن ناحية أخرى، في سنة 1993، قدم أرن أندرسون فكرة الشجرة ذات الميل الأيمن لتبسيط عمليات الإدراج والحذف.
تشبيه بالأشجار 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 إدارة متجهات ذات أطوال متغيرة، في حين أن الأشجار الحمراء والسوداء هي ببساطة أشجار ثنائية.
وقت التنفيذ
وعلى صعيد آخر، يمكن تحسين ذلك باستخدام خوارزميات متوازية للتقسيم والانضمام. في هذه الحالة يكون وقت التنفيذ هو .
لم يتم أخذ الفرز في الاعتبار في هذا التحليل.
العمل
حذف الحالة 1
من جهة ثانية، العقدة الحالية N هي الجذر الجديد. تمت إزالة عقدة سوداء واحدة من كل مسار، لذلك يتم الحفاظ على خصائص RB. ينخفض ارتفاع الشجرة السوداء بمقدار 1.
dir = DIRECTION(parent);
- struct Node *uncle = grandparent->child[1 - dir]؛
- if (node == parent->child[1 - dir]) {
- // Case #5
- rotate_subtree(tree, parent, dir);
حذف الحالة 4
وفي هذا الصدد، أطفال الأخوين S و S هم من السود، ولكن P هو أحمر. لا يؤثر تبادل ألوان S و P على عدد العقد السوداء على المسارات التي تمر عبر S، ولكنه يضيف واحدًا إلى عدد العقد السوداء على المسارات التي تمر عبر N، مما يعوض العقدة السوداء المحذوفة على تلك المسارات.
sibling = close_nephew;
- case_6:
- rotate_subtree(tree, parent, dir);
- sibling->color = parent->color;
- parent->color = BLACK;
- distant_nephew->color = BLACK;
- return;
}
إضافةً إلى ذلك، يتم استيفاء المتطلب 3 لجميع أزواج العقدة ← الأصل مع الاستثناء المحتمل العقدة ← الأصل عندما يكون الأصل كذلك باللون الأحمر ( انتهاك اللون الأحمر في العقدة ).
- تحتوي حلقة إعادة التوازن لعملية الإدراج على الثوابت التالية:
- العقدة هي العقدة الحالية، في البداية عقدة الإدراج.
- العقدة باللون الأحمر في بداية كل تكرار.
إضافةً إلى ذلك، يتم استيفاء جميع الخصائص الأخرى (بما في ذلك المتطلب 4 ) في جميع أنحاء الشجرة.
الإدراج
وفي هذا السياق، تبدأ عملية الإدراج بوضع العقدة الجديدة (غير NULL)، مثلًا N، في الموضع في شجرة البحث الثنائية لعقدة NULL التي يكون مفتاح سابقتها بالترتيب أقل من مفتاح العقدة الجديدة، والتي بدورها تكون أقل من مفتاح خليفتها بالترتيب. (في كثير من الأحيان، يكون هذا التموضع نتيجة لعملية بحث داخل الشجرة تسبق عملية الإدراج مباشرةً وتتكون من عقدة P مع اتجاه dir مع يتم تلوين العقدة المدرجة حديثًا باللون الأحمر مؤقتًا حتى تحتوي جميع المسارات على نفس عدد العقد السوداء كما في السابق. ولكن إذا كان الوالد، مثلًا P، أحمر كذلك، فإن هذا الإجراء يؤدي إلى انتهاك اللون الأحمر.
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;
حذف الحالة 3
كذلك، الأخ S أحمر اللون، لذلك يجب على P وأبناء الأخ C و D أن يكونوا أسود اللون. يؤدي عند P إلى تحويل S إلى جد N. ثم بعد عكس ألوان P و S، فإن المسار عبر N لا يزال قصيرًا بعقدة سوداء واحدة. لكن N لديه الآن أحد الوالدين الأحمر P وبعد إعادة التعيين لديه شقيق أسود S، وبالتالي فإن التحولات في الحالات 4 أو 5 أو 6 قادرة على استعادة شكل RB.
return T'
if TR.blackHeight>TL.blackHeight:
أدخل الحالة 5
ومن ناحية أخرى، الوالد P أحمر ولكن العم U أسود. الهدف النهائي هو تدوير العقدة الأصلية P إلى موضع الجد، ولكن هذا لن ينجح إذا كان N حفيدًا "داخليًا" لـ G (أي إذا كان N هو الطفل الأيسر للطفل الأيمن لـ G أو الطفل الأيمن للطفل الأيسر لـ G ). يؤدي عند P إلى تبديل أدوار العقدة الحالية N وعقدتها الأم P. يضيف الدوران مسارات عبر N (تلك الموجودة في الشجرة الفرعية المسماة 2، انظر الرسم التخطيطي) ويزيل المسارات عبر P (تلك الموجودة في الشجرة الفرعية المسماة 4 ). لكن كل من P و N أحمران، لذا يتم الحفاظ على المتطلب رقم 4. تم استعادة المتطلب 3 في الحالة 6.
عمليات المجموعة والعمليات المجمعة
في هذا الإطار، إذا كان للشجرتين نفس الارتفاع الأسود، فإن جوين يقوم ببساطة بإنشاء عقدة جديدة مع شجرة فرعية يسارية وجذر وشجرة فرعية يمينية . إذا كان كل من و لهما جذر أسود، فاضبط ليكون أحمر. وإلا فسيتم تعيين باللون الأسود.
وفي السياق ذاته، إذا كان للشجرتين نفس الارتفاع الأسود، فإن جوين يقوم ببساطة بإنشاء عقدة جديدة مع شجرة فرعية يسارية وجذر وشجرة فرعية يمينية . إذا كان كل من و لهما جذر أسود، فاضبط ليكون أحمر. وإلا فسيتم تعيين باللون الأسود.
في هذا الإطار، الانضمام : تعمل دالة الانضمام على شجرتين مع مفتاح ، حيث ، أي أن جميع المفاتيح أصغر من ، وجميع المفاتيح أكبر من . تُرجع هذه الدالة شجرة تحتوي على جميع العناصر في وكذلك .
ومن ناحية أخرى، إذا كانت ارتفاعات اللون الأسود غير متساوية، افترض أن ارتفاع اللون أكبر من ارتفاع اللون (الحالة الأخرى تكون متماثلة). ينضم العمود الفقري الأيمن لـ حتى العقدة السوداء ، والتي تكون متوازنة مع . في هذه المرحلة، تُنشأ عقدة جديدة مع الابن الأيسر ، والجذر (مُعَيَّن ليكون أحمر)، والابن الأيمن لتحل محل c. قد تُبطل العقدة الجديدة ثابت الأحمر-الأسود، إذ لا يمكن ظهور أكثر من ثلاث عقد حمراء في صف واحد. يمكن إصلاح ذلك من خلال الدوران المزدوج. إذا انتشرت المشكلة الحمراء المزدوجة إلى الجذر، فسيتم فيما بعد تعيين الجذر ليكون أسود، واستعادة الخصائص. تكلفة هذه الوظيفة هي الفرق بين ارتفاعات اللون الأسود بين شجرتي الإدخال.
- خوارزمية الانضمام هي كما يلي:
- 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):
وعلى صعيد آخر، بالنسبة لبعض التطبيقات، تقوم Split كذلك بإرجاع قيمة منطقية تشير إلى ما إذا كان يظهر في الشجرة. تكلفة الانقسام هي ترتيب ارتفاع الشجرة. في الواقع، لا علاقة لهذه الخوارزمية بأي خصائص خاصة لشجرة حمراء-سوداء، ويمكن استخدامها على أي شجرة باستخدام عملية ربط، مثل شجرة إيه في إل.
وعلى صعيد آخر، تقسيم : لتقسيم شجرة حمراء-سوداء إلى شجرتين أصغر، تلك الأصغر من المفتاح ، وتلك الأكبر من المفتاح ، ارسم أولاً مسارًا من الجذر عن طريق إدخال في الشجرة الحمراء-السوداء. بعد هذا الإدراج، سيتم العثور على جميع القيم الأقل من على يسار المسار، وسيتم العثور على جميع القيم الأكبر من على اليمين. من خلال تطبيق جوين، يتم دمج جميع الأشجار الفرعية على الجانب الأيسر من الأسفل إلى الأعلى باستخدام المفاتيح الموجودة على المسار كعقد وسيطة من الأسفل إلى الأعلى لتشكيل الشجرة اليسرى، والجزء الأيمن متماثل.
وعلى صعيد آخر، إذا كانت ارتفاعات اللون الأسود غير متساوية، افترض أن ارتفاع اللون أكبر من ارتفاع اللون (الحالة الأخرى تكون متماثلة). ينضم العمود الفقري الأيمن لـ حتى العقدة السوداء ، والتي تكون متوازنة مع . في هذه المرحلة، تُنشأ عقدة جديدة مع الابن الأيسر ، والجذر (مُعَيَّن ليكون أحمر)، والابن الأيمن لتحل محل c. قد تُبطل العقدة الجديدة ثابت الأحمر-الأسود، إذ لا يمكن ظهور أكثر من ثلاث عقد حمراء في صف واحد. يمكن إصلاح ذلك من خلال الدوران المزدوج. إذا انتشرت المشكلة الحمراء المزدوجة إلى الجذر، فسيتم فيما بعد تعيين الجذر ليكون أسود، واستعادة الخصائص. تكلفة هذه الوظيفة هي الفرق بين ارتفاعات اللون الأسود بين شجرتي الإدخال.
علاوةً على ذلك، فضلًا عن عمليات الإدراج والحذف والبحث لعنصر واحد، تم تعريف الكثير من عمليات المجموعة على الاتحاد والتقاطع وفرق المجموعة. ومن ثم يمكن تنفيذ عمليات سريعة مجمعة للإدراج أو الحذف استنادًا إلى هذه الوظائف المحددة. تعتمد عمليات المجموعة هذه على عمليتين مساعدتين، التقسيم والانضمام. بفضل العمليات الجديدة، يمكن أن يصبح تنفيذ الأشجار الحمراء والسوداء أكثر كفاءة وقابلية للتوازي بدرجة كبيرة. من أجل تحقيق تعقيدات الوقت، يتطلب هذا التنفيذ أن يُسمح للجذر بأن يكون أحمر أو أسود، وأن تخزن كل عقدة ارتفاعها الأسود الخاص بها.
}
if (distant_nephew && distant_nephew->color == RED)
الدليل
إضافةً إلى ذلك، لكي تحتوي شجرة حمراء-سوداء ذات ارتفاع معين على عدد أدنى من العقد، يجب أن يكون لديها مسار واحد طويل مع أقصى عدد من العقد الحمراء، لتحقيق أقصى ارتفاع للشجرة مع أدنى ارتفاع للأسود. فضلًا عن هذا المسار، يجب أن تكون جميع العقد الأخرى باللون الأسود. إذا تمت إزالة عقدة من هذه الشجرة فإنها تفقد ارتفاعها أو بعض خصائص RB.
وفي السياق ذاته، لكي تحتوي شجرة حمراء-سوداء ذات ارتفاع معين على أقل عدد من العقد، يجب أن يكون لها مسار واحد فقط طويل يحتوي على أقصى عدد من العقد الحمراء، وذلك لتحقيق أقصى ارتفاع للشجرة مع أدنى ارتفاع للعقد السوداء. فضلًا عن هذا المسار، يجب أن تكون جميع العقد الأخرى سوداء. إذا أُزيلت عقدة من هذه الشجرة، فإنها إما تفقد ارتفاعها أو إحدى خصائص RB.
شجرة ارتفاع RB مع الجذر الأحمر هو الحد الأدنى. وهذا يتفق مع
علاوةً على ذلك، رسم بياني للدالة محدب مع نقاط توقف عند أين تمت جدولة الوظيفة على النحو التالي A027383( h –1) لـ
من جهة ثانية، شجرة RB صغيرة (RB h في الشكل 2) بارتفاع يحتوي على جذر حيث أن شجرتيه الفرعيتين مختلفتين في الارتفاع. الشجرة الفرعية الأعلى هي كذلك شجرة RB دنيا، وتحتوي كذلك على أطول مسار يحدد ارتفاعها العقد والارتفاع الأسود الشجرة الفرعية الأخرى هي شجرة ثنائية مثالية ذات ارتفاع (أسود) وجود العقد السوداء - ولا يوجد عقدة حمراء. ثم عدد العقد عن طريق الاستقراء
};
#define DIRECTION(N) (N == N->parent->right ? RIGHT : LEFT)
علاوةً على ذلك، struct Node *rotate_subtree(struct Tree *tree, struct Node *sub, enum Dir dir) {
wait all proc1,proc2
وعلى صعيد آخر، تعقيد كل من الاتحاد والتقاطع والاختلاف هو لشجرتين حمراء وسوداء بأحجام و . يعد هذا التعقيد مثاليًا من حيث عدد المقارنات. الأمر الأكثر أهمية هو أنه نظرًا لأن المكالمات المتكررة إلى الاتحاد أو التقاطع أو الاختلاف مستقلة عن بعضها البعض، فيمكن تنفيذها بالتوازي مع . متى ، يتضمن التنفيذ القائم على الانضمام نفس الرسم البياني غير الدوري الموجه حسابيًا (DAG) مثل الإدراج والحذف لعنصر واحد إذا تم استخدام جذر الشجرة الأكبر لتقسيم الشجرة الأصغر.
return join(TL, t2.key, TR)
من جانب آخر، هنا، من المفترض أن يقوم الانقسام بإرجاع شجرتين: واحدة تحتوي على المفاتيح أقل من مفتاح الإدخال الخاص بها، والأخرى تحتوي على المفاتيح الأكبر. (الخوارزمية ، ولكن هناك كذلك نسخة مدمرة في مكانها.)
كذلك، تعتبر خوارزمية التقاطع أو الاختلاف مشابهة، ولكنها تتطلب روتين مساعد جوين2 الذي يشبه جوين ولكن بدون المفتاح الأوسط. بناءً على الوظائف الجديدة للاتحاد أو التقاطع أو الاختلاف، يمكن إدراج مفتاح واحد أو مفاتيح متعددة أو حذفها من الشجرة الحمراء والسوداء. نظرًا لأن Split يستدعي جوين ولكنه لا يتعامل مع معايير موازنة الأشجار الحمراء والسوداء بشكل مباشر، فإن مثل هذا التنفيذ يُطلق عليه عادةً اسم .
الخصائص
وفي هذا الصدد، مثلًا، كل شجرة ثنائية مثالية تتكون فقط من عقد سوداء هي شجرة حمراء-سوداء.
إضافةً إلى ذلك، يزعم بعض المؤلفين، مثل كورمن وآخرون، أن "الجذر أسود" كمتطلب خامس؛ ولكن ليس ميلهورن وساندرز أو سيدجويك وواين. نظرًا لأنه يمكن دائمًا تغيير الجذر من الأحمر إلى الأسود، فإن هذه القاعدة لها تأثير ضئيل على التحليل. تغفل هذه المقالة كذلك هذه النقطة، لأنها تزعج الخوارزميات التكرارية والإثباتات قليلاً.
في هذا الإطار، (الاستنتاج) إذا كان للعقدة N طفل واحد فقط، فيجب أن يكون الطفل باللون الأحمر. إذا كان الطفل أسود اللون، فإن أوراقه ستجلس على عمق أسود مختلف عن عقدة N' null (والتي تعتبر سوداء بحسب القاعدة 2)، مما ينتهك المتطلب 4.
علاوةً على ذلك، فضلًا عن المتطلبات المفروضة على شجرة البحث الثنائية، يجب استيفاء المتطلبات التالية بواسطة
- كل عقدة تكون إما حمراء أو سوداء.
- تعتبر جميع العقد الفارغة سوداء.
- العقدة الحمراء ليس لها طفل أحمر.
- كل مسار من عقدة معينة إلى أي من عقد أوراقها يمر عبر نفس عدد العقد السوداء.
وعلى صعيد آخر، لا تؤثر عمليات القراءة فقط، مثل البحث أو عبور الشجرة، على أي من المتطلبات. على النقيض من ذلك، فإن عمليات التعديل الإدراج والحذف تحافظ بسهولة على المتطلبات 1 و2، ولكن فيما يتعلق بالمتطلبات الأخرى يجب بذل بعض الجهد الإضافي، لتجنب إدخال انتهاك للمتطلب 3، والذي يسمى انتهاكًا أحمر، أو للمتطلب 4، والذي يسمى انتهاكًا أسود.
علاوةً على ذلك، تفرض المتطلبات خاصية أساسية للأشجار ذات اللونين الأحمر والأسود: المسار من الجذر إلى أبعد ورقة لا يزيد عن ضعف طول المسار من الجذر إلى أقرب ورقة. النتيجة هي أن الشجرة متوازنة الارتفاع. نظرًا لأن العمليات مثل الإدراج والحذف والبحث عن القيم تتطلب أسوأ وقت يتناسب مع الارتفاع من الشجرة، هذا الحد الأعلى للارتفاع يسمح للأشجار الحمراء والسوداء بأن تكون فعالة في أسوأ الحالات، أي في العدد من الإدخالات، أي (خاصية مشتركة بين جميع الأشجار المتوازنة ذاتيا، مثلًا، شجرة إيه في إل أو شجرة B، ولكن ليس أشجار البحث الثنائية العادية). للحصول على دليل رياضي، راجع قسم إثبات الحدود.
من جانب آخر، تسمح الأشجار الحمراء والسوداء، مثل جميع أشجار البحث الثنائية، بالوصول المتسلسل الفعال (مثلًا، التنقل بالترتيب، أي: بالترتيب من اليسار إلى الجذر إلى اليمين) لعناصرها. لكنها تدعم كذلك الوصول المباشر الأمثل على وجه التقريب عبر الانتقال من الجذر إلى الورقة، مما يؤدي إلى وقت البحث.
struct Node *sub_parent = sub->parent;
- 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;
ومن جهة أخرى، struct Node *new_root = sub->child[1 - dir]؛ // 1 - dir is the opposite direction
};
- struct Node *child[2]؛
- };
- enum Color color;
- int key;
- };
- struct Tree {
- struct Node *root;
/* symmetric */
في هذا الإطار، اتحاد شجرتين حمراوين و تمثلان المجموعتين و ، هو شجرة حمراوين تمثل تحسب الدالة التكرارية التالية هذا الاتحاد:
if t1 = NULL return t2
- 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)
function union(t1, t2):
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟