9. الأشجار الحمراء-السوداء
في هذا الفصل، نقدّم أشجار الأحمر والأسود (red-black trees)، وهي صيغة من أشجار البحث الثنائي (binary search trees) ذات ارتفاع لوغاريتمي. أشجار الأحمر والأسود من أكثر بنى البيانات انتشارًا على الإطلاق. فهي تظهر بوصفها بنية البحث الأساسية في تطبيقات مكتبات كثيرة، منها إطار مجموعات جافا (Java Collections Framework) وعدّة تطبيقات في مكتبة القوالب المعيارية للغة ++C (C++ Standard Template Library). وهي مستخدَمة كذلك داخل نواة نظام التشغيل لينكس. وهناك عدة أسباب لشعبية أشجار الأحمر والأسود:
- شجرة أحمر وأسود تخزّن قيمة يكون ارتفاعها على الأكثر.
- تعمل العمليتان و على شجرة الأحمر والأسود في في أسوأ الحالات.
- العدد المُستهلك (amortized) لعمليات الدوران (rotation) التي تُنفَّذ أثناء عملية أو ثابت.
والخاصيتان الأوليان من هاتين الخاصيتين تضعان أشجار الأحمر والأسود مسبقًا على قوائم التخطي (skiplists) وأشجار ترياب (treaps) وأشجار الكبش الفداء (scapegoat trees). وتعتمد قوائم التخطي وأشجار ترياب على العشوائية (randomization)، فزمنها التشغيلي البالغ متوقَّع (expected) لا مضمون. أما أشجار الكبش الفداء فلها حدّ مضمون على ارتفاعها، غير أن و لا تعملان إلا في في الزمن المُستهلك (amortized). والخاصية الثالثة ليست سوى إضفاء على الوجه؛ فهي تخبرنا بأن الزمن اللازم لإضافة عنصر أو إزالته أقلّ بكثير من الزمن الذي يستغرقه العثور على .9.1 غير أن الخصائص الممتازة لأشجار الأحمر والأسود يأتي ثمنها: تعقيد التنفيذ (implementation complexity). فالحفاظ على حدّ قدره على الارتفاع ليس بالأمر اليسير؛ إذ يتطلب تحليلًا دقيقًا لعدد من الحالات. ويجب أن نحرص على أن يؤدي التنفيذ الشيء الصحيح تمامًا في كل حالة. فأي دوران في غير موضعه أو تغيير في اللون ينتج خللًا (bug) قد يصعب جدًا فهمه وتتبّعه. وبدلًا من القفز مباشرةً إلى تنفيذ أشجار الأحمر والأسود، سنقدّم أولًا بعض الخلفية عن بنية بيانات ذات صلة: أشجار 2-4. وهذا سيتيح لنا قدرًا من الفهم لكيفية اكتشاف أشجار الأحمر والأسود، ولماذا يكون صيانتها بكفاءة ممكنًا أصلًا.
الحواشي
....9.1 لاحظ أن قوائم التخطي وأشجار ترياب تمتلك هذه الخاصية بالمعنى المتوقَّع (expected). انظر التمرينين 4.6 و7.5.
الأقسام الفرعية
9.1 أشجار 2-4
الأقسام الفرعية
9.1 أشجار 2-4
شجرة 2-4 هي شجرة مُجذَّرة (rooted tree) لها الخصائص التالية: الخاصية 9.1 (الارتفاع) جميع الأوراق (leaves) لها العمق نفسه.
الخاصية 9.2 (الدرجة) لكل عقدة داخلية (internal node) عدد من الأبناء يساوي 2 أو 3 أو 4.
ويبيّن الشكل 9.1 مثالًا على شجرة 2-4.
وتقتضي خصائص أشجار 2-4 أن يكون ارتفاعها لوغاريتميًا في عدد الأوراق:
المبرهنة 9.1 شجرة 2-4 ذات ورقة يكون ارتفاعها على الأكثر.
البرهان. إن الحدّ الأدنى البالغ 2 لعدد أبناء العقدة الداخلية يقتضي أنه إذا كان ارتفاع شجرة 2-4 هو ، فإن شجرة من هذا النوع تملك ورقة على الأقل. بمعنى آخر،
وأخذ لوغاريتم طرفي هذه المتباينة يعطي .
9.1.1 إضافة ورقة
إضافة ورقة إلى شجرة 2-4 أمر يسير (انظر الشكل 9.2). فإذا أردنا إضافة ورقة بوصفها ابنةً لعقدة ما على ما قبل المستوى الأخير، فإننا نكتفي بجعل ابنةً لـ . وهذا يحافظ قطعًا على خاصية الارتفاع، لكنه قد يخالف خاصية الدرجة؛ فإذا كان ذا أربعة أبناء قبل إضافة ، فإن صار له الآن خمسة أبناء. وفي هذه الحالة نقسم إلى عقدتين، ' ذات ابنين، و ' ذات ثلاثة أبناء. لكن ' صارت الآن بلا أب، فنجعلها بشكل تكراري (recursive) ابنةً للعقدة '، أي ابنةً لأب '. ومرة أخرى، قد يسبّب هذا أن يكون لأب ' عدد من الأبناء أكبر مما ينبغي، وعندئذ نقسمه. تستمر هذه العملية حتى نصل إلى عقدة لها أقل من أربعة أبناء، أو حتى نقسم الجذر إلى عقدتين و . وفي الحالة الأخيرة نُنشئ جذرًا جديدًا له و كابنين. وهذا يزيد عمق جميع الأوراق في الوقت نفسه، ولذلك يحافظ على خاصية الارتفاع.
 |
