8. أشجار الكبش الفداء
في هذا الفصل، ندرس بنية بيانات من نوع شجرة البحث الثنائية (binary search tree)، وهي ScapegoatTree. تقوم هذه البنية على الحكمة الشائعة بأنّه، حين يسوء شيءٌ ما، فإنّ أوّل ما يلجأ إليه الناس هو البحث عن من يُلام (كبش الفداء). ومتى ثبتت المسؤولية، يتركون كبش الفداء ليصلح المشكلة. تحافظ ScapegoatTree على توازنها عبر عمليات إعادة البناء الجزئية (partial rebuilding). وأثناء عملية إعادة البناء الجزئية، تُفكَّك شجرة فرعية كاملة وتُعاد بناؤها من جديد كشجرة فرعية متوازنة تمامًا. وهناك طرق كثيرة لإعادة بناء الشجرة الفرعية ذات الجذر لتصبح شجرة متوازنة تمامًا. وأبسط هذه الطرق هو اجتياز الشجرة الفرعية ذات الجذر وجمع جميع عقدها في مصفوفة، ، ثم بناء شجرة فرعية متوازنة على نحو تعاودي (recursive) باستخدام . فإذا جعلنا ، فإنّ العنصر يصبح جذر الشجرة الفرعية الجديدة، وتُخزَّن على نحو تعاودي في الشجرة الفرعية اليسرى، وتُخزَّن على نحو تعاودي في الشجرة الفرعية اليمنى.
void rebuild(Node<T> u) {
int ns = size(u);
Node<T> p = u.parent;
Node<T>[] a = (Node<T>[]) Array.newInstance(Node.class, ns);
packIntoArray(u, a, 0);
if (p == nil) {
r = buildBalanced(a, 0, ns);
r.parent = nil;
} else if (p.right == u) {
p.right = buildBalanced(a, 0, ns);
p.right.parent = p;
} else {
p.left = buildBalanced(a, 0, ns);
p.left.parent = p;
}
}
int packIntoArray(Node<T> u, Node<T>[] a, int i) {
if (u == nil) {
return i;
}
i = packIntoArray(u.left, a, i);
a[i++] = u;
return packIntoArray(u.right, a, i);
}
Node<T> buildBalanced(Node<T>[] a, int i, int ns) {
if (ns == 0)
return nil;
int m = ns / 2;
a[i + m].left = buildBalanced(a, i, m);
if (a[i + m].left != nil)
a[i + m].left.parent = a[i + m];
a[i + m].right = buildBalanced(a, i + m + 1, ns - m - 1);
if (a[i + m].right != nil)
a[i + m].right.parent = a[i + m];
return a[i + m];
}
يستغرق استدعاء زمنًا مقداره . أمّا الشجرة الفرعية الناتجة فإنّ لها أصغر ارتفاع ممكن؛ إذ لا توجد شجرة ذات ارتفاع أصغر تحوي عقدة.
الأقسام الفرعية
8.1 ScapegoatTree: شجرة بحث ثنائية مع إعادة بناء جزئية
الأقسام الفرعية
8.1 ScapegoatTree: شجرة بحث ثنائية مع إعادة بناء جزئية
إنّ ScapegoatTree هي BinarySearchTree، وهي إضافةً إلى تتبّع العدد للعقد في الشجرة، تحتفظ بعدّاد يحافظ على حدّ أعلى (upper bound) لعدد العقد.
int q;
في كل الأوقات، يطيع و المتراجحتَين التاليتين:
إضافةً إلى ذلك، فإنّ ارتفاع ScapegoatTree لوغاريتمي؛ وفي كل الأوقات لا يتجاوز ارتفاع شجرة كبش الفداء
حتى مع هذا القيد، قد تبدو ScapegoatTree غير متوازنة على نحوٍ مفاجئ. فشجرة الشكل 8.1 تحوي وارتفاعها .
الشكل 8.1: ScapegoatTree تحوي 10 عقد وارتفاعها 5. 
يُنفَّذ تنفيذ العملية في ScapegoatTree باستخدام الخوارزمية المعيارية للبحث في BinarySearchTree (راجع القسم 6.2). وهذا يستغرق زمنًا متناسبًا مع ارتفاع الشجرة الذي، بحسب (8.1)، هو . ولتنفيذ العملية ، نزيد أوّلًا و ثم نستخدم الخوارزمية المعتادة لإضافة إلى شجرة بحث ثنائية؛ فنبحث عن ثم نضيف ورقة جديدة بحيث . وفي هذه المرحلة قد نكون محظوظين، فقد لا يتجاوز عمق القيمة . وإن كان الأمر كذلك، فاتركنا الحال على حالها ولم نفعل شيئًا آخر. لكن للأسف، سيحدث أحيانًا أنّ . وفي هذه الحالة، نحتاج إلى تقليل الارتفاع. وليست هذه عملًا كبيرًا؛ إذ لا توجد سوى عقدة واحدة، وهي ، يتجاوز عمقها . ولإصلاح ، نصعد من عائدين إلى الجذر باحثين عن كبش فداء، . إنّ كبش الفداء هو عقدة شديدة اللاتوازن، وله الخاصية التالية
حيث هو الابن الذي يلي على المسار الممتد من الجذر إلى . وسنبرهن بعد قليلٍ على أنّ كبش فداء موجود. أمّا الآن فيمكننا التسليم بذلك. وبعد أن نجد كبش الفداء ، نهدم تمامًا الشجرة الفرعية ذات الجذر ونعيد بناؤها كشجرة بحث ثنائية متوازنة تمامًا. ومن المعادلة (8.2) نعلم أنّه حتى قبل إضافة لم تكن الشجرة الفرعية ذات الجذر شجرة ثنائية كاملة. ومن ثمّ، عندما نعيد بناء ، ينخفض الارتفاع بمقدار 1 على الأقل، بحيث يعود ارتفاع ScapegoatTree إلى ما لا يتجاوز .
boolean add(T x) {
// first do basic insertion keeping track of depth
Node<T> u = newNode(x);
int d = addWithDepth(u);
if (d > log32(q)) {
// depth exceeded, find scapegoat
Node<T> w = u.parent;
while (3*size(w) <= 2*size(w.parent))
w = w.parent;
rebuild(w.parent);
}
return d >= 0;
}
إذا أهملنا كلفة العثور على كبش الفداء وإعادة بناء الشجرة الفرعية ذات الجذر ، فإنّ زمن تشغيل يهيمن عليه البحث الأوّلي، الذي يستغرق من الزمن. أمّا كلفة العثور على كبش الفداء وإعادة البناء فسنحاسبها في القسم التالي باستخدام التحليل المُلبَّد (amortized analysis). وتنفيذ عملية في ScapegoatTree بسيطٌ جدًّا. فنبحث عن ونزيله باستخدام الخوارزمية المعتادة لإزالة عقدة من BinarySearchTree. (ولاحظ أنّ ذلك لا يمكنه إطلاقًا أن يزيد من ارتفاع الشجرة.) ثمّ نقص مع الإبقاء على دون تغيير. وأخيرًا نتحقّق ممّا إذا كان ، فإن كان كذلك أعدنا بناء الشجرة بأكملها كشجرة بحث ثنائية متوازنة تمامًا وضبطنا .
boolean remove(T x) {
if (super.remove(x)) {
if (2*n < q) {
rebuild(r);
q = n;
}
return true;
}
return false;
}
ومرّة أخرى، إذا أهملنا كلفة إعادة البناء، فإنّ زمن تشغيل العملية متناسب مع ارتفاع الشجرة، ومن ثمّ فهو .
8.1.1 تحليل صحّة العمليات وزمن تشغيلها في هذا القسم، نحلّل صحّة العمليات على ScapegoatTree وزمن تشغيلها المُلبَّد. ونبرهن أوّلًا على الصحّة بأنّنا نبيّن أنّه، عندما ينتج عن العملية عقدة تنتهك الشرط (8.1)، فإنّنا نستطيع دائمًا العثور على كبش فداء: الملمّة 8.1 *ليكن عقدة عمقها في ScapegoatTree. عندئذٍ توجد عقدة على المسار الممتد من إلى الجذر بحيث *
البرهان. نفترض، طلبًا للتناقض، أنّ الأمر ليس كذلك، وأنّ
يسري ذلك لكل العقد على المسار الممتد من إلى الجذر. لنُسمِّ المسار الممتد من الجذر إلى بالرمز . عندئذٍ لدينا ، ، وبشكلٍ عامّ
لكنّ هذا يعطي تناقضًا، إذ إنّ ، ومن ثمّ
تالًا، نحلّل جزأَي زمن التشغيل اللذين لم نحتسبهما بعد. هناك جزأان: كلفة الاستدعاءات إلى عند البحث عن عقد كبش الفداء، وكلفة الاستدعاءات إلى عند العثور على كبش فداء . ويمكن ربط كلفة الاستدعاءات إلى بكلفة الاستدعاءات إلى على النحو التالي: الملمّة 8.2 أثناء استدعاء في ScapegoatTree، تكون كلفة العثور على كبش الفداء وإعادة بناء الشجرة الفرعية ذات الجذر هي .
البرهان. كلفة إعادة بناء عقدة كبش الفداء ، بعد العثور عليها، هي . وعند البحث عن عقدة كبش الفداء، نستدعي على تسلسلٍ من العقد حتى نجد كبش الفداء . لكنّ أوّل عقدة في هذا التسلسل تُعدّ كبش فداء، ومن ثمّ نعلم أنّ
يسري ذلك لكل . إذن، كلفة جميع الاستدعاءات إلى هي
 |
