7. أشجار البحث الثنائية العشوائية
في هذا الفصل، نقدّم بنية شجرة بحث ثنائية (binary search tree) تستخدم التوزيع العشوائي (randomization) لتحقيق زمن متوقَّع (expected time) لكل العمليات.
الأقسام الفرعية
7.1 الأشجار الثنائية للبحث العشوائي
الأقسام الفرعية
7.1 الأشجار الثنائية للبحث العشوائي
تأمّل الشجرتين الثنائيتين للبحث الظاهرتين في الشكل 7.1، ولكلٍّ منهما عقدة. إنّ الشجرة على اليسار هي قائمة (list)، والأخرى شجرة بحث ثنائية متوازنة تمامًا. أمّا ارتفاع الشجرة على اليسار فهو ، وارتفاع الشجرة على اليمين ثلاثة. الشكل 7.1: شجرتان ثنائيتان للبحث تحتويان على الأعداد الصحيحة . 
تخيّل كيف أمكن بناء هاتين الشجرتين. فالشجرة على اليسار تنتَج إذا ما بدأنا من BinarySearchTree فارغ وأضفنا التسلسل
لا يوجد أي تسلسل إضافات آخر يولّد هذه الشجرة (ويمكنك إثبات ذلك بالاستدلال على ). وفي المقابل، يمكن توليد الشجرة على اليمين عن طريق التسلسل
وتسلسلات أخرى تعمل أيضًا، ومنها
و
وفي الواقع، هناك تسلسل إضافات يولّد الشجرة على اليمين، وتسلسل واحد فقط يولّد الشجرة على اليسار.
يقدّم المثال السابق بعض الأدلة التجريبية على أنّه، إن اخترنا تبديلًا عشوائيًا (random permutation) لـ وأضفناه إلى شجرة بحث ثنائية، فإنّنا أميل إلى الحصول على شجرة متوازنة جدًّا (جانب الشكل 7.1 الأيمن) أكثر من ميلنا إلى الحصول على شجرة غير متوازنة البتّة (جانب الشكل 7.1 الأيسر). ويمكننا ترسيخ هذه الفكرة بدقّة بدراسة الأشجار الثنائية للبحث العشوائية. وتُحصل شجرة البحث الثنائية العشوائية (random binary search tree) ذات الحجم بالطريقة التالية: خُذ تبديلًا عشوائيًا، ، للأعداد الصحيحة وأضف عناصره واحدًا تلو الآخر إلى BinarySearchTree. وبـ«التبديل العشوائي» نعني أنّ كلًّا من التبديلات (الترتيبات) الممكنة وعددها لـ محتمِلة بالقدر نفسه، بحيث يكون احتمال الحصول على أيّ تبديل بعينه هو . ولاحظ أنّ القيم يمكن استبدالها بأي مجموعة مرتَّبة (ordered set) من عنصرًا دون أن يتغيّر أيٌّ من خصائص شجرة البحث الثنائية العشوائية. فالعنصر ما هو إلا تمثيل للعنصر ذي الرتبة (rank) في مجموعة مرتَّبة ذات حجم . وقبل أن نعرض نتيجتنا الرئيسة عن الأشجار الثنائية للبحث العشوائية، لا بدّ من أن نتوقّف قليلًا عند استطراد قصير نتناول فيه نوعًا من الأعداد يتكرّر كثيرًا عند دراسة البنى العشوائية. فبالنسبة إلى عدد صحيح غير سالب، ، يُعرَّف العدد التوافقي (harmonic number) رقم ، ويُرمَز إليه بـ ، بالتعريف
وليس للعدد التوافقي صيغة مغلقة بسيطة، لكنه يرتبط ارتباطًا وثيقًا جدًّا باللوغاريتم الطبيعي (natural logarithm) لـ . وبخاصة،
ولعلّ من درس التفاضل والتكامل أن يلاحظ أنّ السبب في ذلك هو التكامل . وإذا تذكّرنا أنّ التكامل يمكن تفسيره كمساحة محصورة بين منحنى ومحور ، أمكننا وضع حدٍّ أدنى (lower bound) لقيمة يساوي التكامل ، وحدٍّ أعلى (upper bound) يساوي . (راجع الشكل 7.2 لشرحٍ بياني.)
الشكل 7.2: العدد التوافقي رقم ، أي ، محدود من أعلى ومنأسفل بتكاملَين. فقيمة هذين التكاملَين تُعطى بمساحة المنطقة المظلَّلة، بينما قيمة تُعطى بمساحة المستطيلات. 
الملمّة 7.1 *في شجرة بحث ثنائية عشوائية ذات حجم ، تنطبق العبارتان التاليتان: * لأي ، يكون الطول المتوقَّع لمسار البحث عن هو .7.1 لأي ، يكون الطول المتوقَّع لمسار البحث عن هو .
سنبرهن على الملمة 7.1 في القسم التالي. أمّا الآن، فلننظر فيما تخبرنا به الجزأان من الملمة 7.1. فأمّا الجزء الأول فيخبرنا أنّه إذا بحثنا عن عنصر في شجرة ذات حجم ، فإنّ الطول المتوقَّع لمسار البحث يساوي على الأكثر . وأمّا الجزء الثاني فيخبرنا بالأمر نفسه عند البحث عن قيمة غير مخزَّنة في الشجرة. وعندما نقارن بين جزأَي الملمة، نرى أنّ البحث عن شيءٍ موجود في الشجرة أسرع قليلًا فقط ممّا هو عليه البحث عن شيءٍ ليس فيها. 7.1.1 برهان الملمة 7.1 الملاحظة المفتاحية اللازمة لبرهان الملمة 7.1 هي التالية: يحتوي مسار البحث عن قيمة تقع في الفترة المفتوحة في شجرة بحث ثنائية عشوائية، ، على العقدة ذات المفتاح إذا وفقط إذا، في التبديل العشوائي المستخدَم لإنشاء ، كان يظهر قبل أيٍّ من . ولمعرفة ذلك، راجع الشكل 7.3 ولاحظ أنّه إلى أن تُضاف قيمة ما في ، تكون مسارات البحث عن كل قيمة في الفترة المفتوحة متطابقة. (وتذكّر أنّه كي تختلف مسارات البحث عن قيمتين، لا بدّ من وجود عنصر في الشجرة يُقارَن بهما على نحو مختلف.) وليكن أول عنصر في يظهر في التبديل العشوائي. لاحظ أنّ أصبح الآن، وسيظلّ دائمًا، على مسار البحث عن . فإن كان فإنّ العقدة التي تحوي تُنشأ قبل العقدة التي تحوي . وفي وقتٍ لاحق، عند إضافة ، ستُضاف إلى الشجرة الفرعية (subtree) التي جذورها هو ، لأنّ . ومن جهة أخرى، لن يزور مسار البحث عن هذه الشجرة الفرعية أبدًا، لأنّه سينتقل إلى بعد زيارة . الشكل 7.3: القيمة تكون على مسار البحث عن إذا وفقط إذا كانت أول عنصر ضمن يُضاف إلى الشجرة. 
وبالمثل، فإنّ تُدرَج في مسار البحث عن إذا وفقط إذا ظهرت قبل أيٍّ من في التبديل العشوائي المستخدَم لإنشاء . ولاحظ أنّه إذا بدأنا بتبديل عشوائي لـ ، فإنّ المتتاليات الجزئية التي لا تحتوي سوى و هي أيضًا تبديلات عشوائية لعناصرها على التوالي. وعليه، فإنّ كل عنصر ضمن المجموعتين و محتمَل بالقدر نفسه أن يسبق أيّ عنصر آخر في مجموعته ضمن التبديل العشوائي المستخدَم لإنشاء . ومن ثمّ لدينا
وبهذه الملاحظة، ينطوي برهان الملمة 7.1 على بعض الحسابات البسيطة بالأعداد التوافقية:
البرهان. [برهان الملمة 7.1] وليكن متغيّرًا عشوائيًا إشاريًا (indicator random variable) يساوي واحدًا عندما يظهر على مسار البحث عن ، وصفرًا في غير ذلك. وعندئذٍ يكون طول مسار البحث معطىً بـ
فإذا كان ، كان الطول المتوقَّع لمسار البحث معطىً بـ (راجع الشكل 7.4.a)
 |