|---|
 |
 |
ولأن ارتفاع شجرة 2-4 لا يتجاوز أبدًا ، تنتهي عملية إضافة الورقة بعد خطوة على الأكثر.
9.1.2 إزالة ورقة
إزالة ورقة من شجرة 2-4 أعقد قليلًا (انظر الشكل 9.3). ولإزالة ورقة من أبيها ، كل ما يلزم هو حذفها. فإذا كان ذا ابنين فقط قبل إزالة ، فإن يتبقّى له ابن واحد فقط فيخالف خاصية الدرجة.
 |
|---|
 |
 |
 |
 |
ولتصحيح ذلك، ننظر إلى العقدة الشقيقة لـ '، وهي . وهذه العقدة موجودة قطعًا لأن أب ' كان له ابنان على الأقل. فإذا كانت لها ثلاثة أو أربعة أبناء، فإننا نأخذ أحد أبناء ونمنحه إلى . عندئذ يكون ذا ابنين وتكون ذات ابنين أو ثلاثة، وقد انتهينا. وعلى النقيض من ذلك، إذا كانت ذات ابنين فقط، فإننا ندمج و في عقدة واحدة، ، ذات ثلاثة أبناء. ثم نُزيل بشكل تكراري من أب . وتنتهي هذه العملية حين نصل إلى عقدة، ، يكون أو شقيقتها أكثر من ابنين، أو حين نصل إلى الجذر. وفي الحالة الأخيرة، إن لم يبقَ للجذر سوى ابن واحد، نحذف الجذر ونجعل ابنه هو الجذر الجديد. وهذا يقلّل ارتفاع كل ورقة في الوقت نفسه، ولذلك يحافظ على خاصية الارتفاع. ومرة أخرى، ولأن ارتفاع الشجرة لا يتجاوز أبدًا ، تنتهي عملية إزالة الورقة بعد خطوة على الأكثر. opendatastructures.org
9.2 RedBlackTree: محاكاة لشجرة 2-4
الأقسام الفرعية
9.2 RedBlackTree: محاكاة لشجرة 2-4
شجرة الأحمر والأسود هي شجرة بحث ثنائي (binary search tree) تكون فيها لكل عقدة، ، صبغة (colour) إما حمراء أو سوداء. ويُملَّم الأحمر بالقيمة 0 والأسود بالقيمة .
class Node<T> extends BinarySearchTree.BSTNode<Node<T>,T> {
byte colour;
}
قبل أي عملية على شجرة الأحمر والأسود وبعدها تكون الخاصيتان التاليتان مستوفىتين. وتُعرَّف كل خاصية بمعاني أسماء الصبغتين الأحمر والأسود، وكذلك بمعاني القيمتين العدديتين 0 و1. الخاصية 9.3 (ارتفاع الأسود) يوجد العدد نفسه من العُقد السوداء في كل مسار من الجذر إلى ورقة. (ومجموع صبغات أي مسار من الجذر إلى ورقة هو نفسه.)
الخاصية 9.4 (انعدام الحافة الحمراء) لا تتجاور أي عقدتين حمراوين. (ولكل عقدة ، عدا الجذر، .)
ولاحِظ أننا نستطيع دائمًا تلوين الجذر لشجرة الأحمر والأسود بالأسود دون إخلال بأي من هاتين الخاصيتين، لذا سنفترض أن الجذر أسود، وستحافظ خوارزميات تحديث شجرة الأحمر والأسود على ذلك. وهناك حيلة أخرى تبسّط أشجار الأحمر والأسود، وهي معاملة العُقد الخارجية (والمُمثَّلة بـ ) بوصفها عُقدًا سوداء. وبهذه الطريقة يكون لكل عقدة حقيقية، ، في شجرة الأحمر والأسود ابنان بالضبط، لكل منهما صبغة محدَّدة تمامًا. ويبيّن الشكل 9.4 مثالًا على شجرة الأحمر والأسود.
الشكل 9.4: مثال على شجرة أحمر وأسود ارتفاع الأسود فيها 3. وقد رُسمت العُقد الخارجية ( ) على هيئة مربعات. 
ولكل عقدة داخلية في ابنان أو ثلاثة أو أربعة: العقدة السوداء التي بدأت بابنين سوداوين لا يزال لها ابنان أسودان بعد هذا التحويل. والعقدة السوداء التي بدأت بابن أحمر وابن أسود يكون لها ثلاثة أبناء بعد هذا التحويل. والعقدة السوداء التي بدأت بابنين أحمرين يكون لها أربعة أبناء بعد هذا التحويل. وعلاوةً على ذلك، فإن خاصية ارتفاع الأسود تضمن الآن أن لكل مسار من الجذر إلى ورقة في الطول نفسه. بمعنى آخر، هي شجرة 2-4! ولشجرة 2-4 هذه، وهي ، ورقة تقابل العُقد الخارجية لشجرة الأحمر والأسود وعددها . ومن ثمّ فإن ارتفاع هذه الشجرة على الأكثر . والآن، فإن كل مسار من الجذر إلى ورقة في شجرة 2-4 يقابل مسارًا من جذر شجرة الأحمر والأسود إلى عقدة خارجية. وأول عقدة وآخر عقدة في هذا المسار تكونان سوداوين، ولا يكون أكثر من عقدة داخلية واحدة من كل عقدتين حمراء، فإن هذا المسار يحتوي على عقدة سوداء على الأكثر، و عقدة حمراء على الأكثر. ولذلك فإن أطول مسار من الجذر إلى أي عقدة داخلية في هو على الأكثر
لأي . وهذا يثبت أهم خصائص أشجار الأحمر والأسود:
المبرهنة 9.2 ارتفاع شجرة الأحمر والأسود ذات عقدة هو على الأكثر.
والآن بعد أن رأينا العلاقة بين أشجار 2-4 وأشجار الأحمر والأسود، ليس صعبًا أن نصدّق إمكانية صيانة شجرة الأحمر والأسود بكفاءة أثناء إضافة العناصر وإزالتها. فقد رأينا من قبل أن إضافة عنصر في BinarySearchTree يمكن إجراؤها بإضافة ورقة جديدة. وعليه، فلتنفيذ في شجرة الأحمر والأسود نحتاج إلى طريقة تحاكي انقسام عقدة ذات خمسة أبناء في شجرة 2-4. وتُمثَّل عقدة شجرة 2-4 ذات الأبناء الخمسة بعقدة سوداء لها ابنان أحمران، أحدهما له بدوره ابن أحمر. يمكننا ``split'' هذه العقدة بأن نلوّنها بالأحمر ونلوّن ابنيها بالأسود. ويبيّن الشكل 9.6 مثالًا على ذلك. الشكل 9.6: محاكاة عملية انقسام في شجرة 2-4 أثناء الإضافة في شجرة الأحمر والأسود. (وهذه تحاكي إضافة شجرة 2-4 المبيّنة في الشكل 9.2.) 
وبالمثل، فإن تنفيذ يتطلب طريقةً لدمج عقدتين واستعارة ابن من شقيقة. ودمج عقدتين هو العملية العكسية للانقسام (المبيّن في الشكل 9.6)، ويتضمّن تلوين شقيقتين (سوداوين) بالأحمر وتلوين أبيهما (الأحمر) بالأسود. أما الاستعارة من شقيقة فهي أعقد هذه الإجراءات، إذ تتضمّن الدوران وإعادة تلوين العُقد معًا. وبالطبع، علينا طوال ذلك أن نحافظ على خاصية انعدام الحافة الحمراء وعلى خاصية ارتفاع الأسود. ولم يعد مدهشًا أن هذا ممكن، غير أن ثمة عددًا كبيرًا من الحالات التي يجب أن نأخذها في الحسبان إذا حاولنا محاكاة شجرة 2-4 مباشرةً بواسطة شجرة الأحمر والأسود. وعند حدٍّ ما يصبح الأمر ببساطة تجاهُل شجرة 2-4 الكامنة والعمل مباشرةً نحو الحفاظ على خصائص شجرة الأحمر والأسود. 9.2.2 أشجار الأحمر والأسود المائلة إلى اليسار لا يوجد تعريف وحيد لأشجار الأحمر والأسود. بل هناك عائلة من البنى تتبيّن كيف تحافظ على خاصيتي ارتفاع الأسود وانعدام الحافة الحمراء أثناء عمليتي و . وتنفّذ البنى المختلفة ذلك بطرق مختلفة. وهنا ننفّذ بنية بيانات نسميها RedBlackTree. وهذه البنية تنفّذ نوعًا بعينه من نسخ أشجار الأحمر والأسود يستوفي خاصية إضافية: الخاصية 9.5 (الميل إلى اليسار) عند أي عقدة ، إذا كان أسود، فإن أسود.
ولاحِظ أن شجرة الأحمر والأسود المبيّنة في الشكل 9.4 لا تستوفي خاصية الميل إلى اليسار؛ إذ يخالفها أب العقدة الحمراء في المسار الأقصى يمينًا. والسبب في الحفاظ على خاصية الميل إلى اليسار أنها تقلّل عدد الحالات التي نتصادم معها عند تحديث الشجرة أثناء عمليتي و . وبعبارة أخرى، في أشجار 2-4، فإن ذلك يعني أن لكل شجرة 2-4 تمثيلًا وحيدًا: عقدة الدرجة الثانية تصبح عقدة سوداء لها ابنان أسودان. وعقدة الدرجة الثالثة تصبح عقدة سوداء ابنها الأيسر أحمر وابنها الأيمن أسود. وعقدة الدرجة الرابعة تصبح عقدة سوداء لها ابنان أحمران. وقبل أن نشرح تنفيذ و بالتفصيل، نقدّم أولًا بعض الإجراءات الفرعية (subroutines) البسيطة التي تستخدمها هاتان الدالتان والمبيّنة في الشكل 9.7. والإجراءان الفرعيان الأولان مخصّصان للتعامل مع الصبغات مع الحفاظ على خاصية ارتفاع الأسود. وتأخذ طريقة كمدخل عقدة سوداء لها ابنان أحمران، وتلوّن بالأحمر وتلوّن ابنيها بالأسود. وتُبطل طريقة هذا الإجراء:
void pushBlack(Node<T> u) {
u.colour--;
u.left.colour++;
u.right.colour++;
}
void pullBlack(Node<T> u) {
u.colour++;
u.left.colour--;
u.right.colour--;
}
وتبدّل طريقة صبغتي و ثم تنفّذ دورانًا إلى اليسار عند . وهذه الطريقة تعكس صبغتي هاتين العقدتين وكذلك علاقتهما بالأب والابن:
void flipLeft(Node<T> u) {
swapColors(u, u.right);
rotateLeft(u);
}
وتفيد عملية بصفة خاصة في استعادة خاصية الميل إلى اليسار (left-leaning) عند عقدة تخالفها (لأن أسود و أحمر). وفي هذه الحالة الخاصة يمكننا أن نتيقن أن هذه العملية تحافظ على كلتا خاصيتي ارتفاع الأسود وانعدام الحافة الحمراء. وعملية متناظرة مع إذا تبادلت أدوار اليمين واليسار.
void flipRight(Node<T> u) {
swapColors(u, u.left);
rotateRight(u);
}
9.2.3 الإضافة
لتنفيذ في RedBlackTree، نفّذ إدراجًا قياسيًا من نمط BinarySearchTree لإضافة ورقة جديدة، ، بحيث ونضبط . ولاحِظ أن هذا لا يغيّر ارتفاع الأسود لأي عقدة، فهو لا يخالف خاصية ارتفاع الأسود. لكنه قد يخالف خاصية الميل إلى اليسار (إذا كانت الابن الأيمن لأبيها)، وقد يخالف خاصية انعدام الحافة الحمراء (إذا كان أبو هو ). ولاستعادة هاتين الخاصيتين نستدعي الطريقة .
boolean add(T x) {
Node<T> u = newNode(x);
u.colour = red;
boolean added = add(u);
if (added)
addFixup(u);
return added;
}
والمبيَّنة في الشكل 9.8، تأخذ طريقة كمدخل عقدة صبغتها حمراء، والتي قد تخالف خاصية انعدام الحافة الحمراء و/أو خاصية الميل إلى اليسار. ومن المرجّح أن يكون اتباع النقاش التالي مستحيلًا دون الرجوع إلى الشكل 9.8 أو إلى إعادة رسمه على ورقة. وقد يُستحسن بالقارئ دراسة هذا الشكل قبل المتابعة.
إذا كانت هي جذر الشجرة، يمكننا تلوين بالأسود لاستعادة الخاصيتين معًا. وإذا كانت العقدة الشقيقة لـ حمراء أيضًا، فلا بد أن يكون أبو أسود، وعليه فكلتا خاصيتي الميل إلى اليسار وانعدام الحافة الحمراء مستوفاة بالفعل. أما فيما عدا ذلك، فنبدأ أولًا بتحديد ما إذا كان أبو ، وهو ، يخالف خاصية الميل إلى اليسار، فإن كان كذلك نفّذنا عملية وضبطنا . وهذا يتركنا في حالة محدَّدة بدقة: هو الابن الأيسر لأبيه ، بحيث أصبحت تستوفي خاصية الميل إلى اليسار. ولم يبقَ سوى ضمان خاصية انعدام الحافة الحمراء عند . ولا نشغل بالنا إلا بالحالة التي تكون فيها حمراء، إذ لو لم تكن كذلك لاستوفى خاصية انعدام الحافة الحمراء أصلًا. وبما أننا لم ننتهِ بعد، فإن حمراء و حمراء. وخاصية انعدام الحافة الحمراء (التي يخالفها دون ) تقتضي أن يكون سلف ، وهو ، موجودًا وملوَّنًا بالأسود. فإذا كان الابن الأيمن لـ أحمر، فإن خاصية الميل إلى اليسار تضمن أن ابني كلاهما أحمر، واستدعاء يجعل حمراء و سوداء. وهذا يستعيد خاصية انعدام الحافة الحمراء عند ، لكنه قد يتسبّب في مخالفتها عند ، فتبدأ العملية كلها من جديد مع . وإذا كان الابن الأيمن لـ أسود، فإن استدعاء يجعل هو الأب (الأسود) للعقدة ويمنح ابنين أحمرين، هما و . وهذا يضمن أن يستوفي خاصية انعدام الحافة الحمراء وأن يستوفي خاصية الميل إلى اليسار. وفي هذه الحالة يمكننا التوقف.
void addFixup(Node<T> u) {
while (u.colour == red) {
if (u == r) { // u is the root - done
u.colour = black;
return;
}
Node<T> w = u.parent;
if (w.left.colour == black) { // ensure left-leaning
flipLeft(w);
u = w;
w = u.parent;
}
if (w.colour == black)
return; // no red-red edge = done
Node<T> g = w.parent; // grandparent of u
if (g.right.colour == black) {
flipRight(g);
return;
} else {
pushBlack(g);
u = g;
}
}
}
وتأخذ طريقة زمنًا ثابتًا في كل تكرار، وكل تكرار إما يُنهي العمل أو ينقل إلى قاعدة الشجرة. ومن ثمّ تنتهي طريقة بعد تكرارًا في .
9.2.4 الإزالة
عملية في RedBlackTree هي أصعب العمليات تنفيذًا، وهذا ينطبق على جميع نسخ أشجار الأحمر والأسود المعروفة. ومثل عملية في BinarySearchTree تمامًا، تنحصر هذه العملية في العثور على عقدة ذات ابن واحد فقط، ، وإخراج العقدة من الشجرة بحيث يجعل ابنه هو . والمشكلة هنا هي أن إذا كان أسود، فإن خاصية ارتفاع الأسود ستُخالف الآن عند . يمكننا تفادي هذه المشكلة مؤقتًا بإضافة إلى . وبالطبع، فإن هذا يُدخل مشكلتين أخريين: (1) إذا كانت و كلتاهما سوداوين في البداية، فإن (الأسود المزدوج، double black)، وهي صبغة غير صالحة. وإذا كان أحمر، فيستبدل بعقدة سوداء ، وقد تخالف خاصية الميل إلى اليسار عند . ويمكن حل المشكلتين معًا باستدعاء طريقة .
boolean remove(T x) {
Node<T> u = findLast(x);
if (u == nil || compare(u.x, x) != 0)
return false;
Node<T> w = u.right;
if (w == nil) {
w = u;
u = w.left;
} else {
while (w.left != nil)
w = w.left;
u.x = w.x;
u = w.right;
}
splice(w);
u.colour += w.colour;
u.parent = w.parent;
removeFixup(u);
return true;
}
وتأخذ طريقة كمدخل عقدة صبغتها أسود (1) أو أسود مزدوج (2). فإذا كانت سوداء مزدوجة، فإن تنفّذ سلسلة من عمليات الدوران وإعادة التلوين تنقل العقدة السوداء المزدوجة إلى أعلى الشجرة حتى يمكن التخلص منها. وأثناء هذه العملية يتغيّر ما تشير إليه إلى أن يشير في نهاية هذه العملية إلى جذر الشجرة الفرعية التي تم تغييرها. وقد يتغير لون جذر هذه الشجرة الفرعية؛ وتحديدًا، قد ينتقل من الأحمر إلى الأسود، ولذلك تنتهي طريقة بفحص ما إذا كان أبو يخالف خاصية الميل إلى اليسار، وإصلاحه إن كان كذلك.
void removeFixup(Node<T> u) {
while (u.colour > black) {
if (u == r) {
u.colour = black;
} else if (u.parent.left.colour == red) {
u = removeFixupCase1(u);
} else if (u == u.parent.left) {
u = removeFixupCase2(u);
} else {
u = removeFixupCase3(u);
}
}
if (u != r) { // restore left-leaning property if needed
Node<T> w = u.parent;
if (w.right.colour == red && w.left.colour == black) {
flipLeft(w);
}
}
}
وتوضّح طريقة في الشكل 9.9. ومرة أخرى، سيكون من الصعب، إن لم يكن مستحيلًا، اتباع النص التالي دون الرجوع إلى الشكل 9.9. ويعالج كل تكرار للحلقة في العقدة السوداء المزدوجة بناءً على إحدى أربع حالات:
الحالة 0: هي الجذر. وهذه أسهل الحالات في المعالجة. فنُعيد تلوين لتصبح سوداء (وهذا لا يخالف أيًّا من خصائص شجرة الأحمر والأسود). الحالة 1: العقدة الشقيقة لـ ، وهي ، حمراء. وفي هذه الحالة يكون شقيق هو الابن الأيسر لأبيه (وذلك استنادًا إلى خاصية الميل إلى اليسار). وننفّذ انقلابًا إلى اليمين عند ثم ننتقل إلى التكرار التالي. ولاحِظ أن هذا الإجراء يجعل أب يخالف خاصية الميل إلى اليسار ويجعل عمق يزداد. لكنه أيضًا يستلزم أن يقع التكرار التالي في الحالة 3 مع ملوَّنًا بالأحمر. وعند دراسة الحالة 3 أدناه سنرى أن العملية تتوقف أثناء التكرار التالي.
Node<T> removeFixupCase1(Node<T> u) {
flipRight(u.parent);
return u;
}
الحالة 2: العقدة الشقيقة لـ ، وهي ، سوداء، و هي الابن الأيسر لأبيها . وفي هذه الحالة نستدعي ، فنجعل سوداء و حمراء، ونُغمق صبغة لتصبح سوداء أو سوداء مزدوجة. وعند هذه النقطة لا تستوفي خاصية الميل إلى اليسار، فنستدعي لتصحيح ذلك. وعند هذه النقطة تكون حمراء، وتكون هي جذر الشجرة الفرعية التي بدأنا بها. ونحتاج إلى فحص ما إذا كانت تسبّب مخالفة خاصية انعدام الحافة الحمراء. ونفعل ذلك بالنظر إلى الابن الأيمن لـ ، وهو . فإذا كانت سوداء، فإن تستوفي خاصية انعدام الحافة الحمراء، ويمكننا متابعة التكرار التالي مع . أما فيما عدا ذلك (أي إذا كانت حمراء)، فكلتا الخاصيتين، انعدام الحافة الحمراء والميل إلى اليسار، تكونان مخالفتين عند و على التوالي. وتُستعاد خاصية الميل إلى اليسار باستدعاء ، لكن خاصية انعدام الحافة الحمراء تبقى مخالفة. وعند هذه النقطة تكون هي الابن الأيسر لـ ، وتكون هي الابن الأيسر لـ ، وتكون و حمراوين معًا، وتكون سوداء أو سوداء مزدوجة. ويجعل من أبًا لكل من و . ويؤدي المتابعة باستدعاء إلى جعل كل من و أسود، وإعادة صبغة إلى الصبغة الأصلية لـ . وعند هذه النقطة تكون العقدة السوداء المزدوجة قد أُزيلت، وأُعيد تأسيس خاصيتي انعدام الحافة الحمراء وارتفاع الأسود. ولم يبقَ سوى مشكلة واحدة محتملة: قد يكون الابن الأيمن لـ أحمر، وعندئذ تُخالف خاصية الميل إلى اليسار. ونفحص ذلك وننفّذ لتصحيحه عند الحاجة.
Node<T> removeFixupCase2(Node<T> u) {
Node<T> w = u.parent;
Node<T> v = w.right;
pullBlack(w); // w.left
flipLeft(w); // w is now red
Node<T> q = w.right;
if (q.colour == red) { // q-w is red-red
rotateLeft(w);
flipRight(v);
pushBlack(q);
if (v.right.colour == red)
flipLeft(v);
return q;
} else {
return v;
}
}
الحالة 3: العقدة الشقيقة لـ سوداء، و هي الابن الأيمن لأبيها . وهذه الحالة متناظرة مع الحالة 2 وتُعالَج إلى حد كبير بالطريقة نفسها. والفرق الوحيد ينشأ من أن خاصية الميل إلى اليسار غير متناظرة، ولذلك تتطلب معالجة مختلفة. وكما سبق، نبدأ باستدعاء ، الذي يجعل حمراء و سوداء. ويؤدي استدعاء إلى ترقية إلى جذر الشجرة الفرعية. وعند هذه النقطة تكون حمراء، ويتفرّع الشيفرة في اتجاهين حسب صبغة الابن الأيسر لـ ، وهو . فإذا كانت حمراء، تنتهي الشيفرة تمامًا كما في الحالة 2، بل إنها أبسط لأنه لا خطر في ألا تستوفي خاصية الميل إلى اليسار. أما الحالة الأكثر تعقيدًا فتحدث عندما تكون سوداء. عندئذ نفحص صبغة الابن الأيسر لـ . فإذا كانت حمراء، فإن لها ابنان أحمران، ويمكن دفع الأسود الزائد منها إلى الأسفل باستدعاء . وعند هذه النقطة تكون قد عادت إلى صبغة الأصلية، وقد انتهينا. أما إذا كان الابن الأيسر لـ أسود، فإن تخالف خاصية الميل إلى اليسار، ونستعيدها باستدعاء . ثم نُعيد العقدة بحيث يكمل التكرار التالي لـ مع .
Node<T> removeFixupCase3(Node<T> u) {
Node<T> w = u.parent;
Node<T> v = w.left;
pullBlack(w);
flipRight(w); // w is now red
Node<T> q = w.left;
if (q.colour == red) { // q-w is red-red
rotateRight(w);
flipLeft(v);
pushBlack(q);
return q;
} else {
if (v.left.colour == red) {
pushBlack(v); // both v's children are red
return v;
} else { // ensure left-leaning
flipLeft(v);
return w;
}
}
}
ويستغرق كل تكرار لـ زمنًا ثابتًا. أما الحالتان 2 و3 فتُنهيان العمل أو تنقلان إلى قاعدة الشجرة. والحالة 0 (حيث هي الجذر) تنتهي دائمًا، وتنقل الحالة 1 فورًا إلى الحالة 3 التي تنتهي هي الأخرى. ولأن ارتفاع الشجرة على الأكثر ، نستنتج أن ثمة تكرارًا على الأكثر لـ ، لذا تعمل في . opendatastructures.org
9.3 الخلاصة
تلخّص النظرية التالية أداء بنية بيانات RedBlackTree: النظرية 9.1 تُنفِّذ RedBlackTree واجهة SSet وتدعم العمليات و و في في أسوأ الحالات لكل عملية.
ولا يشمل ما سبق هذه المكافأة الإضافية: النظرية 9.2 *إذا بدأنا من RedBlackTree فارغ، فإن أي تتابع من عملية و ينتج عن ذلك زمن إجمالي قدره مُنفقًا في مجمل استدعاءات و . *
ونكتفي هنا بمباشرة البرهان على النظرية 9.2. فبمقارنة و بخوارزميتَي إضافة ورقة أو إزالتها في شجرة 2-4، يمكننا أن نطمئن إلى أن هذه الخاصية موروثة من شجرة 2-4. وتحديدًا، إذا استطعنا أن نبيّن أن الزمن الإجمالي المُنفق في الانقسام والدمج والاستعارة في شجرة 2-4 هو ، فإن ذلك يستلزم النظرية 9.2. ويعتمد برهان هذه النظرية لأشجار 2-4 على طريقة الجهد (potential method) في التحليل المُستهلك (amortized analysis).9.2 نعرّف جهد العقدة الداخلية في شجرة 2-4 بأنه
ونعرّف جهد شجرة 2-4 بأنه مجموع إنجازات عُقدها. وعندما يحدث انقسام، فإن ذلك لأن عقدة ذات أربعة أبناء تتحوّل إلى عقدتين، إحداهما ذات ابنين والأخرى ذات ثلاثة أبناء. وهذا يعني أن الجهد الكلي ينخفض بمقدار . وعندما يحدث دمج، فإن عقدتين كانتا لكل منهما ابنان تُستبدلان بعقدة واحدة ذات ثلاثة أبناء. والنتيجة انخفاض في الجهد قدره . ومن ثمّ فإن كل انقسام أو دمج يُنقص الجهد بمقدار اثنين. ولاحظ بعد ذلك أنه، إذا تجاهلنا انقسام العُقد ودمجها، فإن ثمة عددًا ثابتًا فقط من العُقد يتغيّر عدد أبنائها بفعل إضافة ورقة أو إزالتها. وعند إضافة عقدة، يزيد عدد أبناء عقدة واحدة بمقدار واحد، أي يزداد الجهد بما لا يتجاوز ثلاثة. وخلال إزالة ورقة، ينقص عدد أبناء عقدة واحدة بمقدار واحد، أي يزداد الجهد بما لا يتجاوز واحدًا، وقد تشارك عقدتان في عملية استعارة واحدة، فيزداد مجموع جهدهما بما لا يتجاوز واحدًا. وباختصار، يُسبّب كل دمج وكل انقسام انخفاضًا في الجهد بما لا يقل عن اثنين. وتجاهلًا للدمج والانقسام، يُسبّب كل إضافة أو إزالة ارتفاعًا في الجهد بما لا يتجاوز ثلاثة، والجهد دائمًا غير سالب. ومن ثمّ فإن عدد عمليات الانقسام والدمج التي تُسبّبها عملية إضافة أو إزالة على شجرة فارغة في البداية هو على الأكثر. والنظرية 9.2 نتيجة لهذا التحليل وللعلاقة بين أشجار 2-4 وأشجار الأحمر والأسود.
الحواشي
... التحليل.9.2 انظر برهاني المبرهنة 2.2 والمبرهنة 3.1 لتطبيقات أخرى لطريقة الجهد. opendatastructures.org
9.4 مناقشة والتمارين
عُرِّفت أشجار الأحمر والأسود لأول مرة على يد Guibas وSedgewick [38]. ورغم ارتفاع تعقيد تنفيذها، فإنها موجودة في بعض المكتبات والتطبيقات الأكثر استخدامًا. وتناقش معظم الكتب المرجعية في الخوارزميات وبنى البيانات نوعًا ما من نسخ أشجار الأحمر والأسود. ويصف Andersson [6] نسخة من أشجار التوازن تميل إلى اليسار، وهي مشابهة لأشجار الأحمر والأسود لكن بقييد إضافي مفاده أن لكل عقدة ابنًا أحمر واحدًا على الأكثر. وهذا يستلزم أن تحاكي هذه الأشجار أشجار 2-3 بدلًا من أشجار 2-4. وهي أبسط بكثير مع ذلك من بنية RedBlackTree المعروضة في هذا الفصل. ويصف Sedgewick [66] نسختين من أشجار الأحمر والأسود المائلة إلى اليسار. وتستخدمان التكرار (recursion) مع محاكاة للانقسام والدمج من الأعلى إلى الأسفل في أشجار 2-4. ودمج هاتين التقنيتين ينتج شيفرة قصيرة وأنيقة بشكل لافت. وبنية بيانات ذات صلة وأقدم هي شجرة AVL [3]. وأشجار AVL متوازنة الارتفاع (height-balanced): عند كل عقدة ، يكون ارتفاع الشجرة الفرعية التي جذورها عند والشجرة الفرعية التي جذورها عند مختلفين بما لا يتجاوز واحدًا. ويترتب على ذلك فورًا أنه، إذا كان أصغر عدد من الأوراق في شجرة ارتفاعها ، فإن يتبع متتالية فيبوناتشي
مع الحالتين الأساس و . وهذا يعني أن تساوي تقريبًا ، حيث هي النسبة الذهبية (golden ratio). (وبدقة أكبر، .) وبالحجج نفسها المستخدمة في برهان المبرهنة 9.1، فإن هذا يستلزم
لذلك فإن لأشجار AVL ارتفاعًا أصغر من أشجار الأحمر والأسود. ويمكن صيانة توازن الارتفاع أثناء عمليتي و بالعودة صعودًا عبر المسار إلى الجذر، وتنفيذ عملية إعادة توازن (rebalancing) عند كل عقدة يختلف عندها ارتفاع الشجرتين الفرعيتين لـ بمقدار اثنين. انظر الشكل 9.10.
الشكل 9.10: إعادة التوازن في شجرة AVL. لا يلزم أكثر من دوران لتحويل عقدة شجرتاها الفرعيتان ارتفاعهما و إلى عقدة شجرتاها الفرعيتان ارتفاع كل منهما على الأكثر . 
التمرين 9.1 ارسم شجرة 2-4 المقابلة لـ RedBlackTree في الشكل 9.11.
التمرين 9.2 ارسم إضافة 13، ثم 3.5، ثم 3.3 على RedBlackTree في الشكل 9.11.
التمرين 9.3 ارسم إزالة 11، ثم 9، ثم 5 من RedBlackTree في الشكل 9.11.
التمرين 9.4 بيّن أنه، مهما كانت قيم كبيرة، توجد أشجار أحمر وأسود ذات عقدة ارتفاعها .
التمرين 9.5 خُذ العمليتين و بعين الاعتبار. ماذا تفعلان هاتان العمليتان بشجرة 2-4 الكامنة التي تحاكيها شجرة الأحمر والأسود؟
التمرين 9.6 بيّن أنه، مهما كانت قيم كبيرة، توجد تتابعات من عمليات و تؤدي إلى أشجار أحمر وأسود ذات عقدة ارتفاعها .
التمرين 9.7 لماذا تُجري طريقة في تنفيذ RedBlackTree الإسناد ؟ ألم يكن الاستدعاء إلى قد قام به بالفعل؟
التمرين 9.8 افترض أن شجرة 2-4، ، لها ورقة و عقدة داخلية. فما أصغر قيمة لـ ، كدالة في ؟ وما أكبر قيمة لـ ، كدالة في ؟ وإذا كانت شجرة أحمر وأسود تمثّل ، فكم عدد العُقد الحمراء في ؟
التمرين 9.9 افترض أنك أعطيت شجرة بحث ثنائي ذات عقدة وارتفاع على الأكثر . هل من الممكن دائمًا تلوين العُقد بالأحمر والأسود بحيث تستوفي الشجرة خاصيتي ارتفاع الأسود وانعدام الحافة الحمراء؟ وإذا كان الأمر كذلك، فهل يمكن أيضًا جعلها تستوفي خاصية الميل إلى اليسار؟
التمرين 9.10 افترض أن لديك شجرتَي أحمر وأسود، و ، لهما ارتفاع الأسود نفسه، ، بحيث يكون أكبر مفتاح في أصغر من أصغر مفتاح في . بيّن كيف تدمج و في شجرة أحمر وأسود واحدة في .
التمرين 9.11 وسّع حلك للتمرين 9.10 ليشمل الحالة التي تكون فيها شجرتا و لهما ارتفاعا الأسود مختلفين، . وينبغي أن يكون زمن التنفيذ .
التمرين 9.12 اثبت أن شجرة AVL يجب أن تنفّذ، أثناء عملية ، على الأكثر عملية إعادة توازن واحدة (تتضمّن على الأكثر دورانين؛ انظر الشكل 9.10). واعطِ مثالًا على شجرة AVL وعملية على تلك الشجرة تتطلب من رتبة عملية إعادة توازن.
التمرين 9.13 نفّذ صنف AVLTree الذي ينفّذ أشجار AVL على النحو الموصوف أعلاه. وقارن أدائه بأداء تنفيذ RedBlackTree. فأيّ التنفيذين أسرع في عملية ؟
التمرين 9.14 صمّم ونفّذ سلسلة تجارب تقارن الأداء النسبي للعمليات و و في تنفيذات واجهة SSet وهي SkiplistSSet وScapegoatTree وTreap وRedBlackTree. واحرص على تضمين سيناريوهات اختبار متعددة، منها الحالات التي تكون فيها البيانات عشوائية، أو مرتبة سلفًا، أو تُزال بترتيب عشوائي، أو تُزال بترتيب مرتب، وغيرها.