|||
حيث يتبع السطر الأخير من أنّ المجموع متتاليةٌ هابطة هندسيًا.
لم يبقَ سوى إثبات حدٍّ أعلى (upper bound) لكلفة جميع الاستدعاءات إلى خلال تسلسلٍ من عملية: الملمّة 8.3 إذا بدأنا من ScapegoatTree فارغة، فإنّ أي تسلسلٍ من عملية من نوعَي و يستهلك على الأكثر من الزمن في عمليات .
البرهان. لإثبات ذلك، سنستخدم مخطّط أرصدة (credit scheme). نتخيّل أنّ كل عقدة تخزّن عددًا من الأرصدة. ويمكن لكل رصيدٍ أن يدفع ثمن ثابتٍ، ، من وحدات الزمن التي تُنفق في إعادة البناء. ويوزّع هذا المخطّط ما مجموعه من الأرصدة، ويُدفَع كل استدعاء إلى بالأرصدة المخزَّنة عند .
أثناء الإدراج أو الحذف، نمنح رصيدًا واحدًا لكل عقدةٍ على المسار المؤدّي إلى العقدة المُدرَجة أو المحذوفة، . وبهذه الطريقة نوزّع على الأكثر رصيدًا لكل عملية. وأثناء الحذف نحتفظ برصيدٍ إضافي مُدَّخرًا إلى جانب. وعليه، فإنّ ما نوزّعه إجمالًا لا يتجاوز من الأرصدة. ولم يبقَ سوى بيان أنّ هذه الأرصدة تكفي لدفع كلفة جميع الاستدعاءات إلى . فإذا استدعينا أثناء إدراج، فإنّ ذلك لأنّ كبش فداء. ولنفترض، دون تضييقٍ من العموم، أنّ
باستخدام الحقيقة
نستنتج أنّ
وبالتالي
والآن، في آخر مرّةٍ أُعيدت فيها بناء شجرةٍ فرعية تحوي (أو حين أُدرجت ، إن لم تُعَد بناء شجرةٍ فرعية تحوي قطّ)، كان لدينا
لذلك فإنّ عدد عمليات أو التي أثّرت في أو منذ ذلك الحين لا يقلّ عن
ومن ثمّ فإنّ عددًا من الأرصدة لا يقلّ عن هذا العدد مخزَّنٌ عند ، ومتاح لدفع الزمن الذي يستغرقه استدعاء .
أمّا إذا استدعينا أثناء حذف، فإنّ ذلك لأنّ . في هذه الحالة لدينا من الأرصدة المخزَّنة ``مُدَّخرة إلى جانب،'' ونستخدمها لدفع الزمن الذي يلزم لإعادة بناء الجذر. وبهذا يكتمل البرهان.
8.1.2 الخلاصة تلخّص المبرهنة التالية أداء بنية بيانات ScapegoatTree: المبرهنة 8.1 *تُنفِّذ ScapegoatTree واجهة SSet. وإذا أهملنا كلفة عمليات ، فإنّ ScapegoatTree تدعم العمليات و و في زمنٍ قدره لكل عملية. * وإضافةً إلى ذلك، فإنّ البدء من ScapegoatTree فارغة يُسبّب أي تسلسلٍ من عملية من نوعَي و إنفاقًا إجماليًا قدره من الزمن خلال جميع الاستدعاءات إلى .
8.2 مناقشة والتمارين
مصطلح «شجرة كبش الفداء» يعود إلى Galperin وRivest [33] اللذين عرّفا هذه الأشجار وحلّلاها. غير أنّ البنية ذاتها اكتشفها في وقتٍ أسبق Andersson [5,7]، وسمّاها أشجارًا متوازنة عامّة (general balanced trees) لأنّها يمكن أن تأخذ أيّ شكل ما دام ارتفاعها صغيرًا. وستُظهر التجارب مع تنفيذ ScapegoatTree أنّه كثيرًا ما يكون أبطأ بدرجةٍ كبيرة من عمليات SSet الأخرى في هذا الكتاب. وقد يبدو هذا مثيرًا للدهشة إلى حدٍّ ما، لأنّ حدّ الارتفاع
أفضل من الطول المتوقَّع لمسار البحث في Skiplist وليس بعيدًا جدًّا عن نظيره في Treap. ويمكن تحسين التنفيذ إمّا بتخزين أحجام الشجرات الفرعية صراحةً عند كل عقدة، أو بإعادة استخدام أحجام الشجرات الفرعية المحسوبة سلفًا (التمرينان 8.5 و8.6). وحتى مع هذه التحسينات، ستظلّ هناك دائمًا تسلسلاتٌ من عمليات و التي تستغرق فيها ScapegoatTree زمنًا أطول من عمليات SSet الأخرى.
وهذه الفجوة في الأداء تعود إلى أنّ ScapegoatTree، بخلاف عمليات SSet الأخرى المتناوَشة في هذا الكتاب، يمكن أن تقضي وقتًا طويلًا في إعادة ترتيب بنيتها. ويطلب منك التمرين 8.3 إثبات أنّ هناك تسلسلاتٍ من عملية تستهلك فيها ScapegoatTree زمنًا من المرتبة في الاستدعاءات إلى . وهذا على عكس ما في عمليات SSet الأخرى المتناوَشة في هذا الكتاب، فإنّها لا تنجز سوى من التغييرات البنيوية خلال تسلسلٍ من عملية. وهذا، للأسف، نتيجةٌ لازمة عن كون ScapegoatTree تنجز كل إعادة ترتيب لبنيتها عبر استدعاءات إلى [20]. وعلى الرغم من ضعف أدائها، هناك تطبيقات قد تكون فيها ScapegoatTree هي الخيار الصحيح. ويحدث ذلك كلّما كانت هناك بياناتٌ إضافية مرتبطةٌ بعقدٍ لا يمكن تحديثها في زمنٍ ثابت عند إجراء دورانٍ (rotation)، لكن يمكن تحديثها أثناء عملية . وفي هذه الحالات قد تنفع ScapegoatTree والبنيات المرتبطة القائمة على إعادة البناء الجزئي. ويعرض التمرين 8.11 مثالًا على تطبيقٍ من هذا النوع. التمرين 8.1 بيّن إضافة القيمة 1.5 ثم القيمة 1.6 على ScapegoatTree في الشكل 8.1.
التمرين 8.2 بيّن ما يحدث عند إضافة التسلسل إلى ScapegoatTree فارغة، وأظهر أين تذهب الأرصدة الموصوفة في برهان الملمة 8.3، وكيف تُستخدَم خلال تسلسل الإضافات هذا.
التمرين 8.3 بيّن أنّه، إذا بدأنا من ScapegoatTree فارغة واستدعينا لكل ، فإنّ الزمن الإجمالي المنفق في الاستدعاءات إلى لا يقلّ عن من أجل ثابتٍ ما .
التمرين 8.4 تضمن ScapegoatTree الموصوفة في هذا الفصل أن ألّا يتجاوز طول مسار البحث . صمّم وحلّل ونفّذ نسخةً معدَّلة من ScapegoatTree يكون فيها طول مسار البحث لا يتجاوز ، حيث معاملٌ يحقّق . ماذا يخبرك تحليلك و/أو تجاربك عن الكلفة المُلبَّدة لـ و و دالّةً في و ؟
التمرين 8.5 عدّل الدالة في ScapegoatTree بحيث لا تُهدر أي وقت في إعادة حساب أحجام الشجرات الفرعية التي حُسبت من قبل. وهذا مُمكن لأنّ الدالة، حين ترغب في حساب ، تكون قد حسبت بالفعل أحد أو . وقارن بين أداء تنفيذك المعدَّل وأداء التنفيذ المعطى هنا.
التمرين 8.6 نفّذ نسخةً ثانية من بنية بيانات ScapegoatTree تخزّن أحجام الشجرة الفرعية ذات الجذر عند كل عقدة صراحةً وتحافظ عليها. وقارن بين أداء التنفيذ الناتج وأداء تنفيذ ScapegoatTree الأصلي، وكذلك أداء التنفيذ الخاص بالتمرين 8.5.
التمرين 8.7 أعد تنفيذ الدالة التي نُوقشت في مطلع هذا الفصل بحيث لا تتطلّب استخدام مصفوفة لتخزين عقد الشجرة الفرعية قيد إعادة البناء. وبدلًا من ذلك، ينبغي أن تستخدم التكرار (recursion) لربط العقد أوّلًا في قائمةٍ مترابطة، ثم تحويل هذه القائمة المترابطة إلى شجرة ثنائية متوازنة تمامًا. (وهناك تنفيذان تعاوديان بديعان جدًّا لكلتا الخطوتين.)
التمرين 8.8 حلّل ونفّذ WeightBalancedTree. وهذه شجرةٌ تحافظ فيها كل عقدة ، ما عدا الجذر، على ثابت اتزان (balance invariant) هو . وعمليتا و مطابقتان لعمليتي BinarySearchTree المعياريتين، إلّا أنّه كلّما انتُكِث ثابت الاتزان عند عقدة ، أُعيد بناء الشجرة الفرعية ذات الجذر . وينبغي أن يُظهر تحليلك أنّ العمليات على WeightBalancedTree تعمل في زمنٍ مُلبَّد قدره .
التمرين 8.9 حلّل ونفّذ CountdownTree. وفي CountdownTree تحتفظ كل عقدة بعدّادٍ تنازلي . وعمليتا و مطابقتان تمامًا لتلك في BinarySearchTree المعياري، إلّا أنّه كلّما أثّرت إحدى هاتين العمليتين في الشجرة الفرعية ذات الجذر ، نُقص . وعندما يصبح تُعاد الشجرة الفرعية ذات الجذر بناءً كاملًا لتصبح شجرة بحث ثنائية متوازنة تمامًا. وعندما تكون عقدة مشتركة في عملية إعادة بناء (إمّا لأنّ هي التي أُعيد بناؤها أو لأنّ أحد أجداد أُعيد بناؤه)، يُعاد ضبط على . وينبغي أن يُظهر تحليلك أنّ العمليات على CountdownTree تعمل في زمنٍ مُلبَّد قدره . (تلميح: بيّن أوّلًا أنّ كل عقدة تحقّق نسخةً ما من ثابت الاتزان.)
التمرين 8.10 حلّل ونفّذ DynamiteTree. وفي DynamiteTree تتتبّع كل عقدة حجمَ الشجرة الفرعية ذات جذر في متغيّر . وعمليتا و مطابقتان تمامًا لتلك في BinarySearchTree المعياري، إلّا أنّه كلّما أثّرت إحدى هاتين العمليتين في الشجرة الفرعية لعقدة ، انفجرت باحتمال . وحين تنفجر ، تُعاد شجرتها الفرعية بناءً كاملًا لتصبح شجرة بحث ثنائية متوازنة تمامًا. وينبغي أن يُظهر تحليلك أنّ العمليات على DynamiteTree تعمل في زمنٍ متوقَّع قدره .
التمرين 8.11 صمّم ونفّذ بنية بيانات Sequence تحافظ على تسلسلٍ (قائمة) من العناصر. وهي تدعم العمليات التالية: : أضف عنصرًا جديدًا بعد العنصر في التسلسل، وأعِد العنصر المُضاف حديثًا. (وإن كان فارغًا (null)، فيُضاف العنصر الجديد في مطلع التسلسل.) : أزل من التسلسل. : أعِد إذا وفقط إذا كان يسبق في التسلسل. وينبغي أن تعمل العمليتان الأوليان في زمنٍ مُلبَّد قدره . أمّا العملية الثالثة فينبغي أن تعمل في زمنٍ ثابت. ويمكن تنفيذ بنية بيانات Sequence بتخزين العناصر في شيءٍ من قبيل ScapegoatTree، بالترتيب نفسه الذي ترد فيه في التسلسل. ولتنفيذ في زمنٍ ثابت، يُوسَم كل عنصر بعددٍ صحيحٍ يُرمِّز المسار من الجذر إلى . وبهذه الطريقة يمكن تنفيذ بمقارنة وسمَي و .