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

شجرة حمراء-سوداء
شجرة حمراء-سوداء
يكتب	شجرة
اخترع	1978
تم اختراعه بواسطة	ليونيداس جيه. جيباس وروبرت سيدجويك
التعقيدات في تدوين O الكبير
فضاء
تعقيد الفضاء
فضاء
تعقيد الوقت
وظيفة
يبحث
إدراج
يمسح

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

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

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

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

تاريخ

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

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

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

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

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

مصطلحات

مثال على شجرة حمراء-سوداء

شجرة الأحمر والأسود هي نوع خاص من شجرة البحث الثنائية ، تستخدم في علوم الكمبيوتر لتنظيم قطع البيانات القابلة للمقارنة ، مثل شظايا النص أو الأرقام (مثل الأرقام في الشكلين 1 و2). غالبًا ما تسمى العقد التي تحمل المفاتيح و/أو البيانات "عقدًا داخلية" ، ولكن لجعل هذا الأمر محددًا للغاية، تُسمى أيضًا عقدًا غير فارغة في هذه المقالة.

لا تحتوي عقد الأوراق في الأشجار الحمراء والسوداء ( NIL في الشكل 1) على مفاتيح أو بيانات. ولا يلزم أن تكون هذه "الأوراق" أفرادًا صريحين في ذاكرة الكمبيوتر: يمكن لمؤشر NULL - كما هو الحال في جميع هياكل بيانات الشجرة الثنائية - ترميز حقيقة عدم وجود عقدة فرعية في هذا الموضع في العقدة (الأصلية). ومع ذلك، فبموجب موضعها في الشجرة، تكون هذه الكائنات فيما يتعلق بالعقد الأخرى ذات صلة بهيكل RB، فقد يكون لها عقدة أبوية أو شقيقة (أي الطفل الآخر للوالد) أو عم أو حتى ابن أخ؛ وقد تكون طفلة - ولكن ليس أبوية أبدًا - لعقدة أخرى. ليس من الضروري حقًا أن ننسب "لونًا" إلى كائنات نهاية المسار هذه، لأن الشرط "is أو " مستتر من الشرط "is " (انظر أيضًا هذه الملاحظة). NILBLACKNIL

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

بدلاً من ذلك، لتوفير قدر ضئيل من وقت التنفيذ، قد يتم تنفيذ هذه الأوراق NIL (ربما العديد منها) كمؤشرات إلى عقدة حارسة فريدة (وسوداء) (بدلاً من مؤشرات القيمة NULL ).

وكخلاصة، يمكن تحديد حقيقة عدم وجود طفل (ليس عقدة حقيقية، ولا يحتوي على بيانات) في جميع الحالات من خلال نفس مؤشر NULL أو كمؤشر واحد لعقدة مراقبة. في جميع أنحاء هذه المقالة، يُطلق على أي من الخيارين اسم عقدة NIL وله القيمة الثابتة NIL .

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

ملكيات

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

كل عقدة تكون إما حمراء أو سوداء.
تعتبر جميع العقد NIL (الشكل 1) سوداء.
العقدة الحمراء ليس لها طفل أحمر.
كل مسار من عقدة معينة إلى أي من العقد NIL التابعة لها يمر عبر نفس عدد العقد السوداء.
(الاستنتاج) إذا كانت العقدة N لديها طفل واحد فقط، فيجب أن يكون الطفل أحمر، لأنه إذا كان أسودًا، فإن أحفاده NIL سيجلسون على عمق أسود مختلف عن طفل NIL الخاص بـ N ، مما ينتهك المتطلب 4.

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

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

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

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

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

تشبيه بالأشجار 2-3-4

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

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

التطبيقات وهياكل البيانات ذات الصلة

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

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

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

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

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

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

العمليات

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

إذا لم يكن تنفيذ المثال أدناه مناسبًا، فيمكن العثور على تنفيذات أخرى مع توضيحات في مكتبة C الموضحة GNU libavl (الإصدار 2.0.3 اعتبارًا من يونيو 2019) الخاصة بـ Ben Pfaff ^{[29] .}

سيتم توضيح تفاصيل عمليات الإدراج والإزالة باستخدام كود C++ كمثال ، والذي يستخدم تعريفات النوع، والماكرو أدناه، ووظيفة المساعدة للتدوير:

//تعريفات النوع الأساسية:

enum color_t { أسود ، أحمر }؛     