||
|---|---|---|
 |
||
 |
||
والحسابات المقابلة لقيمة بحث تكاد تكون مطابقة (راجع الشكل 7.4.b).
الشكل 7.4: احتمالات وجود عنصر على مسار البحث عن عندما (a) يكون عددًا صحيحًا، و(b) عندما لا يكون عددًا صحيحًا. 
(b) 7.1.2 الخلاصة تلخّص المبرهنة التالية أداء شجرة البحث الثنائية العشوائية: المبرهنة 7.1 يمكن إنشاء شجرة بحث ثنائية عشوائية في زمن . وفي شجرة البحث الثنائية العشوائية، تستغرق العملية زمنًا متوقَّعًا قدره .
وينبغي أن نؤكّد مجدّدًا أنّ التوقّع في المبرهنة 7.1 محسوب بالنسبة إلى التبديل العشوائي المستخدَم لإنشاء شجرة البحث الثنائية العشوائية. وبخاصة، فهو لا يعتمد على اختيار عشوائي لـ ؛ بل هو صحيح لكل قيمة من قيم .
الحواشي
....7.1 يمكن تفسير التعبيرَين و على التوالي بأنهما عدد العناصر في الشجرة الأصغر من أو المساوية له، وعدد العناصر في الشجرة الأكبر من أو المساوية له. opendatastructures.org
7.2 Treap: شجرة بحث ثنائية عشوائية
الأقسام الفرعية
7.2 Treap: شجرة بحث ثنائية عشوائية
المشكلة في الأشجار الثنائية للبحث العشوائية أنّها بطبيعتها غير ديناميكية (dynamic). فهي لا تدعم العمليتَين و اللتين تلزمان لتنفيذ واجهة SSet. وفي هذا القسم نشرح بنية بيانات تُدعى Treap تستخدم الملمة 7.1 لتنفيذ واجهة SSet.7.2 إنّ عقدة في Treap تشبه عقدة في BinarySearchTree من حيث أنّها تحمل قيمة بيانات، ، كما أنّها تحتوي أيضًا على أولوية (priority) عددية فريدة، ، تُسنَد عشوائيًا:
class Node<T> extends BinarySearchTree.BSTNode<Node<T>,T> {
int p;
}
إلى جانب كونه شجرة بحث ثنائية، تلتزم عقد الـTreap أيضًا بخاصية الكومة (heap property):
- (خاصية الكومة) عند كل عقدة ، باستثناء الجذر، .
بعبارة أخرى، لكل عقدة أولوية أصغر من أولوية طفليها. ويبيّن الشكل 7.5 مثالًا على ذلك.
الشكل 7.5: مثال على Treap يحوي الأعداد الصحيحة . كل عقدة، ، موصوفة بصندوق يحتوي . 
ويضمن شرطا الكومة وشجرة البحث الثنائية معًا أنّه، بمجرّد تعريف المفتاح ( ) والأولوية ( ) لكل عقدة، يتحدّد شكل الـTreap تمامًا. فخاصية الكومة تخبرنا بأنّ العقدة ذات الأولوية الدنيا لا بدّ أن تكون الجذر، ، للـTreap. أمّا خاصية شجرة البحث الثنائية فتخبرنا بأنّ جميع العقد ذات المفاتيح الأصغر من تُخزَّن في الشجرة الفرعية التي جذورها ، وأنّ جميع العقد ذات المفاتيح الأكبر من تُخزَّن في الشجرة الفرعية التي جذورها . والنقطة المهمّة في قيم الأولوية داخل الـTreap هي أنّها فريدة وتُسنَد عشوائيًا. ولهذا فإنّ هناك طريقتين متكافئتين يمكننا التفكير في الـTreap بهما. فكما هو معرَّف أعلاه، يلتزم الـTreap بخاصيتي الكومة وشجرة البحث الثنائية. وعلى نحو بديل، يمكننا النظر إلى الـTreap على أنّه BinarySearchTree أُضيفت عقدُه بترتيب أولويّاتها المتزايد. فمثلًا، يمكن الحصول على الـTreap في الشكل 7.5 بإضافة تسلسل قيم
إلى BinarySearchTree.
ولأنّ الأولويات تُختار عشوائيًا، فإنّ هذا يعادل أخذ تبديل عشوائي للمفاتيح--وفي حالتنا هذه يكون التبديل هو
--وإضافة هذه المفاتيح إلى BinarySearchTree. لكنّ هذا يعني أنّ شكل الـtreap مطابق لشكل شجرة البحث الثنائية العشوائية. وبخاصة، إذا استبدلنا كل مفتاح برتبته،7.3 فتنطبق الملمة 7.1. ولإعادة صياغة الملمة 7.1 بعبارات Treap، نقول:
الملمّة 7.2 في Treap يخزّن مجموعة من مفتاحًا، تنطبق العبارتان التاليتان: * لأي ، يكون الطول المتوقَّع لمسار البحث عن هو . لأي ، يكون الطول المتوقَّع لمسار البحث عن هو . * هنا، تدلّ على رتبة في المجموعة .
ونؤكّد مجدّدًا أنّ التوقّع في الملمة 7.2 محسوب على الاختيارات العشوائية لأولويات كل عقدة. وهو لا يتطلّب أيّ افتراضات بشأن العشوائية في المفاتيح. وتخبرنا الملمة 7.2 بأنّ هياكل Treap تستطيع تنفيذ العملية بكفاءة. غير أنّ الفائدة الحقيقية للـTreap تكمن في قدرته على دعم العمليتَين و . ولتحقيق ذلك، عليه إجراء دورانات (rotations) للحفاظ على خاصية الكومة. راجع الشكل 7.6. الدوران في شجرة بحث ثنائية هو تعديلٌ محلّي يأخذ أبًا لعقدة ويجعل أبًا لـ ، مع الحفاظ على خاصية شجرة البحث الثنائية. ويأتي الدوران بنوعَين: دوران أيسر أو أيمن، بحسب ما إذا كان طفلًا أيمنًا أو أيسرًا لـ على التوالي.
والشيفرة التي تطبّق ذلك عليها معالجة الحالتَين أعلاه، فضلًا عن حالةٍ حدّية (boundary case) ينبغي الانتباه لها (عندما يكون هو الجذر)، ولذلك فإنّ الشيفرة الفعلية أطول قليلًا ممّا يوحي به الشكل 7.6 للقارئ:
void rotateLeft(Node u) {
Node w = u.right;
w.parent = u.parent;
if (w.parent != nil) {
if (w.parent.left == u) {
w.parent.left = w;
} else {
w.parent.right = w;
}
}
u.right = w.left;
if (u.right != nil) {
u.right.parent = u;
}
u.parent = w;
w.left = u;
if (u == r) { r = w; r.parent = nil; }
}
void rotateRight(Node u) {
Node w = u.left;
w.parent = u.parent;
if (w.parent != nil) {
if (w.parent.left == u) {
w.parent.left = w;
} else {
w.parent.right = w;
}
}
u.left = w.right;
if (u.left != nil) {
u.left.parent = u;
}
u.parent = w;
w.right = u;
if (u == r) { r = w; r.parent = nil; }
}
بالنسبة إلى بنية بيانات الـTreap، أهمّ خاصية للدوران هي أنّ عمق ينقص بمقدار واحد فيما يزيد عمق بمقدار واحد. وباستخدام الدورانات يمكننا تنفيذ العملية على النحو التالي: ننشئ عقدة جديدة، ، ونُسند ، ونختار قيمةً عشوائية لـ . ثم نضيف باستخدام خوارزمية المعتادة الخاصة بـ BinarySearchTree، بحيث تصير الآن ورقةً (leaf) في الـTreap. وعند هذه النقطة يكون الـTreap لدينا ملتزمًا بخاصية شجرة البحث الثنائية، ولكن ليس بالضرورة بخاصية الكومة. وبخاصة، قد يكون . وإن كان الأمر كذلك، فإنّنا نجري دورانًا عند العقدة = حتّى تصبح أبًا للعقدة . وإذا ظلّ يخالف خاصية الكومة، فلا بدّ لنا من تكرار ذلك، مع إنقاص عمق بمقدار واحد في كل مرة، إلى أن يصير إمّا الجذر وإمّا بحيث .
boolean add(T x) {
Node<T> u = newNode();
u.x = x;
u.p = rand.nextInt();
if (super.add(u)) {
bubbleUp(u);
return true;
}
return false;
}
void bubbleUp(Node<T> u) {
while (u.parent != nil && u.parent.p > u.p) {
if (u.parent.right == u) {
rotateLeft(u.parent);
} else {
rotateRight(u.parent);
}
}
if (u.parent == nil) {
r = u;
}
}
ويبيّن الشكل 7.7 مثالًا على عملية .
زمن تشغيل العملية محدَّدٌ بزمن اتباع مسار البحث عن مضافًا إليه عدد الدورانات التي أُجريت لنقل العقدة المضافة حديثًا، ، إلى موضعها الصحيح في الـTreap. وبموجب الملمة 7.2، فإنّ الطول المتوقَّع لمسار البحث يساوي على الأكثر . وإضافةً إلى ذلك، فإنّ كل دوران يُنقِص عمق . وهذا يتوقّف إذا صار هو الجذر، ومن ثمّ لا يمكن أن يتجاوز عدد الدورانات المتوقَّع الطول المتوقَّع لمسار البحث. وبالتالي فإنّ زمن التشغيل المتوقَّع للعملية في الـTreap هو . (يطلب التمرين 7.5 أن تُثبت أنّ عدد الدورانات المتوقَّع أثناء الإضافة ليس في الحقيقة إلا .) أمّا العملية في الـTreap فهي عكس العملية . فنبحث عن العقدة، ، التي تحوي ، ثمّ نجري دورانات لنقل إلى الأسفل حتى يصير ورقة، ثمّ نفصل عن الـTreap. ولاحظ أنّه لنقل إلى الأسفل، يمكننا إجراء دوران أيسر أو أيمن عند ، وهو ما سيستبدل بـ أو على التوالي. ويُتَّخذ الاختيار وفق أول الشروط التالية المنطبقة:
- إذا كان و كلاهما ، فإنّ ورقة ولا يُجرى أيّ دوران.
- إذا كان (أو ) هو ، ف أجرِ دورانًا أيمنًا (أو أيسرًا، على التوالي) عند .
- إذا كان (أو ، ف أجرِ دورانًا أيمنًا (أو أيسرًا، على التوالي) عند .
تضمن هذه القواعد الثلاث ألّا ينقطع الـTreap عن بعضه، وأن تُستعاد خاصية الكومة بعد إزالة .
boolean remove(T x) {
Node<T> u = findLast(x);
if (u != nil && compare(u.x, x) == 0) {
trickleDown(u);
splice(u);
return true;
}
return false;
}
void trickleDown(Node<T> u) {
while (u.left != nil || u.right != nil) {
if (u.left == nil) {
rotateLeft(u);
} else if (u.right == nil) {
rotateRight(u);
} else if (u.left.p < u.right.p) {
rotateRight(u);
} else {
rotateLeft(u);
}
if (r == u) {
r = u.parent;
}
}
}
ويبيّن الشكل 7.8 مثالًا على عملية .
والحيلة في تحليل زمن تشغيل العملية هي ملاحظة أنّ هذه العملية تعكس العملية . وبخاصة، إذا أعدنا إدراج باستخدام الأولوية نفسها ، فإنّ العملية ستجري عدد الدورانات نفسه بالضبط، وتعيد الـTreap إلى الحالة عينها التي كان عليها قبل وقوع عملية . (وإذا قُرئ الشكل 7.8 من الأسفل إلى الأعلى، فإنه يوضّح إضافة القيمة 9 إلى Treap.) وهذا يعني أنّ زمن التشغيل المتوقَّع للعملية على Treap ذات حجم متناسب مع زمن التشغيل المتوقَّع للعملية على Treap ذات حجم . ومن ثمّ نستنتج أنّ زمن التشغيل المتوقَّع لـ هو . 7.2.1 الخلاصة تلخّص المبرهنة التالية أداء بنية بيانات Treap: المبرهنة 7.2 يطبّق Treap واجهة SSet. يدعم Treap العمليات و و في زمن متوقَّع قدره لكل عملية.
من المفيد مقارنة بنية بيانات Treap ببنية بيانات SkiplistSSet. فالاثنتان تطبّقان عمليات SSet في زمن متوقَّع قدره لكل عملية. وفي كلتا البنيتين، تتضمّن و عملية بحث ثمّ عددًا ثابتًا من تغييرات المؤشّرات (راجع التمرين 7.5 أدناه). ومن ثمّ فإنّ الطول المتوقَّع لمسار البحث هو القيمة الحاسمة في تقييم أداء هاتين البنيتين. وفي SkiplistSSet، يكون الطول المتوقَّع لمسار البحث هو
وفي Treap، يكون الطول المتوقَّع لمسار البحث هو
وعليه، فإنّ مسارات البحث في الـTreap أقصر بدرجة كبيرة، وهذا ينعكس عمليًا على عمليات أسرع في Treap مقارنةً بقوائم التخطّي (skiplists). ويُبيّن التمرين 4.7 في الفصل 4 كيف يمكن تقصير الطول المتوقَّع لمسار البحث في قائمة التخطّي ليصبح
باستخدام قذفات عملة مُتحيّزة (biased coin tosses). وحتى مع هذا التحسين، يبقى الطول المتوقَّع لمسارات البحث في SkiplistSSet أطول بوضوح ممّا هو عليه في Treap.
الحواشي
... interface.7.2 جاء اسم Treap من أنّ بنية البيانات هذه شجرة بحث ثنائية (القسم 6.2) وكومة (الفصل 10) في آنٍ واحد. ... rank,7.3 رتبة (rank) عنصر في مجموعة عناصر هي عدد العناصر في الأصغر من . opendatastructures.org
7.3 النقاش والتمارين
جرت دراسة الأشجار الثنائية للبحث العشوائية على نطاق واسع. ويقدّم Devroye [19] برهانًا للملمة 7.1 ولنتائج ذات صلة. وهناك في الأدبيات نتائج أقوى بكثير، وأبرزها ما يعود إلى Reed [64]، الذي يُظهر أنّ الارتفاع المتوقَّع لشجرة بحث ثنائية عشوائية هو
حيث هو الحلّ الوحيد على الفترة للمعادلة ، و . وإضافةً إلى ذلك، فإنّ تباين الارتفاع ثابت.
ابتكر Seidel و Aragon [67] اسم Treap، وقد ناقشا هياكل Treap وبعض تنويعاتها. غير أنّ بنيتها الأساسية دُرست قبل ذلك بوقتٍ طويل من قِبل Vuillemin [76] الذي أسماها أشجارًا كرتيسية (Cartesian trees). ومن تحسينات المساحة الممكنة لبنية بيانات Treap أن نُغني عن التخزين الصريح للأولوية في كل عقدة. وبدلًا من ذلك، تُحسب أولوية العقدة، ، عبر تجزئة (hashing) عنوان في الذاكرة (وفي Java ذات 32 بت، فإنّ ذلك يعادل تجزئة ). ورغم أنّ عددًا من دوال التجزئة (hash functions) قد تعمل جيدًا لهذا الغرض في الممارسة العملية، إلا أنّه كي تظلّ الأجزاء المهمّة من برهان الملمة 7.1 صحيحة، ينبغي أن تكون دالة التجزئة عشوائية وأن توفّر خاصية الاستقلال التصغيريّ (min-wise independent): فبالنسبة إلى أي قيم متمايزة ، ينبغي أن تكون قيم التجزئة كلها متمايزة باحتمالٍ عالٍ، وأن من أجل كل ،
حيث ثابت ما. ومن أصناف دوال التجزئة التي يسهل تنفيذها وسريعة نسبيًا: تجزئة الجدولة (tabulation hashing) (القسم 5.2.3).
ومن تنويعات Treap الأخرى التي لا تخزّن أولويات عند كل عقدة: شجرة البحث الثنائية العشوائية لـ Martínez و Roura [51]. ففي هذا التنويع، تخزّن كل عقدة، ، الحجم للشجرة الفرعية التي جذورها . وكلتا خوارزمتَي و عشوائيتان. وتقوم خوارزمية إضافة إلى الشجرة الفرعية التي جذورها هو بما يلي: باحتمال ، تُضاف القيمة بالطريقة المعتادة كورقة، ثمّ تُجرى دورانات لرفع حتى جذر هذه الشجرة الفرعية. وفي غير ذلك (باحتمال )، تُضاف القيمة secara تكرارية إلى إحدى الشجرتين الفرعيتين الجذور لهما أو ، بحسب ما يقتضيه الحال. وتُقابل الحالة الأولى عملية في Treap تحصل فيها عقدة على أولوية عشوائية أصغر من أيٍّ من الأولويات الموجودة في الشجرة الفرعية التي جذورها . وتحدث هذه الحالة بالاحتمال نفسه بالضبط. وإزالة قيمة من شجرة بحث ثنائية عشوائية تشبه عملية الإزالة من Treap. فنجد العقدة، ، التي تحوي ، ثمّ نجري دورانات ترفع عمق تكرارًا حتى يصير ورقة، وعندئذٍ يمكننا فصله عن الشجرة. والاختيار بين إجراء دوران أيسر أو أيمن في كل خطوة عشوائي. فباحتمال ، نجري دورانًا أيمنًا عند ، فتصير جذرًا للشجرة الفرعية التي كان جذورها هو . وباحتمال ، نجري دورانًا أيسرًا عند ، فتصير جذرًا للشجرة الفرعية التي كان جذورها هو . ومرةً أخرى، يسهل التحقّق من أنّ هذه هي بالضبط الاحتمالات عينها التي تجري فيها خوارزمية الإزالة في Treap دورانًا أيسرًا أو أيمنًا للعقدة . وللأشجار الثنائية للبحث العشوائية عيبٌ مقارنةً بـTreap، إذ إنّها عند إضافة العناصر وإزالتها تجري اختياراتٍ عشوائية كثيرة، وعليها أن تحافظ على أحجام الشجرات الفرعية. وفي المقابل، فإنّ لأشجار البحث الثنائية العشوائية ميزةٌ على Treap، إذ إنّ أحجام الشجرات الفرعية يمكن أن تخدم غرضًا نافعًا آخر، وتحديدًا توفير الوصول حسب الرتبة في زمن متوقَّع قدره (راجع التمرين 7.10). وبالمقارنة مع ذلك، فإنّ الأولويات العشوائية المخزَّنة في عقد الـtreap لا فائدة فيها سوى إبقاء الـtreap متوازنًا. التمرين 7.1 بيّن إضافة 4.5 (بأولوية 7) ثمّ 7.5 (بأولوية 20) إلى الـTreap في الشكل 7.5.
التمرين 7.2 بيّن إزالة 5 ثمّ 7 من الـTreap في الشكل 7.5.
التمرين 7.3 اثبت أنّ المُدّعى هو أنّ هناك تسلسلًا يولّد الشجرة في الجانب الأيمن من الشكل 7.1. (تلميح: أعطِ صيغةً تكرارية لعدد التسلسلات التي تولّد شجرة بحث ثنائية كاملة ارتفاعها ، ثمّ قيّم هذه الصيغة عند .)
التمرين 7.4 صمّم ونفّذ طريقة التي تأخذ كمُدخَل مصفوفة، ، تحتوي قيمةً متمايزة وتبدّل ترتيب عناصر عشوائيًا. وينبغي أن تعمل هذه الطريقة في زمن ، وأن تُثبت أنّ احتمال كل تبديلٍ من التبديلات الـ الممكنة لـ متساوٍ.
التمرين 7.5 استخدم جزأَي الملمة 7.2 لإثبات أنّ عدد الدورانات المتوقَّع الذي تجريه عملية (وعليه أيضًا عملية ) هو .
التمرين 7.6 عدّل تنفيذ الـTreap المعطى هنا بحيث لا يخزّن الأولويات صراحةً. وبدلًا من ذلك، ينبغي أن يحاكيها عبر تجزئة قيمة لكل عقدة.
التمرين 7.7 افترض أنّ شجرة بحث ثنائية تخزّن عند كل عقدة، ، الارتفاع للشجرة الفرعية التي جذورها ، والحجم لتلك الشجرة الفرعية التي جذورها . بيّن كيف يمكن تحديث هذين المقدارين، في زمن ثابت، لجميع العقد المتأثّرة بالدوران إذا أجرينا دورانًا أيسرًا أو أيمنًا عند . واشرح لماذا لا يمكن بلوغ النتيجة نفسها إذا حاولنا أيضًا تخزين العمق، ، لكل عقدة .
التمرين 7.8 صمّم ونفّذ خوارزمية تبني Treap من مصفوفةٍ مرتَّبة، ، من عنصرًا. وينبغي أن تعمل هذه الطريقة في أسوأ الحالات في زمن ، وأن تبني Treap لا يمكن تمييزه عن Treap أُضيفت عناصر إليه واحدًا تلو الآخر باستخدام طريقة .
التمرين 7.9 يتناول هذا التمرين تفاصيل كيفية البحث بكفاءة في Treap معطىً مؤشّرًا قريبًا من العقدة التي نبحث عنها. صمّم ونفّذ تنفيذًا لـTreap يحتفظ فيه كل عقدة بأصغر قيمة وأكبر قيمة في شجرتها الفرعية. وباستخدام هذه المعلومات الإضافية، أضف طريقة تنفّذ العملية بمساعدة مؤشّر إلى العقدة (ويُرجَّح ألّا تكون بعيدة عن العقدة التي تحوي ). وينبغي أن تبدأ هذه العملية من وتصعد حتى تبلغ عقدة بحيث . ومن تلك النقطة فصاعدًا، ينبغي أن يُجري بحثًا معتادًا عن بدءًا من . (يمكن إظهار أنّ يستغرق زمنًا قدره ، حيث هو عدد العناصر في الـtreap التي تقع قيمتها بين و .) ووسِّع تنفيذك ليصير نسخةً من الـtreap تبدأ كل عمليات فيها من آخر عقدة عثر عليها .
التمرين 7.10 صمّم ونفّذ نسخةً من Treap تتضمّن عملية تُعيد المفتاح ذي الرتبة (rank) في الـTreap. (تلميح: اجعل كل عقدة، ، تحتفظ بحجم الشجرة الفرعية التي جذورها هي .)
التمرين 7.11 نفّذ TreapList، وهو تنفيذٌ لواجهة List بوصفه treap. وينبغي أن تخزّن كل عقدة في الـtreap عنصرَ قائمة، وأن يعثر اجتياز الـtreap بترتيب الوسط (in-order) على العناصر بالترتيب نفسه الذي ترد به في القائمة. وينبغي أن تعمل جميع عمليات List، وهي و و و ، في زمن متوقَّع قدره .
التمرين 7.12 صمّم ونفّذ نسخةً من Treap تدعم عملية . وهذه العملية تزيل من الـTreap كلَّ القيم الأكبر من وتُعيد Treap ثانيةً يحتوي على كل القيم المُزالة. مثال: الشيفرة تزيل من كل القيم الأكبر من وتُعيد Treap جديدًا يحتوي على هذه القيم جميعًا. وينبغي أن تعمل عملية في زمن متوقَّع قدره . تحذير: لكي يعمل هذا التعديل على الوجه الصحيح ولا تزال طريقة تعمل في زمن ثابت، من الضروري تنفيذ التعديلات الواردة في التمرين 7.10.
التمرين 7.13 صمّم ونفّذ نسخةً من Treap تدعم عملية ، ويمكن التفكير فيها على أنّها العملية العاكسة لـ . وهذه العملية تزيل من الـTreap كلَّ القيم وتضيفها إلى الكائن المستقبِل. وتفترض هذه العملية أنّ أصغر قيمة في أكبر من أكبر قيمة في الكائن المستقبِل. وينبغي أن تعمل عملية في زمن متوقَّع قدره .
التمرين 7.14 نفّذ أشجار البحث الثنائية العشوائية لـ Martinez كما نُوقشت في هذا القسم. وقارن بين أداء تنفيذك وأداء تنفيذ الـTreap.