hotchpotch/wikipedia-multilingual-ir-pairs huggingface dataset:
شجرة حمراء وسوداء التنفيذ
يقوم الاقتراح بتقسيم كل من الإدراج والإزالة (ناهيك عن بعض الحالات البسيطة للغاية) إلى ستة مجموعات من العقد والحواف والألوان، والتي تسمى الحالات. يتضمن الاقتراح، لكل من الإدراج والإزالة، حالة واحدة فقط تعمل على تقدم مستوى أسود واحد أقرب إلى الجذر والحلقات، بينما تعمل الحالات الخمس الأخرى على إعادة توازن الشجرة الخاصة بها. يتم تصوير الحالات الأكثر تعقيدًا في الرسم التخطيطي.
يرمز إلى عقدة حمراء و عقدة سوداء (غير فارغة) (ارتفاعها أسود ≥ 1)، يرمز إلى اللون الأحمر أو الأسود لعقدة غير فارغة، ولكن نفس اللون في نفس الرسم البياني. لا يتم تمثيل العقد NULL في المخططات.
يحتوي الرسم التخطيطي على ثلاثة أعمدة واثنين إلى أربعة إجراءات. يُظهر العمود الأيسر التكرار الأول، ويُظهر العمود الأيمن التكرارات الأعلى، ويُظهر العمود الأوسط تقسيم الحالة إلى أفعالها المختلفة.
شجرة حمراء وسوداء التنفيذ
إذا كانت هناك حاجة إلى الإصلاح، فإن الحالات تستخدم كود الحالات الأخرى وهذا بعد إعادة تعيين العقدة الحالية N، والتي تحمل بدورها حلقة زرقاء والتي قد يتعين إعادة تعيين العقد الأخرى إليها أيضًا. يُسمى هذا الإجراء "إعادة التعيين". بالنسبة لكلا العمليتين، الإدراج والحذف، هناك حالة واحدة (بالضبط) تكرر مستوى أسود واحدًا أقرب إلى الجذر؛ ثم تلبي الكوكبة المعاد تعيينها الثوابت الحلقية المقابلة.
مثلث مرقم ربما به دائرة سوداء في الأعلى يمثل شجرة فرعية حمراء-سوداء (متصلة بوالدها وفقًا للمتطلب 3 ) بارتفاع أسود يساوي مستوى التكرار ناقص واحد، أي صفر في التكرار الأول. قد يكون جذره أحمر أو أسود.
مثلث مرقم ربما يمثل شجرة فرعية حمراء-سوداء ذات ارتفاع أسود أقل بمقدار واحد، أي أن الشجرة الأصلية لها ارتفاع أسود يساوي صفرًا في التكرار الثاني.
من أجل التبسيط، يستخدم الكود النموذجي الفصل :
U == NULL || U->color == BLACK // considered black
والعطف :
U ! = NULL && U->color == RED // not considered black
شجرة حمراء وسوداء التنفيذ
لذلك، يجب أن نضع في الاعتبار أن كلا البيانين لا يتم تقييمهما بشكل إجمالي، إذا كان U == NULL. ثم في كلتا الحالتين لا يتم المساس U->color (انظر تقييم الدائرة القصيرة ‏ ). (التعليق considered black يتوافق مع المتطلب 2. )
يجب أن تحدث عبارات if ذات الصلة بشكل أقل تكرارًا إذا تم تحقيق الاقتراح.
تبدأ عملية الإدراج بوضع العقدة الجديدة (غير NULL)، على سبيل المثال N، في الموضع في شجرة البحث الثنائية لعقدة NULL التي يكون مفتاح سابقتها بالترتيب أقل من مفتاح العقدة الجديدة، والتي بدورها تكون أقل من مفتاح خليفتها بالترتيب. (في كثير من الأحيان، يكون هذا التموضع نتيجة لعملية بحث داخل الشجرة تسبق عملية الإدراج مباشرةً وتتكون من عقدة P مع اتجاه dir مع P->child[dir] == NULL.) P->child[dir] == NULL.) يتم تلوين العقدة المدرجة حديثًا باللون الأحمر مؤقتًا حتى تحتوي جميع المسارات على نفس عدد العقد السوداء كما في السابق. ولكن إذا كان الوالد، على سبيل المثال P، أحمر أيضًا، فإن هذا الإجراء يؤدي إلى انتهاك اللون الأحمر.
تحتوي حلقة إعادة التوازن لعملية الإدراج على الثوابت التالية:
شجرة حمراء وسوداء التنفيذ
تظهر المخططات العقدة الأصلية P باعتبارها الطفل الأيسر للعقدة الأصلية G على الرغم من أنه من الممكن أن تكون P على أي من الجانبين. يغطي كود العينة كلا الاحتمالين عن طريق المتغير الجانبي dir.
مجموعة الأعمدة السابقة تحدد الحالة التي يتم إعطاء اسمها في حالة العمود. وبالتالي، سيتم تجاهل القيم المحتملة في الخلايا الفارغة. لذلك في الحالة I2، يغطي كود العينة كلا احتمالات الاتجاهات الفرعية لـ N، على الرغم من أن الرسم التخطيطي المقابل يظهر واحدًا فقط.
أ يشير تسجيل الدخول في العمود التالي إلى أن إعادة التوازن اكتملت بهذه الخطوة. إذا كان العمود بعد يحدد حالة واحدة فقط، فسيتم تقديم هذه الحالة باعتبارها الحالة اللاحقة، وإلا فسيتم وضع علامات استفهام.
شجرة حمراء وسوداء التنفيذ
في الحالة الثانية، تتفاقم مشكلة إعادة التوازن  مستويات الشجرة أو مستوى أسود واحد أعلى في الشجرة، بحيث يصبح الجد G هو العقدة الحالية الجديدة N. لذا يستغرق الأمر الحد الأقصى  خطوات التكرار لإصلاح الشجرة (حيث h هو ارتفاع الشجرة). نظرًا لأن احتمال التصعيد يتناقص بشكل كبير مع كل خطوة، فإن تكلفة إعادة التوازن الإجمالية تظل ثابتة في المتوسط، بل ثابتة عند الاستهلاك.
العقدة الأصلية P للعقدة الحالية هي سوداء، لذا فإن المتطلب 3 صحيح. ينطبق المتطلب رقم 4 أيضًا وفقًا لثابت الحلقة.
إذا كان كل من الوالد P والعم U باللون الأحمر، فيمكن إعادة طلاء كليهما باللون الأسود ويصبح الجد G باللون الأحمر للحفاظ على المتطلب 4. نظرًا لأن أي مسار عبر الوالد أو العم يجب أن يمر عبر الجد، فإن عدد العقد السوداء على هذه المسارات لم يتغير. ومع ذلك، قد ينتهك الجد G الآن الشرط 3، إذا كان لديه أحد الوالدين باللون الأحمر. بعد إعادة تسمية G إلى N، يتم استيفاء ثابت الحلقة بحيث يمكن تكرار إعادة التوازن على مستوى أسود واحد (= مستويين للشجرة) أعلى.
شجرة حمراء وسوداء التنفيذ
تم تنفيذ الحالة 2 لإدراج  مرات وزاد الارتفاع الإجمالي للشجرة بمقدار 1، حيث أصبح الآن h . العقدة الحالية N هي الجذر (الأحمر) للشجرة، وجميع خصائص RB مُرضية.
الأصل P أحمر والجذر. نظرًا لأن N أيضًا أحمر، يتم انتهاك المتطلب 3. ولكن بعد تبديل لون P تصبح الشجرة على شكل RB. يزداد ارتفاع الشجرة السوداء بمقدار 1.
الوالد P أحمر ولكن العم U أسود. الهدف النهائي هو تدوير العقدة الأصلية P إلى موضع الجد، ولكن هذا لن ينجح إذا كان N حفيدًا "داخليًا" لـ G (أي إذا كان N هو الطفل الأيسر للطفل الأيمن لـ G أو الطفل الأيمن للطفل الأيسر لـ G ). يؤدي dir-rotation عند P إلى تبديل أدوار العقدة الحالية N وعقدتها الأم P. يضيف الدوران مسارات عبر N (تلك الموجودة في الشجرة الفرعية المسماة 2، انظر الرسم التخطيطي) ويزيل المسارات عبر P (تلك الموجودة في الشجرة الفرعية المسماة 4 ). لكن كل من P و N أحمران، لذا يتم الحفاظ على المتطلب رقم 4. تم استعادة المتطلب 3 في الحالة 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.
الحالة المعقدة هي عندما لا يكون N هو الجذر، ملونًا باللون الأسود وليس له طفل مناسب (⇔ أطفال NULL فقط). في التكرار الأول، تم استبدال N بـ NULL.
تحتوي حلقة إعادة التوازن لعملية الحذف على الثابت التالي:
عدد العقد السوداء على المسارات عبر N أقل بواحدة مما كان عليه قبل الحذف، في حين أنه لم يتغير في جميع المسارات الأخرى، بحيث يكون هناك انتهاك للون الأسود عند P إذا كانت هناك مسارات أخرى موجودة.
العقدة الحالية N هي الجذر الجديد. تمت إزالة عقدة سوداء واحدة من كل مسار، لذلك يتم الحفاظ على خصائص RB. ينخفض ارتفاع الشجرة السوداء بمقدار 1.
شجرة حمراء وسوداء التنفيذ
أطفال P و S و S من السود. بعد طلاء S باللون الأحمر، فإن جميع المسارات التي تمر عبر S، والتي هي على وجه التحديد المسارات التي لا تمر عبر N، تحتوي على عقدة سوداء أقل. الآن تحتوي جميع المسارات في الشجرة الفرعية التي يتجذرها P على نفس عدد العقد السوداء، ولكن أقل بعقدة واحدة من المسارات التي لا تمر عبر P، لذلك لا يزال من الممكن انتهاك المتطلب 4. بعد إعادة تسمية P إلى N، يتم استيفاء ثابت الحلقة بحيث يمكن تكرار إعادة التوازن على مستوى أسود واحد (= مستوى شجرة واحد) أعلى.
الأخ S أحمر اللون، لذلك يجب على P وأبناء الأخ C و D أن يكونوا أسود اللون. يؤدي dir-rotation عند P إلى تحويل S إلى جد N. ثم بعد عكس ألوان P و S، فإن المسار عبر N لا يزال قصيرًا بعقدة سوداء واحدة. لكن N لديه الآن أحد الوالدين الأحمر P وبعد إعادة التعيين لديه شقيق أسود S، وبالتالي فإن التحولات في الحالات 4 أو 5 أو 6 قادرة على استعادة شكل RB.
أطفال الأخوين S و S هم من السود، ولكن P هو أحمر. لا يؤثر تبادل ألوان S و P على عدد العقد السوداء على المسارات التي تمر عبر S، ولكنه يضيف واحدًا إلى عدد العقد السوداء على المسارات التي تمر عبر N، مما يعوض العقدة السوداء المحذوفة على تلك المسارات.
الأخ S أسود اللون، والطفل المقرب لـ S C أحمر اللون، والطفل البعيد لـ S D أسود اللون. بعد (1-dir)-rotation في S، يصبح ابن الأخ C والد S وشقيق N الجديد. يتم تبادل ألوان S و C. لا تزال جميع المسارات تحتوي على نفس عدد العقد السوداء، ولكن الآن أصبح لدى N شقيق أسود يكون طفله البعيد أحمر، وبالتالي تكون الكوكبة مناسبة للحالة D6. لا يتأثر N ولا أصله P بهذا التحويل، وقد يكون P أحمر أو أسود ( في الرسم التخطيطي).
الأخ S أسود اللون، والطفل البعيد D أحمر اللون. بعد dir-rotation عند P، يصبح الأخ S هو والد الطفل البعيد D لـ P و S. يتم تبادل ألوان P و S، ويصبح D أسود. لا تزال الشجرة الفرعية بأكملها تحمل نفس اللون عند جذرها S، أي إما أحمر أو أسود ( في الرسم التخطيطي، والذي يشير إلى نفس اللون قبل وبعد التحويل. بهذه الطريقة يتم الحفاظ على المتطلب رقم 3. إن المسارات الموجودة في الشجرة الفرعية التي لا تمر عبر N (أي تمر عبر D والعقدة 3 في الرسم التخطيطي) تمر عبر نفس عدد العقد السوداء كما في السابق، ولكن N لديه الآن سلف أسود إضافي: إما أن P أصبح أسود، أو كان أسودًا وتمت إضافة S كجد أسود. وبالتالي، تمر المسارات التي تمر عبر N عبر عقدة سوداء إضافية، بحيث يتم استعادة المتطلب 4 وتصبح الشجرة الإجمالية على شكل RB.
نظرًا لأن الخوارزمية تقوم بتحويل المدخلات دون استخدام بنية بيانات مساعدة واستخدام كمية صغيرة فقط من مساحة التخزين الإضافية للمتغيرات المساعدة، فهي في مكانها.
شجرة حمراء وسوداء إثبات الحدود
العقد (  هي دالة الأرضية ) ولا يوجد شجرة حمراء-سوداء بهذا الارتفاع مع عدد أقل من العقد - وبالتالي فهي ضئيلة. ارتفاعه الأسود هو  (مع الجذر الأسود) أو للفردية  (ثم مع الجذر الأحمر) أيضا
لكي تحتوي شجرة حمراء-سوداء ذات ارتفاع معين على أقل عدد من العقد، يجب أن يكون لها مسار واحد فقط طويل يحتوي على أقصى عدد من العقد الحمراء، وذلك لتحقيق أقصى ارتفاع للشجرة مع أدنى ارتفاع للعقد السوداء. بالإضافة إلى هذا المسار، يجب أن تكون جميع العقد الأخرى سوداء. إذا أُزيلت عقدة من هذه الشجرة، فإنها إما تفقد ارتفاعها أو إحدى خصائص RB.
لكي تحتوي شجرة حمراء-سوداء ذات ارتفاع معين على عدد أدنى من العقد، يجب أن يكون لديها مسار واحد طويل مع أقصى عدد من العقد الحمراء، لتحقيق أقصى ارتفاع للشجرة مع أدنى ارتفاع للأسود. بالإضافة إلى هذا المسار، يجب أن تكون جميع العقد الأخرى باللون الأسود.:444 Proof sketch إذا تمت إزالة عقدة من هذه الشجرة فإنها تفقد ارتفاعها أو بعض خصائص RB.
شجرة حمراء وسوداء إثبات الحدود
شجرة ارتفاع RB  مع الجذر الأحمر هو الحد الأدنى. وهذا يتفق مع
شجرة RB صغيرة (RB h في الشكل 2) بارتفاع  يحتوي على جذر حيث أن شجرتيه الفرعيتين مختلفتين في الارتفاع. الشجرة الفرعية الأعلى هي أيضًا شجرة RB دنيا، RBh–1, وتحتوي أيضًا على أطول مسار يحدد ارتفاعها ;  العقد والارتفاع الأسود  الشجرة الفرعية الأخرى هي شجرة ثنائية مثالية ذات ارتفاع (أسود)  وجود  العقد السوداء - ولا يوجد عقدة حمراء. ثم عدد العقد عن طريق الاستقراء
رسم بياني للدالة  محدب ومقطع خطي ‏ مع نقاط توقف عند  أين  تمت جدولة الوظيفة على النحو التالي  A027383( h –1) لـ  (متسلسلة A027383 في OEIS).
عدم المساواة  يؤدي إلى ، والتي بالنسبة للأعداد الفردية  يؤدي إلى
لذا في كلتا الحالتين، الزوجية والفردية،  هو في الفاصل الزمني
شجرة حمراء سوداء اللون  العقد (المفاتيح) لها ارتفاع شجرة
شجرة حمراء وسوداء عمليات المجموعة والعمليات المجمعة
بالإضافة إلى عمليات الإدراج والحذف والبحث لعنصر واحد، تم تعريف العديد من عمليات المجموعة على red–black trees: الاتحاد والتقاطع وفرق المجموعة. ومن ثم يمكن تنفيذ عمليات سريعة مجمعة للإدراج أو الحذف استنادًا إلى هذه الوظائف المحددة. تعتمد عمليات المجموعة هذه على عمليتين مساعدتين، التقسيم والانضمام. بفضل العمليات الجديدة، يمكن أن يصبح تنفيذ الأشجار الحمراء والسوداء أكثر كفاءة وقابلية للتوازي بدرجة كبيرة. من أجل تحقيق تعقيدات الوقت، يتطلب هذا التنفيذ أن يُسمح للجذر بأن يكون أحمر أو أسود، وأن تخزن كل عقدة ارتفاعها الأسود الخاص بها.
الانضمام : تعمل دالة الانضمام على شجرتين t1 t2 مع مفتاح k، حيث t1 < k < t2، أي أن جميع المفاتيح t1 أصغر من k، وجميع المفاتيح t2 أكبر من k. تُرجع هذه الدالة شجرة تحتوي على جميع العناصر في t1 t2 وكذلك k.
إذا كان للشجرتين نفس الارتفاع الأسود، فإن جوين يقوم ببساطة بإنشاء عقدة جديدة مع شجرة فرعية يسارية t1 وجذر k وشجرة فرعية يمينية t2. إذا كان كل من t1 و t2 لهما جذر أسود، فاضبط k ليكون أحمر. وإلا فسيتم تعيين k باللون الأسود.
شجرة حمراء وسوداء عمليات المجموعة والعمليات المجمعة
إذا كانت ارتفاعات اللون الأسود غير متساوية، افترض أن ارتفاع اللون t1 أكبر من ارتفاع اللون t2 (الحالة الأخرى تكون متماثلة). ينضم العمود الفقري الأيمن لـ t1 حتى العقدة السوداء c، والتي تكون متوازنة مع t2. في هذه المرحلة، تُنشأ عقدة جديدة مع الابن الأيسر c، والجذر k (مُعَيَّن ليكون أحمر)، والابن الأيمن t2 لتحل محل c. قد تُبطل العقدة الجديدة ثابت الأحمر-الأسود، إذ لا يمكن ظهور أكثر من ثلاث عقد حمراء في صف واحد. يمكن إصلاح ذلك من خلال الدوران المزدوج. إذا انتشرت المشكلة الحمراء المزدوجة إلى الجذر، فسيتم بعد ذلك تعيين الجذر ليكون أسود، واستعادة الخصائص. تكلفة هذه الوظيفة هي الفرق بين ارتفاعات اللون الأسود بين شجرتي الإدخال.
إذا كان للشجرتين نفس الارتفاع الأسود، فإن جوين يقوم ببساطة بإنشاء عقدة جديدة مع شجرة فرعية يسارية t1 وجذر k وشجرة فرعية يمينية t2. إذا كان كل من t1 و t2 لهما جذر أسود، فاضبط k ليكون أحمر. وإلا فسيتم تعيين k باللون الأسود.
شجرة حمراء وسوداء عمليات المجموعة والعمليات المجمعة
إذا كانت ارتفاعات اللون الأسود غير متساوية، افترض أن ارتفاع اللون t1 أكبر من ارتفاع اللون t2 (الحالة الأخرى تكون متماثلة). ينضم العمود الفقري الأيمن لـ t1 حتى العقدة السوداء c، والتي تكون متوازنة مع t2. في هذه المرحلة، تُنشأ عقدة جديدة مع الابن الأيسر c، والجذر k (مُعَيَّن ليكون أحمر)، والابن الأيمن t2 لتحل محل c. قد تُبطل العقدة الجديدة ثابت الأحمر-الأسود، إذ لا يمكن ظهور أكثر من ثلاث عقد حمراء في صف واحد. يمكن إصلاح ذلك من خلال الدوران المزدوج. إذا انتشرت المشكلة الحمراء المزدوجة إلى الجذر، فسيتم بعد ذلك تعيين الجذر ليكون أسود، واستعادة الخصائص. تكلفة هذه الوظيفة هي الفرق بين ارتفاعات اللون الأسود بين شجرتي الإدخال.
شجرة حمراء وسوداء عمليات المجموعة والعمليات المجمعة
تقسيم : لتقسيم شجرة حمراء-سوداء إلى شجرتين أصغر، تلك الأصغر من المفتاح x، وتلك الأكبر من المفتاح x، ارسم أولاً مسارًا من الجذر عن طريق إدخال x في الشجرة الحمراء-السوداء. بعد هذا الإدراج، سيتم العثور على جميع القيم الأقل من x على يسار المسار، وسيتم العثور على جميع القيم الأكبر من x على اليمين. من خلال تطبيق جوين، يتم دمج جميع الأشجار الفرعية على الجانب الأيسر من الأسفل إلى الأعلى باستخدام المفاتيح الموجودة على المسار كعقد وسيطة من الأسفل إلى الأعلى لتشكيل الشجرة اليسرى، والجزء الأيمن متماثل.
بالنسبة لبعض التطبيقات، تقوم Split أيضًا بإرجاع قيمة منطقية تشير إلى ما إذا كان x يظهر في الشجرة. تكلفة الانقسام هي  ترتيب ارتفاع الشجرة. في الواقع، لا علاقة لهذه الخوارزمية بأي خصائص خاصة لشجرة حمراء-سوداء، ويمكن استخدامها على أي شجرة باستخدام عملية ربط، مثل شجرة إيه في إل.
اتحاد شجرتين حمراوين t1 و t2 تمثلان المجموعتين A و B، هو شجرة حمراوين t تمثل A ∪ B تحسب الدالة التكرارية التالية هذا الاتحاد:
شجرة حمراء وسوداء عمليات المجموعة والعمليات المجمعة
هنا، من المفترض أن يقوم الانقسام بإرجاع شجرتين: واحدة تحتوي على المفاتيح أقل من مفتاح الإدخال الخاص بها، والأخرى تحتوي على المفاتيح الأكبر. (الخوارزمية غير مدمرة ‏، ولكن هناك أيضًا نسخة مدمرة في مكانها.)
تعتبر خوارزمية التقاطع أو الاختلاف مشابهة، ولكنها تتطلب روتين مساعد جوين2 الذي يشبه جوين ولكن بدون المفتاح الأوسط. بناءً على الوظائف الجديدة للاتحاد أو التقاطع أو الاختلاف، يمكن إدراج مفتاح واحد أو مفاتيح متعددة أو حذفها من الشجرة الحمراء والسوداء. نظرًا لأن Split يستدعي جوين ولكنه لا يتعامل مع معايير موازنة الأشجار الحمراء والسوداء بشكل مباشر، فإن مثل هذا التنفيذ يُطلق عليه عادةً اسم خوارزميات الشجرة القائمة على الانضمام ‏.
تعقيد كل من الاتحاد والتقاطع والاختلاف هو  لشجرتين حمراء وسوداء بأحجام  و . يعد هذا التعقيد مثاليًا من حيث عدد المقارنات. الأمر الأكثر أهمية هو أنه نظرًا لأن المكالمات المتكررة إلى الاتحاد أو التقاطع أو الاختلاف مستقلة عن بعضها البعض، فيمكن تنفيذها بالتوازي مع عمق متوازي ‏ . متى ، يتضمن التنفيذ القائم على الانضمام نفس الرسم البياني غير الدوري الموجه حسابيًا (DAG) مثل الإدراج والحذف لعنصر واحد إذا تم استخدام جذر الشجرة الأكبر لتقسيم الشجرة الأصغر.
شجرة حمراء وسوداء الخوارزميات المتوازية
يمكن تشغيل الخوارزميات المتوازية لبناء أشجار حمراء وسوداء من قوائم مرتبة من العناصر في وقت ثابت أو  الوقت، اعتمادًا على طراز الكمبيوتر، إذا كان عدد المعالجات المتاحة متناسبًا بشكل مقارب مع عدد  من العناصر حيث . ومن المعروف أيضًا أن خوارزميات البحث السريع والإدراج والحذف المتوازية معروفة أيضًا.
تُعد الخوارزميات القائمة على الانضمام ‏ للأشجار الحمراء والسوداء متوازية للعمليات الشاملة، بما في ذلك الاتحاد، والتقاطع، والإنشاء، والتصفية، والاختزال بالخريطة، وما إلى ذلك.
يمكن تنفيذ عمليات أساسية، مثل الإدراج والإزالة والتحديث، بالتوازي من خلال تحديد عمليات لمعالجة كميات كبيرة من عناصر متعددة. كما يمكن معالجة كميات كبيرة من خلال عدة عمليات أساسية، على سبيل المثال، قد تحتوي الكميات الكبيرة على عناصر لإدراجها وعناصر لإزالتها من الشجرة.
شجرة حمراء وسوداء الخوارزميات المتوازية
لا تنطبق الخوارزميات الخاصة بالعمليات المجمعة على الشجرة الحمراء والسوداء فحسب، بل يمكن تكييفها مع هياكل بيانات متسلسلة مرتبة أخرى أيضًا، مثل شجرة 2–3 ‏، وشجرة 2–3–4 ‏، وشجرة (أ، ب). سيتم شرح الخوارزميات المختلفة للإدراج بالجملة فيما يلي، ولكن يمكن أيضًا تطبيق نفس الخوارزميات للإزالة والتحديث. الإدراج المجمع هو عملية تقوم بإدراج كل عنصر من التسلسل  في شجرة .
يمكن تطبيق هذا النهج على كل بنية بيانات تسلسلية مرتبة تدعم عمليات الانضمام والتقسيم الفعالة. الفكرة العامة هي تقسيم I و T إلى أجزاء متعددة وإجراء الإدخالات على هذه الأجزاء بالتوازي.
لاحظ أنه في الخطوة 3، القيود المفروضة على التقسيم أؤكد أنه في الخطوة 5، يمكن ضم الأشجار مرة أخرى وفرز التسلسل الناتج.
يُظهر الكود الزائف تنفيذًا بسيطًا لتقسيم وغزو لخوارزمية تعتمد على الانضمام للإدراج بالجملة. يمكن تنفيذ كلا النداءين المتكررين بالتوازي. تختلف عملية الانضمام المستخدمة هنا عن الإصدار الموضح في هذه المقالة، حيث يتم استخدام join2 بدلاً من ذلك، والذي يفتقد المعلمة الثانية k.
لم يتم أخذ الفرز I في الاعتبار في هذا التحليل.
شجرة حمراء وسوداء الخوارزميات المتوازية
يمكن تحسين ذلك باستخدام خوارزميات متوازية للتقسيم والانضمام. في هذه الحالة يكون وقت التنفيذ هو .
هناك طريقة أخرى لتنفيذ العمليات المجمعة بالتوازي وهي استخدام نهج الأنابيب. يمكن القيام بذلك عن طريق تقسيم مهمة معالجة عملية أساسية إلى سلسلة من المهام الفرعية. بالنسبة للعمليات الأساسية المتعددة، يمكن معالجة المهام الفرعية بالتوازي عن طريق تعيين كل مهمة فرعية إلى معالج منفصل.
لكل عنصر في I، تحدد الخوارزمية موضع الإدراج المقابل في T. يمكن إجراء ذلك بالتوازي لكل عنصر  لأن T لن يتعرض للطفرات في هذه العملية. الآن، يجب تقسيم I إلى متتاليات فرعية S وفقًا لموضع إدراج كل عنصر. على سبيل المثال،  هي المتتالية الفرعية لـI التي تحتوي على العناصر التي يكون موضع إدراجها على يسار العقدة n.
سيتم إدراج العنصر الأوسط  من كل متتالية فرعية  في T كعقدة جديدة . يمكن إجراء ذلك بالتوازي لكل  حيث أن موضع إدراج كل  فريد، بحكم التعريف. إذا احتوى  على عناصر على يسار أو يمين ، فسيتم تضمينها في مجموعة جديدة من المتتاليات الفرعية S مثل  أو .
شجرة حمراء وسوداء الخوارزميات المتوازية
من المحتمل أن تحتوي T على عقدتين حمراوين متتاليتين في نهاية المسارات من الجذر إلى الأوراق، والتي تحتاج إلى إصلاح. لاحظ أنه أثناء الإصلاح  يجب تحديث موضع إدراج العناصر 𝑆، إذا تأثرت العقد المقابلة بالدوران.
إذا كان لعقدتين أسلاف سوداء أقرب مختلفة، فيمكن إصلاحهما بالتوازي. وبما أنه لا يمكن أن يكون لأربع عقد على الأكثر نفس السلف الأسود الأقرب، فيمكن إصلاح العقد في المستوى الأدنى بعدد ثابت من الخطوات المتوازية.
سيتم تطبيق هذه الخطوة بالتتابع على مستويات السواد أعلاه حتى يتم إصلاح T بالكامل.
تُكرر الخطوات من 3 إلى 5 على المتتاليات الجزئية الجديدة حتى تصبح S فارغة. عند هذه النقطة، يكون كل عنصر  قد أُضيف. يُسمى كل تطبيق لهذه الخطوات مرحلة. بما أن طول المتتاليات الجزئية في S هو  وفي كل مرحلة تُقسّم المتتاليات الجزئية إلى النصف، فإن عدد المراحل هو .
بما أن جميع المراحل تتحرك صعودًا عبر مستويات الظلام في الشجرة، فيمكن ربطها بالتوازي في خط أنابيب. بمجرد انتهاء كل مرحلة من معالجة مستوى أسود واحد، تتمكن المرحلة التالية من التحرك صعودًا والاستمرار على هذا المستوى.
لم يتم أخذ الفرز I في الاعتبار في هذا التحليل. أيضًا،  من المفترض أن يكون أصغر من  وإلا فسيكون من الأكثر كفاءة إنشاء الشجرة الناتجة من الصفر.
خوارزمية غروفر
خوارزمية غروفر ويُطلق عليها أيضًا خوارزمية البحث الكمومي، هي خوارزمية كمومية ابتكرها عالم الحاسوب الأمريكي من أصل هندي لوف غروفر عام 1996، وتُستخدم في الحوسبة الكمومية للبحث غير المنظم، إذ يُمكنها أن تُحدد باحتمالية عالية المدخلات الفريدة لدالة الصندوق الأسود التي تُنتج قيمة مخرجات محددة، باستخدام تقييمات  للدالة فقط، حيث 𝑁 هو حجم مجال الدالة. تتسم المسألة المماثلة في الحوسبة الكلاسيكية بتعقيد استعلام مقداره 𝑂 (𝑁) (أي أنه يجب تقييم الدالة لعدد 𝑂 (𝑁) مرات) لا يوجد نهج أفضل من تجربة جميع قيم المدخلات واحدة تلو الأخرى، وهو ما يستغرق في المتوسط ما يساوي 𝑁/2 من الخطوات.
خوارزمية غروفر
أثبت علماء الحاسوب تشارلز هـ. بينيت، وإيثان بيرنشتاين، وجيليس براسارد، وأوميش فازيراني أن أي حل كمي للمسألة يحتاج إلى تقييم الدالة لعدد  من المرات، لذا تُعدّ خوارزمية غروفر مثاليةً تقريبيًا. بما أن الخوارزميات الكلاسيكية للمسائل الكاملة ذات العدد غير المتماثل تتطلب خطواتٍ أُسية، ولأن خوارزمية غروفر تُوفّر تسريعًا تربيعيًا على الأكثر مقارنةً بالحل الكلاسيكي للبحث غير المنظم، فإن هذا يُشير إلى أن خوارزمية غروفر وحدها لن تُوفّر حلولًا في زمن كثير الحدود للمسائل الكاملة ذات العدد غير المتماثل (حيث إن الجذر التربيعي للدالة الأسية لا يزال دالة أُسية، وليس دالة كثيرة الحدود).
على عكس الخوارزميات الكمومية الأخرى، والتي قد تُوفّر تسريعًا أُسيًا مقارنةً بنظيراتها الكلاسيكية، فإن خوارزمية غروفر تُوفّر تسريعًا تربيعيًا فقط. ومع ذلك، فحتى التسريع التربيعي يكون ملحوظًا عندما تكون قيمة 𝑁 كبيرة، ويمكن تطبيق خوارزمية غروفر لتسريع فئات واسعة من الخوارزميات. في هجمات البحث الشامل، تستطيع خوارزمية غروفر التوصل إلى مفتاح تشفير متماثل بطول 128 بت بعد حوالي 264 تكرارًا، ويُمكنها اكتشاف مفتاح تشفير بطول 256 بت بعد حوالي 2128 تكرارًا. وعلى الرغم من ذلك، فإن خوارزمية غروفر قد لا تُشكل خطرًا متزايدًا بشكل ملحوظ على التشفير مقارنةً بالخوارزميات الكلاسيكية الحالية.
أنتيغون (مسرحية)
أنتيغون (بالفرنسية: Antigone) هي مسرحية من فصل واحد كتبها جان أنوي، وعُرضت لأول مرة في مسرح الأتولييه بباريس في 6 فبراير 1944، خلال فترة الاحتلال الألماني، بإخراج وتصميم ديكور وأزياء من إعداد أندريه بارساك.
تُعد إعادة صياغة لمسرحية سوفوكليس التي تحمل نفس الاسم، وهي جزء من سلسلة المسرحيات السوداء الجديدة، إلى جانب جيزابيل (1932)، روميو وجانيت (1946)، وميديا (1953).
أنتيغون (مسرحية) الحبكة
أنتيغون هي ابنة أوديب وجوكاست (زوجة وأم أوديب)، اللذين كانا حاكمين مدينة طيبة. بعد انتحار جوكاست ونفي أوديب، قتل شقيقا أنتيغون، إتيوقل وبولينيس، بعضهما البعض في صراع على عرش طيبة. كريون، شقيق جوكاست، أصبح الملك الجديد بسبب ذلك، وقرر أن يدفن فقط إتيوقل دون بولينيس، الذي وصفه بالمتمرد والخائن وأصدر مرسومًا يحذر فيه أن من يجرؤ على دفن جثة الخائن سيُعاقب بالإعدام. لم يجرؤ أحد على تحدي هذا المنع، فترك جسد بولينيس معرضًا لأشعة الشمس والنسور.
الوحيدة التي ترفض هذا الوضع هي أنتيغون. رغم منع عمها كريون، تذهب عدة مرات إلى جثة أخيها وتحاول تغطيتها بالتراب. أما أسمين، أختها، فلا تريد مرافقتها لأنها تخاف من كريون ومن الموت..
أنتيغون (مسرحية) الحبكة
تُضبط أنتيغون متلبسة من طرف حراس الملك. ويُضطر كريون إلى تنفيذ حكم الإعدام بحقها. وبعد نقاش طويل بينها وبين عمها حول معنى الوجود، يُحكم عليها بأن تُدفن حيّة. لكن، وقبل أن يُغلق القبر، يعلم كريون أن ابنه ايمون، خطيب أنتيغون، قد حبس نفسه داخل القبر إلى جانب من يحب. وعندما يُعاد فتح القبر، يجدون أنتيغون قد شنقت نفسها بحزامها، وايمون، بعد أن بصق في وجه أبيه، طعن نفسه بسيفه في بطنه. وبسبب اليأس من فقدان ابنها الذي كانت تعشقه، تقوم أوريديس، زوجة كريون، بذبح نفسها من عنقها.
أنتيغون (مسرحية) الكتابة والإنتاج
كتب جان أنوي المسرحية بين عامي 1941 و1942، وبحسب كلماته: «على ضوء أولى العمليات الإرهابية، ولكن بالأخص كتنويع انطلاقًا من رائعة سوفوكليس، حول السلطة والتمرّد» . أحد الأحداث البارزة التي أثّرت في كتابة المسرحية هو محاولة الاغتيال الفاشلة التي استهدفت بيير لافال ومارسيل ديات** على يد المقاوم بول كوليت يوم 27 أغسطس 1941. ويبدو أن هذا الفعل، الذي اعتُبر التزامًا محكومًا عليه بالفشل، كان له تأثير كبير في تشكيل شخصية أنتيغون في المسرحية .
كما يوضح في مقدمة الطبعة الأولى، كان أنوي، الذي أُعجب بمسرحية سوفوكليس منذ مراهقته ، يرى خلال فترة الحرب أن مواضيعها — أي الفرد الذي ينهض في وجه قوى تفوقه — تكتسب دلالة جديدة. فعلى عكس الكاتب الكلاسيكي الذي صوّر صراع البشر مع الآلهة والمصير، قام أنوي بإضفاء الطابع الإنساني على المعركة الخاسرة التي يخوضها أبطاله، إذ إن القوى المتواجدة في مسرحيته ليست إلا بشرية: النفاق، الأنانية، والكبرياء .
أنتيغون (مسرحية) الكتابة والإنتاج
بعد موافقة الإدارة الألمانية على الرقابة ، عُرضت المسرحية لأول مرة يوم 4 فبراير 1944 على خشبة مسرح الأتولييه (Théâtre de l’Atelier) بإخراج أندريه بارساك. كان بارساك صديقًا للمؤلف، وقد أخرج عدة أعمال له، مثل حفلة اللصوص (Le Bal des voleurs, سنة 1938)، وموعد سانليس (Le Rendez-vous de Senlis, سنة 1941)، وأوريديس (Eurydice, سنة 1941). كما قام بارساك أيضًا بتصميم الديكورات والأزياء، التي جاءت حديثة الطابع عمدًا : فالملك كريون تخلى عن الطوغا (الرداء الإغريقي التقليدي) وارتدى سترة رسمية (فرَاك)، أما أنتيغون وإسمين، فارتدتا فساتين بسيطة، أنتيغون باللون الأسود، وإسمين بالأبيض، بينما كان الحراس يرتدون معاطف مطرية سوداء طويلة، تشبه تلك التي كان يرتديها أفراد الميليشيا أو الغيستابو (الشرطة السرية النازية) .