struct RBnode { // عقدة شجرة حمراء-سوداء RBnode * الأصل ؛ // == لا شيء إذا كان جذر الشجرة RBnode * الطفل [ 2 ]؛ // == لا شيء إذا كان الطفل فارغًا // الفهرس هو: // LEFT := 0، إذا (المفتاح <المفتاح الأساسي) // RIGHT := 1، إذا (المفتاح > المفتاح الأساسي) enum color_t color ؛ int key ؛ };       
      
    
    
    
    
    
   


#define NIL NULL // مؤشر فارغ أو مؤشر إلى عقدة المراقبة 
#define LEFT 0 
#define RIGHT 1 
#define left child[LEFT] 
#define right child[RIGHT]

struct RBtree { // شجرة حمراء-سوداء RBnode * root ; // == NIL إذا كانت الشجرة فارغة };   
    


// احصل على اتجاه الطفل (∈ { LEFT, RIGHT }) 
// لعقدة RBnode غير الجذرية غير الصفرية* N: 
#define childDir(N) ( N == (N->parent)->right ? RIGHT : LEFT )

RBnode * RotateDirRoot ( RBtree * T ، // شجرة حمراء-سوداء RBnode * P ، // جذر الشجرة الفرعية ( قد يكون جذر T ) int dir ) { // dir ∈ { LEFT, RIGHT } RBnode * G = P -> parent ؛ RBnode * S = P -> child [ 1 - dir ] ؛ RBnode * C ؛ assert ( S != NIL )؛ // مطلوب مؤشر إلى العقدة الصحيحة C = S -> child [ dir ]؛ P -> child [ 1 - dir ] = C ؛ if ( C != NIL ) C -> parent = P ؛ S -> child [ dir ] = P ؛ P -> parent = S ؛ S -> parent = G ؛ if ( G != NULL ) G -> child [ P == G -> right ? RIGHT : LEFT ] = S ؛ else T -> root = S ؛ العودة S ; // جذر جديد للشجرة الفرعية } 
        
                 
         
     
     
   
     
    
           
         
    
     
              
  
      
    


#تعريف RotateDir(N,dir) RotateDirRoot(T,N,dir) 
#تعريف RotateLeft(N) RotateDirRoot(T,N,LEFT) 
#تعريف RotateRight(N) RotateDirRoot(T,N,RIGHT)

ملاحظات حول الكود النموذجي ومخططات الإدراج والإزالة

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

يرمز إلى عقدة حمراء وعقدة سوداء (غير صفرية) (ارتفاع أسود ≥ 1)،يرمز إلى اللون الأحمر أو الأسود لعقدة غير فارغة، ولكن نفس اللون في نفس الرسم البياني. لا يتم تمثيل العقد الفارغة في الرسوم البيانية.
يشير المتغير N إلى العقدة الحالية، والتي يتم تسميتها بـ N أو N في المخططات.
يحتوي الرسم التخطيطي على ثلاثة أعمدة واثنين إلى أربعة إجراءات. يوضح العمود الأيسر التكرار الأول، والعمود الأيمن التكرارات الأعلى، ويوضح العمود الأوسط تقسيم الحالة إلى إجراءاتها المختلفة. ^[30]

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

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

ملاحظة

من أجل التبسيط، يستخدم كود العينة الفصل :

U == NIL || U->color == BLACK // considered black

والعطف :

U != NIL && U->color == RED // not considered black

وعليه، يجب أن نضع في الاعتبار أن كلا البيانين لا يتم تقييمهما بشكل إجمالي، إذا كان U == NIL. ففي كلتا الحالتين U->colorلا يتم المساس بهما (انظر تقييم الدائرة القصيرة ).
(التعليق considered blackيتوافق مع المتطلب 2.)

يجب أن تحدث العبارات ذات الصلة بشكل أقل بكثير إذا تم تحقيق ifالاقتراح ^{[30] .}

إدراج

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

void RBinsert1 ( RBtree * T ، // -> شجرة حمراء وسوداء struct RBnode * N ، // -> العقدة التي سيتم إدراجها struct RBnode * P ، // -> العقدة الأصلية لـ N (قد تكون NULL) int dir ) // الجانب (الأيسر أو الأيمن) من P حيث سيتم إدراج N { struct RBnode * G ؛ // -> العقدة الأصلية لـ P struct RBnode * U ؛ // -> عم N 
            
      
      
              

      
      

  N -> color = RED ; N -> left = NIL ; N -> right = NIL ; N -> parent = P ; if ( P == NULL ) { // لا يوجد أصل T -> root = N ; // N هو الجذر الجديد للشجرة T. return ; // الإدراج مكتمل } P -> child [ dir ] = N ; // أدخل N كـ dir-child لـ P // بداية حلقة (do while): do {

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

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

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

قبل				قضية	الدوران	تكليف	بعد				التالي	Δح
ص	ج	و	س	قضية	الدوران	تكليف	ص	ج	و	س	التالي	Δح
				11							✓
				اي2		ن := ج	؟				؟	2
—				اي3							✓
	—			14							✓
			أنا	15	ص ↶ ن	ن := ص				ا	16	0
			ا	16	ص ↷ ج						✓
الإدراج: يوضح هذا الملخص في الأعمدة السابقة ، أنه تم تغطية جميع الحالات المحتملة ^[32] للأبراج.

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

أدخل الحالة I1

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

    إذا ( P -> color == BLACK ) { // Case_I1 (P black): return ; // الإدراج مكتمل } // من الآن فصاعدًا، يكون P أحمر. إذا (( G = P -> parent ) == NULL ) انتقل إلى Case_I4 ; // P أحمر وجذر // وإلا: P أحمر و G!=NULL. dir = childDir ( P ); // جانب الأصل G الذي توجد عليه العقدة P U = G -> child [ 1 - dir ]; // عم إذا ( U == NIL || U -> color == BLACK ) // يعتبر أسودًا انتقل إلى Case_I56 ; // P أحمر و U أسود

أدخل الحالة I2

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

    // Case_I2 (P+U أحمر): 
P -> اللون = أسود ؛ U -> اللون = أسود ؛ G -> اللون = أحمر ؛ N = G ؛ // عقدة حالية جديدة // تكرار مستوى أسود واحد أعلى // (= مستويان من الشجرة) } while (( P = N -> parent ) != NULL ); // نهاية حلقة (do while)-

أدخل الحالة I3

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

  // ترك حلقة (do while) (بعد السقوط من Case_I2). 
// Case_I3: N هو الجذر والأحمر. return ; // تم الإدراج

أدخل الحالة I4

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

Case_I4 : // P هو الجذر والأحمر: P -> color = BLACK ; return ; // الإدراج مكتمل

أدخل الحالة I5

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

Case_I56 : // P red && U black: if ( N == P -> child [ 1 - dir ]) { // Case_I5 (P red && U black && N inner grandchild of G): RotateDir ( P , dir ); // P ليس الجذر أبدًا N = P ; // العقدة الحالية الجديدة P = G -> child [ dir ]; // الأصل الجديد لـ N // السقوط إلى Case_I6 }

أدخل الحالة I6

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

  // Case_I6 (P red && U black && N external grandchild of G): 
RotateDirRoot ( T , G , 1 - dir ); // G قد يكون الجذر P -> color = BLACK ; G -> color = RED ; return ; // الإدراج مكتمل } // نهاية RBinsert1

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

إزالة

حالات بسيطة

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

- عندما يكون للعقدة المحذوفة طفل واحد فقط (غير فارغ). في هذه الحالة، ما عليك سوى استبدال العقدة بطفلها، وتلوينها باللون الأسود.
يجب أن يكون الطفل الوحيد (غير فارغ) باللون الأحمر وفقًا للاستنتاج 5، ويجب أن تكون العقدة المحذوفة باللون الأسود وفقًا للمتطلب 3.

- عندما لا تحتوي العقدة المحذوفة على أبناء (كلاهما NIL) وتكون هي الجذر، استبدلها بـ NIL. الشجرة فارغة.

- عندما لا تحتوي العقدة المحذوفة على أبناء (كلاهما NIL)، وتكون باللون الأحمر ، قم ببساطة بإزالة عقدة الورقة.

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

إزالة ورقة سوداء غير جذرية

الحالة المعقدة هي عندما لا يكون N هو الجذر، ويكون ملونًا باللون الأسود وليس له أي طفل مناسب (⇔ أطفال NIL فقط). في التكرار الأول، يتم استبدال N بـ NIL.

void RBdelete2 ( RBtree * T , // -> شجرة حمراء-سوداء struct RBnode * N ) // -> العقدة المراد حذفها { struct RBnode * P = N -> الأصل ; // -> العقدة الأصلية لـ N بايت dir ; // جانب P الذي يقع عليه N (∈ { LEFT, RIGHT }) struct RBnode * S ; // -> شقيق لـ N struct RBnode * C ; // -> ابن أخ قريب struct RBnode * D ; // -> ابن أخ بعيد 
            
      
 
        
             
      
      
      

  // P != NULL، لأن N ليس الجذر. 
dir = childDir ( N ); // جانب الأصل P الذي توجد عليه العقدة N // استبدل N في الأصل P بـ NIL: P -> child [ dir ] = NIL ; goto Start_D ; // انتقل إلى الحلقة     
  
    
         

  // بداية حلقة (do while): 
do { dir = childDir ( N ); // جانب الأصل P الذي توجد عليه العقدة N Start_D : S = P -> child [ 1 - dir ]; // شقيق N (ارتفاعه أسود >= 1) D = S -> child [ 1 - dir ]; // ابن أخ بعيد C = S -> child [ dir ]; // ابن أخ قريب if ( S -> color == RED ) go to Case_D3 ; // S red ===> P+C+D black // S is black: if ( D != NIL && D -> color == RED ) // لا يعتبر أسود go to Case_D6 ; // D red && S black if ( C != NIL && C -> color == RED ) // لا يعتبر أسود go to Case_D5 ; // C أحمر وS+D أسود // هنا يكون كلا ابني الأخ == NIL (التكرار الأول) أو أسود (لاحقًا). إذا ( P -> اللون == RED ) انتقل إلى Case_D4 ؛ // P أحمر وC+S+D أسود

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

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

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

قبل				قضية	الدوران	تكليف	بعد				التالي	Δح
ص	ج	س	د	قضية	الدوران	تكليف	ص	ج	س	د	التالي	Δح
—				د1							✓
				د2		ن := ص	؟				؟	1
				د3	ص ↶ س	ن := ن					د6	0
											د5	0
											د4	0
				د4							✓
				د5	ج ↷ س	ن := ن					د6	0
				د6	ص ↶ س						✓
الحذف: يوضح هذا الملخص في الأعمدة السابقة ، أنه تم تغطية جميع الحالات المحتملة ^[32] لمجموعات الألوان.

في المخططات أدناه، يتم استخدام P لوالد N ، و S لشقيق N ، وC (بمعنى ابن الأخ المقرب ) لطفل S في نفس اتجاه N ، و D (بمعنى ابن الأخ البعيد ) لطفل S الآخر ( لا يمكن أن تكون S عقدة NIL في التكرار الأول، لأنه يجب أن يكون ارتفاعها الأسود واحدًا، وهو ارتفاع N الأسود قبل حذفها، ولكن C و D قد تكونان عقدتين NIL).
تُظهر المخططات العقدة الحالية N باعتبارها الابنة اليسرى لوالدها P على الرغم من أنه من الممكن أن تكون N على أي من الجانبين. تغطي عينات التعليمات البرمجية كلا الاحتمالين عن طريق المتغير side dir.
في بداية (في التكرار الأول) الإزالة، تكون N هي العقدة NIL التي تحل محل العقدة المراد حذفها. ولأن موقعها في العقدة الأصلية هو الشيء الوحيد المهم، يتم ترميزها بواسطة(المعنى: العقدة الحالية N هي عقدة NIL وطفل أيسر) في العمود الأيسر من مخططات الحذف. مع استمرار العملية، قد تصبح العقد المناسبة (ذات الارتفاع الأسود ≥ 1) حالية (انظر على سبيل المثال الحالة D2).
من خلال عد الرصاصات السوداء (و) في مخطط الحذف، يمكن ملاحظة أن المسارات عبر N بها رصاصة واحدة أقل من المسارات الأخرى. وهذا يعني وجود انتهاك للون الأسود عند P —إذا كان موجودًا.
تحدد مجموعة الألوان الموجودة في مجموعة الأعمدة قبل الحالة، والتي يتم إعطاء اسمها في حالة العمود . وبالتالي يتم تجاهل القيم المحتملة في الخلايا الفارغة.
تم ترتيب الصفوف في الملخص بحيث تكون تغطية جميع حالات RB المحتملة مفهومة بسهولة.
يشير دوران العمود إلى ما إذا كان الدوران يساهم في إعادة التوازن.
يُظهر تعيين العمود تعيينًا لـ N قبل الدخول في خطوة تكرار لاحقة. قد يؤدي هذا إلى إعادة تعيين العقد الأخرى P و C و S و D أيضًا.
إذا تم تغيير شيء ما بواسطة الحالة، فسيتم عرض ذلك في مجموعة الأعمدة بعد .
تشير علامة ✓ في العمود التالي إلى اكتمال إعادة التوازن بهذه الخطوة. إذا حدد العمود التالي حالة واحدة فقط، فسيتم تقديم هذه الحالة باعتبارها الحالة التالية، وإلا فستكون هناك علامات استفهام.
توجد الحلقة في الأقسام من Start_Dخلال "حذف الحالة D2"، حيث يتم تصعيد مشكلة إعادة التوازن إلى مستوى أعلى في الشجرة بحيث تصبح العقدة الأصلية P هي العقدة الحالية الجديدة N. لذا فإن الأمر يتطلب تكرارات قصوى لإصلاح الشجرة (حيث يكون ارتفاع الشجرة). ولأن احتمال التصعيد ينخفض بشكل كبير مع كل تكرار فإن إجمالي تكلفة إعادة التوازن ثابتة في المتوسط، بل ثابتة مستهلكة. (كملاحظة جانبية: يشير Mehlhorn & Sanders إلى: "لا تدعم أشجار AVL تكاليف التحديث المستهلكة الثابتة." ^[16]^{: 165، 158} وهذا صحيح بالنسبة لإعادة التوازن بعد الحذف، ولكن ليس إدراج AVL. ^[33] ) $\دلتا h=1$ $h$ $h$
خارج جسم الحلقة هناك فروع موجودة للحالات D3، D6، D5 + D6، D4، وD1؛ يحتوي قسم "حذف الحالة D3" الخاص به على ثلاثة فروع موجودة مختلفة للحالات D6 ، D5 و D4 .
تحدث الدورات في الحالات D6 و D5 + D6 و D3 + D5 + D6 – كلها خارج الحلقة. وبالتالي، تحدث ثلاث دورات على الأكثر في المجموع.

حذف الحالة D1

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

  // Case_D1 (P == NULL): 
return ; // تم الحذف

حذف الحالة D2

→ شرح الرموز

حذف الحالة D2

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

    // Case_D2 (P+C+S+D أسود): 
S -> اللون = أحمر ؛ N = P ؛ // عقدة حالية جديدة (ربما الجذر) // تكرار مستوى أسود واحد // (= مستوى شجرة واحد) أعلى } while (( P = N -> parent ) != NULL ); // نهاية حلقة (do while)- // (مع return;)

حذف الحالة D3

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

Case_D3 : // S red && P+C+D black: RotateDirRoot ( T , P , dir ); // P may be the root P -> color = RED ; S -> color = BLACK ; S = C ; // != NIL // now: P red && S black D = S -> child [ 1 - dir ]; // ابن أخ بعيد if ( D != NIL && D -> color == RED ) go to Case_D6 ; // D red && S black C = S -> child [ dir ]; // ابن أخ قريب if ( C != NIL && C -> color == RED ) go to Case_D5 ; // C red && S+D black // بخلاف ذلك، تعتبر C+D سوداء. // الانتقال إلى Case_D4

حذف الحالة D4

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

Case_D4 : // P أحمر وS+C+D أسود: S -> اللون = أحمر ؛ P -> اللون = أسود ؛ العودة ؛ // تم الحذف

حذف الحالة D5

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

Case_D5 : // C أحمر وS+D أسود: RotateDir ( S ، 1 - dir )؛ // S ليس الجذر أبدًا S -> اللون = أحمر ؛ C -> اللون = أسود ؛ D = S ؛ S = C ؛ // الآن: D أحمر وS أسود // الانتقال إلى Case_D6

حذف الحالة D6

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

Case_D6 : // D أحمر وS أسود: RotateDirRoot ( T ، P ، dir )؛ // قد يكون P هو الجذر S -> color = P -> color ؛ P -> color = BLACK ؛ D -> color = BLACK ؛ return ؛ // تم الحذف } // نهاية RBdelete2

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

إثبات الحدود

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

$m_{h}$	$=2^{\lfloor (h+1)/2\rfloor }+2^{\lfloor h/2\rfloor }-2$
	$={\Biggl \{}$	$2\cdot 2^{\tfrac {h}{2}}-2=2^{\tfrac {h}{2}}+1}-2$		إذا حتى $h$
	$3\cdot 2^{\tfrac {h-1}{2}}-2$		إذا كان غريبا $h$

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

دليل

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

شجرة RB ذات ارتفاع ضئيل وجذور حمراء. وهذا يتفق مع $h=1$

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

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

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

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

حل الدالة لـ $h$

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

m_{h}=3\cdot 2^{(h-1)/2}-2={\bigl (}3\cdot 2^{-3/2}{\bigr )}\cdot 2^{(h+2)/2}-2>2\cdot 2^{h/2}-2

.

لذا في كلتا الحالتين، الزوجية والفردية، في الفاصل $h$

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

مع كون عدد العقد. ^[34] $n$

خاتمة

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

عمليات المجموعة والعمليات المجمعة

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

الانضمام : توجد الدالة الانضمام على شجرتين حمراوين وسوداوين $t 1$ و $t 2$ ومفتاح $k$ ، حيث $t 1 < k < t 2$ ، أي أن جميع المفاتيح في $t 1$ أقل من $k$ ، وجميع المفاتيح في $t 2$ أكبر من $k$ . وترجع شجرة تحتوي على جميع العناصر في $t 1$ و $t 2$ أيضًا كـ $k$ .

إذا كانت الشجرتان لهما نفس الارتفاع الأسود، فإن Join ببساطة ينشئ عقدة جديدة بشجرة فرعية يسارية

t 1

وجذر

k

وشجرة فرعية يمينية

t 2.

إذا كان لكل من

t 1

و

t 2

جذر أسود، فاضبط

k

ليكون أحمر. وإلا فسيتم ضبط

k ليكون أسود.

إذا كانت ارتفاعات اللون الأسود غير متساوية، افترض أن ارتفاع اللون الأسود في

t 1

أكبر من ارتفاع اللون الأسود في

t 2

(الحالة الأخرى متناظرة). يتبع الانضمام العمود الفقري الأيمن لـ

t 1

حتى العقدة السوداء

c

، والتي تكون متوازنة مع

t 2.

في هذه المرحلة، يتم إنشاء عقدة جديدة مع الطفل الأيسر

c

والجذر

k

(المضبوط ليكون أحمر) والطفل الأيمن

t 2

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

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

بالنسبة لبعض التطبيقات، تقوم Split أيضًا بإرجاع قيمة منطقية تشير إلى ظهور

x

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

O(\log n),

خوارزمية الانضمام هي كما يلي:

دالة joinRightRB(T _L , k, T _R ):
     إذا كان (T _L .color=black) و(T _L .blackHeight=T _R .blackHeight):
         ارجع Node(T _L ,⟨k,red⟩,T _R )
    T'=Node(T _L .left,⟨T _L .key,T _L .color⟩,joinRightRB(T _L .right,k,T _R ))
     إذا كان (T _L .color=black) و(T'.right.color=T'.right.right.color=red):
        ت. يمين.يمين.لون=أسود؛
        العودة rotateLeft(T')
     العودة T' /* T ' '[مستقيم T'] */

دالة joinLeftRB(T _L , k, T _R ):
  /* متماثل للانضمام إلى RightRB */

دالة join(T _L , k, T _R ):
     إذا كان T _L .blackHeight>T _R .blackHeight:
        T'=joinRightRB(T _L ,k,T _R )
         إذا كان (T'.color=red) و(T'.right.color=red):
            ت.اللون=أسود
        العودة T'
     إذا كان T _R .blackHeight>T _L .blackHeight:
        /* متماثل */
    إذا كان (T _L .color=black) و (T _R .color=black):
         ارجع Node(T _L ,⟨k,red⟩,T _R )
     ارجع Node(T _L ,⟨k,black⟩,T _R )

خوارزمية التقسيم هي كما يلي:

دالة split(T, k):
     إذا (T = nil) ارجع (nil, false, nil)
     إذا (k = T.key) ارجع (T.left, true, T.right)
     إذا (k < T.key):
        (L',b,R') = تقسيم (T.يسار، k)
        العودة (L',b,join(R',T.key,T.right))
    (L',b,R') = تقسيم (T.right, k)
    العودة (الانضمام (T.left، T.key، L')، b، T.right)

اتحاد شجرتين حمراء وسوداء $t 1$ و $t 2$ تمثلان المجموعتين $A$ و $B$ ، هو شجرة حمراء وسوداء $t$ تمثل $A \cup B.$ تحسب الدالة التكرارية التالية هذا الاتحاد:

دالة الاتحاد (t ₁ ، t ₂ ):
     إذا كانت t ₁ = صفرًا، ارجع t ₂
    إذا كانت t ₂ = صفرًا، ارجع t ₁ 
    (L ₁ ، b، R ₁ ) = تقسيم (t ₁ ، t _2. مفتاح)
    proc1= البداية :
        T _L = اتحاد (L ₁ ، t ₂ . يسار)
    proc2= البداية :
        T _R =union(R ₁ ,t ₂ .right)
     انتظر الكل proc1,proc2
     ارجع join(T _L , t ₂ .key, T _R )

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

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

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

الخوارزميات المتوازية

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

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

عمليات مجمعة متوازية

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

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

الانضمام القائم

يمكن تطبيق هذا النهج على كل بنية بيانات تسلسلية مرتبة تدعم عمليات الضم والتقسيم الفعالة. ^[37] والفكرة العامة هي تقسيم البيانات إلى أجزاء متعددة وإجراء عمليات الإدراج على هذه الأجزاء بالتوازي. $I$ $T$

أولاً يجب فرز الجزء الأكبر من العناصر المراد إدراجها. $I$
بعد ذلك، تنقسم الخوارزمية إلى أجزاء ذات أحجام متساوية تقريبًا. $I$ $k\in \mathbb {N} ^{+}$ $\langle I_{1},\cdots ,I_{k}\rangle$
بعد ذلك يجب تقسيم الشجرة إلى أجزاء بطريقة تجعل لكل منها القيود التالية: $T$ $T$ $k$ $k$ $\langle T_{1},\cdots ,T_{k}\rangle$ $\langle T_{1},\cdots ,T_{k}\rangle$ $j\in \mathbb {N} ^{+}|\,1\leq j<k$ $j\in \mathbb {N} ^{+}|\,1\leq j<k$
1. ${\text{last}}(I_{j})<{\text{first}}(T_{j+1})$
2. ${\text{last}}(T_{j})<{\text{first}}(I_{j+1})$
الآن تقوم الخوارزمية بإدراج كل عنصر من عناصر في بشكل متسلسل. يجب تنفيذ هذه الخطوة لكل ، ويمكن القيام بذلك بواسطة ما يصل إلى معالجات بالتوازي. $I_{j}$ $T_{j}$ $j$ $k$
وأخيرًا، سيتم ضم الأشجار الناتجة لتشكيل النتيجة النهائية للعملية بأكملها.

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

الشجرة الأولية
تقسيم I و T
أدخل في الانقسام T
مشترك

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

bulkInsert (T, I, k):
    1.الفرز
    bulklInsertRec(T, I, k)

bulkInsertRec (T, I, k):
     إذا k = 1:
         لجميع e في I: T.insert(e)
     وإلا
        م := ⌊الحجم(I) / 2⌋
        (T ₁ ، _، T ₂ ) := تقسيم (T، I[m])
        bulkInsertRec(T ₁ ، I[0 .. م]، ⌈k / 2⌉)
            || bulkInsertRec(T ₂ ، I[m + 1 .. الحجم (I) - 1]، ⌊k / 2⌋)
        T ← join2(T ₁ , T ₂ )

وقت التنفيذ

لم يتم أخذ الفرز في الاعتبار في هذا التحليل. $I$

#مستويات التكرار	$\in O(\log k)$
T(تقسيم) + T(ضم)	$\in O(\log \|T\|)$
إدخالات لكل خيط	$\in O\left({\frac {\|I\|}{k}}\right)$
ت(أدخل)	$\in O(\log \|T\|)$
T(bulkInsert) مع = #معالجات $k$	$\in O\left(\log k\log \|T\|+{\frac {\|I\|}{k}}\log \|T\|\right)$

يمكن تحسين ذلك باستخدام خوارزميات متوازية للتقسيم والربط. في هذه الحالة، يكون وقت التنفيذ . ^[38] $\in O\left(\log |T|+{\frac {|I|}{k}}\log |T|\right)$

عمل

#انقسامات، #انضمامات	$\in O(k)$
W(تقسيم) + W(ضم)	$\in O(\log \|T\|)$
#إدراجات	$\in O(\|I\|)$
و(أدخل)	$\in O(\log \|T\|)$
W(إدراج بالجملة)	$\in O(k\log \|T\|+\|I\|\log \|T\|)$

خطوط الأنابيب

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

أولاً يجب فرز الجزء الأكبر من العناصر المراد إدراجها. $I$
لكل عنصر في الخوارزمية يتم تحديد موضع الإدراج المناسب في . ويمكن القيام بذلك بالتوازي لكل عنصر حيث لن يتم تحوره في هذه العملية. يجب الآن تقسيمه إلى تسلسلات فرعية وفقًا لموضع الإدراج لكل عنصر. على سبيل المثال ، التسلسل الفرعي لـ الذي يحتوي على العناصر التي سيكون موضع إدراجها على يسار العقدة . $I$ $T$ $\in I$ $T$ $I$ $S$ $s_{n,{\mathit {left}}}$ $I$ $n$
سيتم إدراج العنصر الأوسط لكل تسلسل فرعي في عقدة جديدة . ويمكن القيام بذلك بالتوازي لكل عقدة، حيث إن موضع إدراج كل عقدة فريد من نوعه. إذا احتوى على عناصر إلى اليسار أو اليمين من ، فسيتم تضمينها في مجموعة جديدة من التسلسلات الفرعية مثل أو . $m_{n,{\mathit {dir}}}$ $s_{n,{\mathit {dir}}}$ $T$ $n'$ $m_{n,{\mathit {dir}}}$ $m_{n,{\mathit {dir}}}$ $s_{n,{\mathit {dir}}}$ $m_{n,{\mathit {dir}}}$ $S$ $s_{n',{\mathit {left}}}$ $s_{n',{\mathit {right}}}$
الآن من الممكن أن يحتوي على ما يصل إلى عقدتين حمراوين متتاليتين في نهاية المسارات من الجذر إلى الأوراق، والتي تحتاج إلى إصلاح. لاحظ أنه أثناء الإصلاح، يجب تحديث موضع إدراج العناصر، إذا تأثرت العقد المقابلة بالدوران. إذا كان لعقدتين أسلاف سوداء أقرب مختلفة، فيمكن إصلاحهما بالتوازي. نظرًا لأنه لا يمكن أن يكون لأربع عقد على الأكثر نفس السلف الأسود الأقرب، فيمكن إصلاح العقد الموجودة في أدنى مستوى في عدد ثابت من الخطوات المتوازية. سيتم تطبيق هذه الخطوة على التوالي على المستويات السوداء أعلاه حتى يتم إصلاحها بالكامل. $T$ $\in S$

$T$
سيتم تكرار الخطوات من 3 إلى 5 على التسلسلات الفرعية الجديدة حتى تصبح فارغة. في هذه المرحلة، تم إدراج كل عنصر. يُطلق على كل تطبيق لهذه الخطوات اسم مرحلة . نظرًا لأن طول التسلسلات الفرعية في هو وفي كل مرحلة يتم قطع التسلسلات الفرعية إلى النصف، فإن عدد المراحل هو . نظرًا لأن جميع المراحل تتحرك لأعلى مستويات اللون الأسود في الشجرة، فيمكن موازاتها في خط أنابيب. بمجرد انتهاء المرحلة من معالجة مستوى أسود واحد، تكون المرحلة التالية قادرة على التحرك لأعلى والاستمرار عند هذا المستوى. $S$ $\in I$ $S$ $\in O(|I|)$ $\in O(\log |I|)$

الشجرة الأولية
البحث عن مواضع الإدراج
المرحلة 1 إدراج العناصر
المرحلة الأولى تبدأ بإصلاح العقد
المرحلة 2 إدراج العناصر
المرحلة الثانية تبدأ بإصلاح العقد
المرحلة 3 إدراج العناصر
المرحلة الثالثة تبدأ بإصلاح العقد
المرحلة الثالثة تستمر في إصلاح العقد

وقت التنفيذ

لا يتم أخذ الفرز في الاعتبار في هذا التحليل. كما يُفترض أن يكون أصغر من ، وإلا فسيكون من الأفضل إنشاء الشجرة الناتجة من الصفر. $I$ $|I|$ $|T|$

T(البحث عن موضع الإدراج)	$\in O(\log \|T\|)$
#مراحل	$\in O(\log \|I\|)$
T(إدراج) + T(إصلاح)	$\in O(\log \|T\|)$
T(bulkInsert) مع ~ #processors $\|I\|$	$\in O(\log \|I\|+2\cdot \log \|T\|)$ $=O(\log \|T\|)$

عمل

W(البحث عن مواضع الإدراج)	$\in O(\|I\|\log \|T\|)$
#إدخالات، #إصلاحات	$\in O(\|I\|)$
W(إدراج) + W(إصلاح)	$\in O(\log \|T\|)$
W(إدراج بالجملة)	$\in O(2\cdot \|I\|\log \|T\|)$ $=O(\|I\|\log \|T\|)$

انظر أيضا

قائمة هياكل البيانات
هيكل بيانات الشجرة
دوران الشجرة
شجرة إحصائية الطلب
شجرة AA ، وهي نوع من أنواع الشجرة ذات اللون الأحمر والأسود
شجرة حمراء سوداء ذات ميول يسارية
شجرة AVL
شجرة B ( شجرة 2–3 ، شجرة 2–3–4 ، شجرة B+ ، شجرة B* ، شجرة UB )
شجرة كبش الفداء
شجرة متباعدة
شجرة تي
شجرة WAVL

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

^ أ ب كورمن، توماس إتش .؛ ليسيرسون، تشارلز إي .؛ ريفست، رونالد إل .؛ شتاين، كليفورد (2001). "الأشجار الحمراء والسوداء". مقدمة إلى الخوارزميات (الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا. ص 273-301. رقم ISBN 978-0-262-03293-3.
^ باتون، جيمس. "الأشجار الحمراء والسوداء".
^ موريس، جون (1998). "الأشجار الحمراء والسوداء". هياكل البيانات والخوارزميات .
^ باير، رودولف (1972). "الأشجار الثنائية المتماثلة B: بنية البيانات وخوارزميات الصيانة". Acta Informatica . 1 (4): 290–306. doi :10.1007/BF00289509. S2CID 28836825.
^ Drozdek, Adam (2001). Data Structures and Algorithms in Java (2 ed.). Sams Publishing. ص. 323. ISBN 978-0534376680.
^ ab Guibas, Leonidas J. ; Sedgewick, Robert (1978). "إطار ثنائي اللون للأشجار المتوازنة". وقائع الندوة السنوية التاسعة عشرة حول أسس علوم الكمبيوتر . ص 8-21. doi :10.1109/SFCS.1978.3.
^ "أشجار حمراء سوداء". foreverlyconfuzzled.com . مؤرشف من الأصل في 2007-09-27 . تم الاسترجاع في 2015-09-02 .
^ Sedgewick, Robert (2012). Red–Black BSTs. Coursera. يتساءل الكثير من الناس لماذا استخدمنا اسم الأحمر والأسود. حسنًا، لقد اخترعنا بنية البيانات هذه، هذه الطريقة في النظر إلى الأشجار المتوازنة، في Xerox PARC الذي كان موطنًا للكمبيوتر الشخصي والعديد من الابتكارات الأخرى التي نعيش معها اليوم والتي تدخل واجهات المستخدم الرسومية، وEthernet والبرمجة الموجهة للكائنات والعديد من الأشياء الأخرى. لكن أحد الأشياء التي تم اختراعها هناك كانت الطباعة بالليزر وكنا متحمسين للغاية لوجود طابعة ليزر ملونة قريبة يمكنها طباعة الأشياء بالألوان ومن بين الألوان كان اللون الأحمر هو الأفضل. لذا، لهذا السبب اخترنا اللون الأحمر للتمييز بين الروابط الحمراء وأنواع الروابط في ثلاث عقد. لذا، فهذه إجابة على السؤال للأشخاص الذين كانوا يسألون.
^ "من أين جاء مصطلح "الشجرة الحمراء/السوداء"؟". Programmers.stackexchange.com . تم الاسترجاع في 2015-09-02 .
^ أندرسون، أرن (11 أغسطس 1993). "أشجار البحث المتوازنة أصبحت بسيطة". في ديهني، فرانك؛ ساك، يورج روديجر؛ سانتورو، نيكولا؛ وايتسايدز، سو (المحررون). الخوارزميات وهياكل البيانات (وقائع). ملاحظات المحاضرات في علوم الكمبيوتر. المجلد 709. دار نشر سبرينغر برلين هايدلبرغ. ص 60-71. CiteSeerX 10.1.1.118.6192 . doi :10.1007/3-540-57155-8_236. ISBN 978-3-540-57155-1. تم أرشفة النسخة الأصلية في 2018-12-08.عنوان URL البديل
^ Okasaki, Chris (1999-01-01). "Red–black trees in a function setting". مجلة البرمجة الوظيفية . 9 (4): 471–477. doi : 10.1017/S0956796899003494 . ISSN 1469-7653. S2CID 20298262.
^ سيدجويك، روبرت (1983). الخوارزميات (الطبعة الأولى). أديسون ويسلي . رقم ISBN 978-0-201-06672-2.
^ Sedgewick, Robert ; Wayne, Kevin. "RedBlackBST.java". algs4.cs.princeton.edu . تم الاسترجاع في 7 أبريل 2018 .
^ سيدجويك، روبرت (2008). "الأشجار الحمراء والسوداء ذات الميول اليسارية" (PDF) .
^ abc Sedgewick, Robert ; Wayne, Kevin (2011). Algorithms (الطبعة الرابعة). Addison-Wesley Professional. ISBN 978-0-321-57351-3.
^ abcd Mehlhorn, Kurt ; Sanders, Peter (2008). "7. Sorted Sequences" (PDF) . الخوارزميات وهياكل البيانات: مجموعة الأدوات الأساسية. برلين/هايدلبرج: سبرينغر. CiteSeerX 10.1.1.148.2305 . doi :10.1007/978-3-540-77978-0. ISBN 978-3-540-77977-3.
^ ab Cormen, Thomas ; Leiserson, Charles ; Rivest, Ronald ; Stein, Clifford (2022). "13. Red–Black Trees". Introduction to Algorithms (الطبعة الرابعة). MIT Press . ص 331-332. ISBN 9780262046305.
^ باستخدام تعريف كنوث للنظام: الحد الأقصى لعدد الأطفال
^ Sedgewick, Robert (1998). Algorithms in C++ . Addison-Wesley Professional. ص 565-575. ISBN 978-0-201-35088-3.
^ "IBM Developer". developer.ibm.com . تم الاسترجاع في 25 مايو 2024 .
^ "تنفيذ epoll (1)". سبتمبر 2014.
^ فاف 2004
^ من "روبرت سيدجويك" (PDF) . Cs.princeton.edu . 4 يونيو 2020. تم الاسترجاع في 26 مارس 2022 .
^ "الأشجار المتوازنة" (PDF) . Cs.princeton.edu . تم الاسترجاع في 26 مارس 2022 .
^ ديمين ، إد. هارمون، د.؛ إياكونو، J.؛ باتراسكو، م. (2007). “الأمثلية الديناميكية – تقريبًا” (PDF) . مجلة SIAM للحوسبة . 37 (1): 240. دوى :10.1137/S0097539705447347. S2CID 1480961.
^ "كيف يعمل HashMap في JAVA". coding-geek.com.
^ تارجان، روبرت إندري (أبريل 1985). "التعقيد الحسابي المطفأ" (PDF) . مجلة SIAM للطرق الجبرية والمنفصلة . 6 (2): 306-318. doi :10.1137/0606031.
^ الشيء المهم في دورات الشجرة هذه هو أنها تحافظ على تسلسل عقد الشجرة.
^ "بن فاف (2007): إصدار HTML عبر الإنترنت لمجموعة موثقة جيدًا من روتينات مكتبة شجرة البحث الثنائية والأشجار المتوازنة".
^ ab تحتوي الأعمدة اليسرى على عدد أقل بكثير من العقد مقارنة بالأعمدة اليمنى، وخاصة فيما يتعلق بالإزالة. يشير هذا إلى أنه يمكن تحقيق بعض الكفاءة عن طريق سحب التكرار الأول من حلقات إعادة التوازن للإدراج والحذف، لأن العديد من العقد المسماة هي عقد فارغة في التكرار الأول وغير فارغة بشكل قاطع لاحقًا. (انظر أيضًا هذه الملاحظة.)
^ تم وضع الدورات قبل إعادة التلوين لأسباب تتعلق بالوضوح. لكن يتم التنقل بينهما، بحيث يكون من الممكن اختيار نقل الدورة إلى الذيل بحرية .
^ ab تم العثور على نفس التقسيم في Ben Pfaff.
^ دينيش ب. ميهتا، سارتاج ساهني (محرر) دليل هياكل البيانات والتطبيقات 10.4.2
^ تنطبق المساواة عند الحد الأعلى على أشجار RB الدنيا RB _{2 k} ذات الارتفاع الزوجي مع العقد وفقط لتلك الأشجار. لذا فإن التفاوت أكثر دقة بشكل طفيف من المثال الشائع في كورمن ص 264. علاوة على ذلك، فإن هذه الأشجار هي أشجار ثنائية تقبل لونًا واحدًا فقط يتوافق مع متطلبات RB من 1 إلى 4. ولكن هناك أشجار أخرى من هذا القبيل، على سبيل المثال إضافة عقدة فرعية إلى ورقة سوداء يجبرها دائمًا على اللون الأحمر. (تسمح شجرة RB الدنيا ذات الارتفاع الفردي بقلب لون الجذر من الأحمر إلى الأسود.) $2\cdot k$ $n=2\cdot 2^{k}-2$ $h<2\log _{2}(n+1),$
^ ab Blelloch, Guy E. ; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets" (PDF) , Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016) , ACM, pp. 253–264, arXiv : 1602.02120 , doi :10.1145/2935764.2935768, ISBN 978-1-4503-4210-0، S2CID 2897793.
^ بارك، هيجين؛ بارك، كونسو (2001). "خوارزميات موازية للأشجار الحمراء والسوداء". علوم الكمبيوتر النظرية . 262 (1-2): 415-435. doi : 10.1016/S0304-3975(00)00287-5 . تعمل خوارزميتنا الموازية لبناء شجرة حمراء وسوداء من قائمة مرتبة من العناصر في الوقت المناسب مع المعالجات الموجودة على ذاكرة الوصول العشوائي CRCW وتعمل في الوقت المناسب مع المعالجات الموجودة على ذاكرة الوصول العشوائي EREW. $n$ $O(1)$ $n$ $O(\log \log n)$ $n/\log \log n$
^ ساندرز، بيتر (2019). ميلهورن، كورت؛ ديتزفيلبينجر، مارتن؛ ديمنتييف، رومان (المحررون). الخوارزميات المتسلسلة والمتوازية وهياكل البيانات: مجموعة الأدوات الأساسية . سبرينغر للكتب الإلكترونية. شام: سبرينغر. ص 252-253. doi :10.1007/978-3-030-25209-0. ISBN 9783030252090. S2CID 201692657.
^ Akhremtsev, Yaroslav; Sanders, Peter (2016). "Fast Parallel Operations on Search Trees". HiPC 2016, the 23rd IEEE International Conference on High Performance Computing, Data, and Analytics, Hyderabad, India, December, 19-22 . IEEE, Piscataway (NJ): 291–300. arXiv : 1510.05433 . Bibcode :2015arXiv151005433A. ISBN 978-1-5090-5411-4.
^ ياجا، جوزيف (1992). مقدمة إلى الخوارزميات المتوازية. ريدنج، ماساتشوستس. [ua]: أديسون ويسلي. ص 65-70. ISBN 0201548569. زبل 0781.68009.

قراءة إضافية

عالم الرياضيات: شجرة حمراء وسوداء
جامعة ولاية سان دييغو: CS 660: ملاحظات حول الأشجار الحمراء والسوداء، بقلم روجر ويتني
فاف، بن (يونيو 2004). "تحليل أداء BSTs في برمجيات النظام" (PDF) . جامعة ستانفورد .

روابط خارجية

بن فاف: مقدمة إلى أشجار البحث الثنائية والأشجار المتوازنة. مؤسسة البرمجيات الحرة، بوسطن 2004، ftp.gnu.org (ملف PDF بتنسيق gzip؛ 1662 كيلو بايت)
تنفيذ كامل وعامل في لغة C
محاضرة OCW MIT حول الأشجار الحمراء والسوداء لإريك ديماين
تصور إدراج شجرة البحث الثنائية على YouTube – تصور إدراجات البيانات العشوائية والمرتبة مسبقًا، في أشجار البحث الثنائية الأولية، والأشجار الحمراء والسوداء ذات الميل إلى اليسار
شجرة حمراء وسوداء مزعجة مكتوبة بلغة C++
BSTs باللونين الأحمر والأسود في أشجار البحث المتوازنة 3.3
عرض توضيحي باللونين الأحمر والأسود من BST

Original text

Rate this translation

Your feedback will be used to help improve Google Translate

[Cormen2001-1] أ ب كورمن، توماس إتش .؛ ليسيرسون، تشارلز إي .؛ ريفست، رونالد إل .؛ شتاين، كليفورد (2001). "الأشجار الحمراء والسوداء". مقدمة إلى الخوارزميات (الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا. ص 273-301. رقم ISBN 978-0-262-03293-3.

[wiscurl2-2] باتون، جيمس. "الأشجار الحمراء والسوداء".

[3] موريس، جون (1998). "الأشجار الحمراء والسوداء". هياكل البيانات والخوارزميات .

[Bayer72-4] باير، رودولف (1972). "الأشجار الثنائية المتماثلة B: بنية البيانات وخوارزميات الصيانة". Acta Informatica . 1 (4): 290–306. doi :10.1007/BF00289509. S2CID 28836825.

[5] Drozdek, Adam (2001). Data Structures and Algorithms in Java (2 ed.). Sams Publishing. ص. 323. ISBN 978-0534376680.

[GS78-6] Guibas, Leonidas J. ; Sedgewick, Robert (1978). "إطار ثنائي اللون للأشجار المتوازنة". وقائع الندوة السنوية التاسعة عشرة حول أسس علوم الكمبيوتر . ص 8-21. doi :10.1109/SFCS.1978.3.

[7] "أشجار حمراء سوداء". foreverlyconfuzzled.com . مؤرشف من الأصل في 2007-09-27 . تم الاسترجاع في 2015-09-02 .

[Sedgewick12-8] Sedgewick, Robert (2012). Red–Black BSTs. Coursera. يتساءل الكثير من الناس لماذا استخدمنا اسم الأحمر والأسود. حسنًا، لقد اخترعنا بنية البيانات هذه، هذه الطريقة في النظر إلى الأشجار المتوازنة، في Xerox PARC الذي كان موطنًا للكمبيوتر الشخصي والعديد من الابتكارات الأخرى التي نعيش معها اليوم والتي تدخل واجهات المستخدم الرسومية، وEthernet والبرمجة الموجهة للكائنات والعديد من الأشياء الأخرى. لكن أحد الأشياء التي تم اختراعها هناك كانت الطباعة بالليزر وكنا متحمسين للغاية لوجود طابعة ليزر ملونة قريبة يمكنها طباعة الأشياء بالألوان ومن بين الألوان كان اللون الأحمر هو الأفضل. لذا، لهذا السبب اخترنا اللون الأحمر للتمييز بين الروابط الحمراء وأنواع الروابط في ثلاث عقد. لذا، فهذه إجابة على السؤال للأشخاص الذين كانوا يسألون.

[9] "من أين جاء مصطلح "الشجرة الحمراء/السوداء"؟". Programmers.stackexchange.com . تم الاسترجاع في 2015-09-02 .

[10] أندرسون، أرن (11 أغسطس 1993). "أشجار البحث المتوازنة أصبحت بسيطة". في ديهني، فرانك؛ ساك، يورج روديجر؛ سانتورو، نيكولا؛ وايتسايدز، سو (المحررون). الخوارزميات وهياكل البيانات (وقائع). ملاحظات المحاضرات في علوم الكمبيوتر. المجلد 709. دار نشر سبرينغر برلين هايدلبرغ. ص 60-71. CiteSeerX 10.1.1.118.6192 . doi :10.1007/3-540-57155-8_236. ISBN 978-3-540-57155-1. تم أرشفة النسخة الأصلية في 2018-12-08.عنوان URL البديل

[11] Okasaki, Chris (1999-01-01). "Red–black trees in a function setting". مجلة البرمجة الوظيفية . 9 (4): 471–477. doi : 10.1017/S0956796899003494 . ISSN 1469-7653. S2CID 20298262.

[Algs1-12] سيدجويك، روبرت (1983). الخوارزميات (الطبعة الأولى). أديسون ويسلي . رقم ISBN 978-0-201-06672-2.

[13] Sedgewick, Robert ; Wayne, Kevin. "RedBlackBST.java". algs4.cs.princeton.edu . تم الاسترجاع في 7 أبريل 2018 .

[14] سيدجويك، روبرت (2008). "الأشجار الحمراء والسوداء ذات الميول اليسارية" (PDF) .

[Algs4-15] Sedgewick, Robert ; Wayne, Kevin (2011). Algorithms (الطبعة الرابعة). Addison-Wesley Professional. ISBN 978-0-321-57351-3.

[Mehlhorn2008-16] Mehlhorn, Kurt ; Sanders, Peter (2008). "7. Sorted Sequences" (PDF) . الخوارزميات وهياكل البيانات: مجموعة الأدوات الأساسية. برلين/هايدلبرج: سبرينغر. CiteSeerX 10.1.1.148.2305 . doi :10.1007/978-3-540-77978-0. ISBN 978-3-540-77977-3.

[Cormen2009-17] Cormen, Thomas ; Leiserson, Charles ; Rivest, Ronald ; Stein, Clifford (2022). "13. Red–Black Trees". Introduction to Algorithms (الطبعة الرابعة). MIT Press . ص 331-332. ISBN 9780262046305.

[18] باستخدام تعريف كنوث للنظام: الحد الأقصى لعدد الأطفال

[19] Sedgewick, Robert (1998). Algorithms in C++ . Addison-Wesley Professional. ص 565-575. ISBN 978-0-201-35088-3.

[20] "IBM Developer". developer.ibm.com . تم الاسترجاع في 25 مايو 2024 .

[21] "تنفيذ epoll (1)". سبتمبر 2014.

[22] فاف 2004

[LLRB-23] من "روبرت سيدجويك" (PDF) . Cs.princeton.edu . 4 يونيو 2020. تم الاسترجاع في 26 مارس 2022 .

[24] "الأشجار المتوازنة" (PDF) . Cs.princeton.edu . تم الاسترجاع في 26 مارس 2022 .

[DHIP-25] ديمين ، إد. هارمون، د.؛ إياكونو، J.؛ باتراسكو، م. (2007). “الأمثلية الديناميكية – تقريبًا” (PDF) . مجلة SIAM للحوسبة . 37 (1): 240. دوى :10.1137/S0097539705447347. S2CID 1480961.

[26] "كيف يعمل HashMap في JAVA". coding-geek.com.

[tarjan-27] تارجان، روبرت إندري (أبريل 1985). "التعقيد الحسابي المطفأ" (PDF) . مجلة SIAM للطرق الجبرية والمنفصلة . 6 (2): 306-318. doi :10.1137/0606031.

[28] الشيء المهم في دورات الشجرة هذه هو أنها تحافظ على تسلسل عقد الشجرة.

[29] "بن فاف (2007): إصدار HTML عبر الإنترنت لمجموعة موثقة جيدًا من روتينات مكتبة شجرة البحث الثنائية والأشجار المتوازنة".

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

[31] تم وضع الدورات قبل إعادة التلوين لأسباب تتعلق بالوضوح. لكن يتم التنقل بينهما، بحيث يكون من الممكن اختيار نقل الدورة إلى الذيل بحرية .

[cases-32] تم العثور على نفس التقسيم في Ben Pfaff.

[33] دينيش ب. ميهتا، سارتاج ساهني (محرر) دليل هياكل البيانات والتطبيقات 10.4.2

[34] تنطبق المساواة عند الحد الأعلى على أشجار RB الدنيا RB _{2 k} ذات الارتفاع الزوجي مع العقد وفقط لتلك الأشجار. لذا فإن التفاوت أكثر دقة بشكل طفيف من المثال الشائع في كورمن ص 264. علاوة على ذلك، فإن هذه الأشجار هي أشجار ثنائية تقبل لونًا واحدًا فقط يتوافق مع متطلبات RB من 1 إلى 4. ولكن هناك أشجار أخرى من هذا القبيل، على سبيل المثال إضافة عقدة فرعية إلى ورقة سوداء يجبرها دائمًا على اللون الأحمر. (تسمح شجرة RB الدنيا ذات الارتفاع الفردي بقلب لون الجذر من الأحمر إلى الأسود.) $2\cdot k$ $n=2\cdot 2^{k}-2$ $h<2\log _{2}(n+1),$

[join-based-35] Blelloch, Guy E. ; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets" (PDF) , Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016) , ACM, pp. 253–264, arXiv : 1602.02120 , doi :10.1145/2935764.2935768, ISBN 978-1-4503-4210-0، S2CID 2897793.

[36] بارك، هيجين؛ بارك، كونسو (2001). "خوارزميات موازية للأشجار الحمراء والسوداء". علوم الكمبيوتر النظرية . 262 (1-2): 415-435. doi : 10.1016/S0304-3975(00)00287-5 . تعمل خوارزميتنا الموازية لبناء شجرة حمراء وسوداء من قائمة مرتبة من العناصر في الوقت المناسب مع المعالجات الموجودة على ذاكرة الوصول العشوائي CRCW وتعمل في الوقت المناسب مع المعالجات الموجودة على ذاكرة الوصول العشوائي EREW. $n$ $O(1)$ $n$ $O(\log \log n)$ $n/\log \log n$

[37] ساندرز، بيتر (2019). ميلهورن، كورت؛ ديتزفيلبينجر، مارتن؛ ديمنتييف، رومان (المحررون). الخوارزميات المتسلسلة والمتوازية وهياكل البيانات: مجموعة الأدوات الأساسية . سبرينغر للكتب الإلكترونية. شام: سبرينغر. ص 252-253. doi :10.1007/978-3-030-25209-0. ISBN 9783030252090. S2CID 201692657.

[38] Akhremtsev, Yaroslav; Sanders, Peter (2016). "Fast Parallel Operations on Search Trees". HiPC 2016, the 23rd IEEE International Conference on High Performance Computing, Data, and Analytics, Hyderabad, India, December, 19-22 . IEEE, Piscataway (NJ): 291–300. arXiv : 1510.05433 . Bibcode :2015arXiv151005433A. ISBN 978-1-5090-5411-4.

[39] ياجا، جوزيف (1992). مقدمة إلى الخوارزميات المتوازية. ريدنج، ماساتشوستس. [ua]: أديسون ويسلي. ص 65-70. ISBN 0201548569. زبل 0781.68009.

ف ت هـ هياكل بيانات الشجرة
البحث في الأشجار ( المجموعات الديناميكية / المصفوفات الترابطية )	2-3 2-3-4 أأ (أ،ب) أفل ب ب+ ب* ب ^× ( الأمثل ) البحث الثنائي الرقص شجرة فاصلة إحصائية الطلب باليندرم ( يساري ) أحمر-أسود كبش الفداء تباعد ت تريب يو بي متوازن الوزن
أكوام	ثنائي ثنائي الحدين برودال د -اري فيبوناتشي يساري الاقتران ثنائي الحدين المائل مائل فان إيمدي بواس ضعيف
محاولات	مدينة C-trie (ADT مضغوط) هاش الجذر لاحقة البحث الثلاثي سريع جدًا واي فاست
أشجار تقسيم البيانات المكانية	كرة بك ب س ب ديكارتية هيلبرت ر k -d ( ضمني k -d ) م متري أفضل لاعب شجرة الثماني الرقم الهيدروجيني الأولوية ر رباعية ر ر+ ر* شريحة نائب الرئيس إكس
أشجار أخرى	غطاء أسي فينيويك إصبع مؤشر الشجرة الكسيرية الاندماج تقويم التجزئة المسافة ك-اري الطفل الأيسر هو الأخ أو الأخت اليمنى رابط/قطع دمج مبني على السجل ميركل بي كيو يتراوح س ب ق ر قمة

ف ت هـ هياكل البيانات
أنواع	مجموعة حاوية
خلاصة	المصفوفة الترابطية خريطة متعددة هيكل بيانات الاسترجاع قائمة كومة طابور طابور ذو نهايتين قائمة الأولوية قائمة انتظار ذات أولوية مزدوجة النهاية تعيين مجموعة متعددة مجموعة منفصلة
المصفوفات	مصفوفة بت مخزن دائري مجموعة ديناميكية جدول التجزئة شجرة المصفوفة المجزأة مصفوفة متفرقة
مرتبط	قائمة الجمعيات القائمة المرتبطة قائمة التخطي قائمة مرتبطة غير مجمعة قائمة مرتبطة XOR
الأشجار	شجرة ب شجرة البحث الثنائية شجرة AA شجرة AVL شجرة حمراء-سوداء شجرة ذاتية التوازن شجرة متباعدة كومة كومة ثنائية كومة ثنائية الحدين كومة فيبوناتشي شجرة R شجرة R* شجرة R+ شجرة هيلبرت R تري شجرة الحشيش
الرسوم البيانية	مخطط القرار الثنائي الرسم البياني اللا دوري الموجه رسم بياني للكلمات غير الدورية الموجهة
قائمة هياكل البيانات