6. الأشجار الثنائية
يقدّم هذا الفصل أحد أكثر البنى أهمية في علوم الحاسوب: الأشجار الثنائية (binary trees). ويعود سبب تسمية هذه البنى بـ«شجرة» إلى أنّ الرسم الناتج عنها يشبه في كثير من الأحيان الأشجار التي تنبت في الغابة. وهناك طُرق كثيرة لتعريف الأشجار الثنائية. رياضيًا، الشجرة الثنائية رسم بياني (graph) متصل وغير موجّه (undirected) ومنتهٍ (finite) خالٍ من الدورات، لا رأس (vertex) فيه تتجاوز درجته ثلاثة. وفي معظم تطبيقات علوم الحاسوب تكون الأشجار الثنائية مجذّرة (rooted): إذ تُسمّى عقدة خاصة، ، درجتها لا تتجاوز اثنتين، جذر (root) الشجرة. أمّا لكل عقدة، ، فتُسمّى العقدة الثانية على المسار من إلى العقدة الأم (parent) لـ . وتُسمّى بقية العقد المجاورة لـ ابنةً (child) لـ . ومعظم الأشجار الثنائية التي تهمّنا مرتّبة (ordered)، ولذلك نميّز بين الابنة اليسرى والابنة اليمنى لـ . وفي الرسوم التوضيحية، تُرسم الأشجار الثنائية عادةً من الجذر نزولًا، فيقع الجذر في أعلى الرسم، وتحتل الابنتان اليسرى واليمنى على التوالي موضعي اليسار واليمين فيه (الشكّل 6.1). وعلى سبيل المثال، يعرض الشكّل 6.2.a شجرة ثنائية من تسع عقد.
| (a) | (b) |
ولأنّ الأشجار الثنائية ذات أهمية بالغة، فقد ترسّخت لها اصطلاحات خاصة: فعمق (depth) العقدة في شجرة ثنائية هو طول المسار من إلى جذر الشجرة. وإذا كانت عقدة، ، تقع على المسار من إلى ، فإن تُسمّى سلفًا (ancestor) لـ ، وتُسمّى ذريةً (descendant) لـ . أمّا الشجرة الفرعية (subtree) للعقدة فهي الشجرة الثنائية المجذّرة عند وتضمّ جميع ذرية . وارتفاع (height) العقدة هو طول أطول مسار من إلى إحدى ذريّاتها، وارتفاع الشجرة هو ارتفاع جذرها. وتُسمّى العقدة ورقةً (leaf) إذا لم يكن لها أي ابنة. ونفكّر أحيانًا في الشجرة على أنها مُزوَّدة بعقد خارجية (external nodes): فكل عقدة ليس لها ابنة يسرى تكون لها عقدة خارجية بوصفها الابنة اليسرى، وعلى نحو مقابل، كل عقدة ليس لها ابنة يمنى تكون لها عقدة خارجية بوصفها الابنة اليمنى (انظر الشكّل 6.2.b). ومن السهل التحقّق، بالاستدلال (induction)، من أن شجرة ثنائية فيها عقدة حقيقية تضمّ عقدة خارجية.
الأقسام الفرعية
6.1 BinaryTree: شجرة ثنائية أساسية
الأقسام الفرعية
6.1 BinaryTree: شجرة ثنائية أساسية
أبسط طريقة لتمثيل عقدة، ، في شجرة ثنائية هي تخزين جارات — وعددها ثلاثة على الأكثر — صراحةً:
class BTNode<Node extends BTNode<Node>> {
Node left;
Node right;
Node parent;
}
وعند غياب أحد هذه الجارات الثلاثة نُسند إليه القيمة . وهكذا يتطابق كلٌّ من العقد الخارجية للشجرة والعقدة الأم للجذر مع القيمة . وعندئذٍ يمكن تمثيل الشجرة الثنائية نفسها بإشارة إلى عقدة جذرها، :
Node r;
ويمكننا حساب عمق عقدة، ، في شجرة ثنائية بعدّ عدد الخطوات على المسار من إلى الجذر:
int depth(Node u) {
int d = 0;
while (u != r) {
u = u.parent;
d++;
}
return d;
}
6.1.1 الخوارزميات التعاودية
تتيح الخوارزميات التعاودية (recursive) حساب خصائص الأشجار الثنائية بسهولة كبيرة. فمثلًا، لحساب حجم (number of nodes) شجرة ثنائية مجذّرة عند العقدة ، نحسب تعاوديًا حجمَي الشجرتين الفرعيتين المجذّرتين عند ابنتي ، ثم نجمعهما ونضيف واحدًا:
int size(Node u) {
if (u == nil) return 0;
return 1 + size(u.left) + size(u.right);
}
ولحساب ارتفاع عقدة ، نحسب ارتفاع الشجرتين الفرعيتين لـ ، ثم نأخذ الأكبر منهما ونضيف واحدًا:
int height(Node u) {
if (u == nil) return -1;
return 1 + Math.max(height(u.left), height(u.right));
}
6.1.2 اجتياز الأشجار الثنائية
تستخدم الخوارزميتان في القسم السابق كلتاهما التعاود (recursion) لزيارة جميع عقد شجرة ثنائية. وكلٌّ منهما يزور عقد الشجرة الثنائية بالترتيب نفسه الذي تمرّ به الشيفرة التالية:
void traverse(Node u) {
if (u == nil) return;
traverse(u.left);
traverse(u.right);
}
وينتج عن هذا الأسلوب شيفرة قصيرة جدًّا وبسيطة، لكنه قد يسبّب مشكلات أيضًا. فأقصى عمق للتعاود تحدّده أقصى عمق لأي عقدة في الشجرة الثنائية، أي ارتفاع الشجرة نفسها. وإذا كان ارتفاع الشجرة كبيرًا جدًّا، فقد يستهلك هذا التعاود من مساحة المكدس (stack) أكثر من المتاح، فيتسبّب في انهيار البرنامج. أمّا لاجتياز شجرة ثنائية دون تعاود، فيمكنك استخدام خوارزمية تعتمد على الموضع الذي أتينا منه لتحديد الموضع الذي سنذهب إليه تاليًّا. انظر الشكّل 6.3. فإذا وصلنا إلى عقدة من ، فإن الخطوة التالية هي زيارة . وإذا وصلنا إلى من ، فإن الخطوة التالية هي زيارة . وإذا وصلنا إلى من ، فقد انتهينا من زيارة الشجرة الفرعية لـ ، فنعود إلى . وتُنفّذ الشيفرة التالية هذه الفكرة، مع تضمين شيفرة تتعامل مع الحالات التي تكون فيها أو أو على القيمة :
void traverse2() {
Node u = r, prev = nil, next;
while (u != nil) {
if (prev == u.parent) {
if (u.left != nil) next = u.left;
else if (u.right != nil) next = u.right;
else next = u.parent;
} else if (prev == u.left) {
if (u.right != nil) next = u.right;
else next = u.parent;
} else {
next = u.parent;
}
prev = u;
u = next;
}
}
والحقائق نفسها التي يمكن حسابها بالخوارزميات التعاودية يمكن حسابها بهذه الطريقة أيضًا، دون تعاود. فمثلًا، لحساب حجم الشجرة نحتفظ بعدّاد، ، ونزيد بمقدار واحد كلما زرنا عقدة لأول مرة:
int size2() {
Node u = r, prev = nil, next;
int n = 0;
while (u != nil) {
if (prev == u.parent) {
n++;
if (u.left != nil) next = u.left;
else if (u.right != nil) next = u.right;
else next = u.parent;
} else if (prev == u.left) {
if (u.right != nil) next = u.right;
else next = u.parent;
} else {
next = u.parent;
}
prev = u;
u = next;
}
return n;
}
في بعض تنفيذات الأشجار الثنائية لا يُستعمل الحقل . وفي هذه الحالة يظلّ التنفيذ غير التعاودي ممكنًا، لكنّه يضطر إلى استعمال قائمة (List) أو مكدس (Stack) لتتبّع المسار من العقدة الحالية إلى الجذر. وهناك نوع خاص من الاجتياز لا يندرج ضمن نمط الدوال أعلاه، وهو الاجتياز بالعرض (breadth-first traversal). وفي الاجتياز بالعرض تُزرع العقد مستوىً بعد مستوى، بدءًا من الجذر ثم النزول، وتُزار عقد كل مستوى من اليسار إلى اليمين (انظر الشكّل 6.4). وهذا يشبه الطريقة التي نقرأ بها صفحة من نص إنجليزي. ويُنفَّذ الاجتياز بالعرض باستعمال طابور (queue)، ، لا يحتوي في البداية سوى الجذر، . وفي كل خطوة نستخرج العقدة التالية، ، من ، ونعالج ، ثم نضيف و (إذا لم يكونا على القيمة ) إلى :
void bfTraverse() {
Queue<Node> q = new LinkedList<Node>();
if (r != nil) q.add(r);
while (!q.isEmpty()) {
Node u = q.remove();
if (u.left != nil) q.add(u.left);
if (u.right != nil) q.add(u.right);
}
}
6.2 BinarySearchTree: شجرة بحث ثنائية غير متوازنة
الأقسام الفرعية
6.2 BinarySearchTree: شجرة بحث ثنائية غير متوازنة
شجرة BinarySearchTree نوع خاص من الأشجار الثنائية، تخزّن فيها كل عقدة، ، قيمة بيانات، ، مأخوذة من ترتيب كلي (total order) ما. وتخضع قيم البيانات في شجرة البحث الثنائية لخاصية شجرة البحث الثنائية (binary search tree property): فأمّا العقدة ، فكل قيمة بيانات مخزّنة في الشجرة الفرعية المجذّرة عند فهي أصغر من ، وكل قيمة بيانات مخزّنة في الشجرة الفرعية المجذّرة عند فهي أكبر من . ويعرض الشكّل 6.5 مثالًا على BinarySearchTree.
6.2.1 البحث
خاصية شجرة البحث الثنائية مفيدة إلى حدّ بعيد لأنها تتيح لنا تحديد موضع قيمة، ، في شجرة بحث ثنائية بسرعة. ولهذا نبدأ البحث عن من الجذر، . وعند فحص عقدة، ، تنشأ ثلاث حالات:
- إذا كان ، فإن البحث يتقدّم إلى ؛
- إذا كان ، فإن البحث يتقدّم إلى ؛
- إذا كان ، فقد وجدنا العقدة التي تحتوي .
وينتهي البحث عند وقوع الحالة 3 أو عند تحقّق . وفي الحالة الأولى، فقد عثرنا على . وفي الحالة الثانية، نستنتج أن غير موجودة في شجرة البحث الثنائية.
T findEQ(T x) {
Node u = r;
while (u != nil) {
int comp = compare(x, u.x);
if (comp < 0)
u = u.left;
else if (comp > 0)
u = u.right;
else
return u.x;
}
return null;
}
يعرض الشكّل 6.6 مثالين للبحث في شجرة بحث ثنائية. وكما يبيّن المثال الثاني، حتى وإن لم نجد في الشجرة فإننا نظفر ببعض المعلومات القيّمة. فإذا نظرنا إلى آخر عقدة، ، وقعت فيها الحالة 1، رأينا أن هي أصغر قيمة في الشجرة أكبر من . وعلى نحو مماثل، فإن آخر عقدة وقعت فيها الحالة 2 تحتوي على أكبر قيمة في الشجرة أصغر من . وعليه، فإن تتبّع آخر عقدة، ، تقع فيها الحالة 1، يتيح لـ BinarySearchTree تنفيذ العملية التي تُرجع أصغر قيمة مخزّنة في الشجرة تكون أكبر من أو مساوية لها:
T find(T x) {
Node w = r, z = nil;
while (w != nil) {
int comp = compare(x, w.x);
if (comp < 0) {
z = w;
w = w.left;
} else if (comp > 0) {
w = w.right;
} else {
return w.x;
}
}
return z == nil ? null : z.x;
}
| 
|
| --- | --- |
| (a) | (b) |
6.2.2 الإضافة
لإضافة قيمة جديدة، ، إلى BinarySearchTree، نبحث عن أولًا. فإذا عثرنا عليها فلا داعي لإدراجها. وإلّا فسنخزّن عند ابنةٍ ورقة للعقدة الأخيرة، ، التي صادفناها أثناء البحث عن . أمّا كون العقدة الجديدة ابنةً يسرى أو يمنى لـ فيتوقّف على نتيجة مقارنة بـ .
boolean add(T x) {
Node p = findLast(x);
return addChild(p, newNode(x));
}
Node findLast(T x) {
Node w = r, prev = nil;
while (w != nil) {
prev = w;
int comp = compare(x, w.x);
if (comp < 0) {
w = w.left;
} else if (comp > 0) {
w = w.right;
} else {
return w;
}
}
return prev;
}
boolean addChild(Node p, Node u) {
if (p == nil) {
r = u; // inserting into empty tree
} else {
int comp = compare(u.x, p.x);
if (comp < 0) {
p.left = u;
} else if (comp > 0) {
p.right = u;
} else {
return false; // u.x is already in the tree
}
u.parent = p;
}
n++;
return true;
}
يعرض الشكّل 6.7 مثالًا على ذلك. وأكثَر أجزاء هذه العملية استهلاكًا للوقت هو البحث الأولي عن ، إذ يستغرق زمنًا متناسبًا مع ارتفاع العقدة المضافة حديثًا . وفي أسوأ الحالات، يساوي هذا ارتفاع BinarySearchTree.
6.2.3 الحذف
وحذف قيمة مخزّنة في عقدة، ، من BinarySearchTree أصعب قليلًا. فإذا كانت ورقةً، يكفي فصل عن أمّها. والأفضل: إذا كانت ذات ابنة واحدة، فيمكننا نزع (splice) من الشجرة بأن تتبنّى ابنة (انظر الشكّل 6.8):
void splice(Node u) {
Node s, p;
if (u.left != nil) {
s = u.left;
} else {
s = u.right;
}
if (u == r) {
r = s;
p = nil;
} else {
p = u.parent;
if (p.left == u) {
p.left = s;
} else {
p.right = s;
}
}
if (s != nil) {
s.parent = p;
}
n--;
}
غير أنّ الأمور تصبح معقّدة عندما تكون ذات ابنتين. وفي هذه الحالة، أبسط ما يمكن فعله هو العثور على عقدة، ، لها أقل من ابنتين، بحيث يمكن لـ أن تحلّ محلّ . ولأجل الحفاظ على خاصية شجرة البحث الثنائية، ينبغي أن تكون قيمة قريبة من قيمة . فمثلًا، يكفي اختيار بحيث تكون أصغر قيمة أكبر من . والعثور على العقدة سهل؛ فهي أصغر قيمة في الشجرة الفرعية المجذّرة عند . ويمكن إزالة هذه العقدة بسهولة لأنها لا تملك ابنة يسرى (انظر الشكّل 6.9).
void remove(Node u) {
if (u.left == nil || u.right == nil) {
splice(u);
} else {
Node w = u.right;
while (w.left != nil)
w = w.left;
u.x = w.x;
splice(w);
}
}
الشكّل 6.9: يتضمّن حذف قيمة ( ) من عقدة، ، ذات ابنتين استبدال قيمة بأصغر قيمة في الشجرة الفرعية اليمنى المجذّرة عند . 
6.2.4 خلاصة تنطوي كلٌّ من العمليات و و في BinarySearchTree على اتباع مسار من جذر الشجرة إلى إحدى عقدها. ومن دون معرفة أكبر عن شكل الشجرة يصعب قول الكثير عن طول هذا المسار، عدا أنه أقل من ، وهو عدد عقد الشجرة. وتُلخّص المبرهنة التالية (وهي غير مُبهرة) أداء بنية البيانات BinarySearchTree: المبرهنة 6.1 تنفّذ BinarySearchTree واجهة SSet، وتدعم العمليات و و في زمن لكل عملية.
تقارن المبرهنة 6.1 مقارنةً سيّئة بالمبرهنة 4.1، التي تُظهر أن بنية SkiplistSSet تستطيع تنفيذ واجهة SSet بزمن متوقع قدره لكل عملية. والمشكلة في بنية BinarySearchTree أنها قد تصبح غير متوازنة. فبدلًا من أن تبدو على هيئة الشجرة في الشكّل 6.5، قد تبدو على هيئة سلسلة طويلة من عقد، لكلّها خلا العقد الأخيرة ابنة واحدة بالضبط. وهناك طُرق عديدة لتجنّب أشجار البحث الثنائية غير المتوازنة، وكلّها تؤدّي إلى بنى بيانات عملياتها بزمن . وفي الفصل 7 نبيّن كيف يمكن بلوغ عمليات بزمن متوقع قدره بالاعتماد على العشوائية (randomization). وفي الفصل 8 نبيّن كيف يمكن بلوغ عمليات بزمن مُطفأ (amortized) قدره بعمليات إعادة البناء الجزئي. وفي الفصل 9 نبيّن كيف يمكن بلوغ عمليات بزمن أسوأ حالة قدره عبر محاكاة شجرة غير ثنائية: شجرة يمكن أن تتجاوز عقدُها أربعَ ابنات. موقع opendatastructures.org
6.3 مناقشة والتمارين
استُخدمت الأشجار الثنائية لنمذجة العلاقات منذ آلاف السنين. ومن أسباب ذلك أنّ الأشجار الثنائية تنمذج بصورة طبيعية أشجار العائلة (نسبيّة النسب). فهذه هي أشجار العائلة التي يكون فيها الجذر شخصًا، وتكون الابنتان اليسرى واليمنى والدَيْن الشخص، وهكذا تعاوديًا. وفي القرون الأخيرة استُخدمت الأشجار الثنائية أيضًا لنمذجة أشجار الأنواع في الأحياء، حيث تمثّل أوراق الشجرة الأنواع الحيّة الباقية، وتمثّل العقد الداخلية للشجرة أحداث التمايز (speciation) التي يتطوّر فيها تجمّعان من نوع واحد إلى نوعين منفصلين. ويبدو أن أشجار البحث الثنائية قد اُكتشفت على يد عدّة مجموعات بصورة مستقلّة في الخمسينيات [48, القسم 6.2.2]. وتقدّم الفصول اللاحقة مراجعَ إضافية إلى أنواع محدّدة من أشجار البحث الثنائية. وعند تنفيذ شجرة ثنائية من الصفر، هناك عدّة قرارات تصميمية يجب اتخاذها. ومن بينها ما إذا كانت كل عقدة تخزّن مؤشرًا إلى أمّها. فإذا كانت معظم العمليات تتبع مجرّد مسار من الجذر إلى ورقة، فإنّ مؤشرات الأمّ تصبح غير ضرورية، وتهدر المساحة، وتمثّل مصدرًا محتملًا لأخطاء البرمجة. ومن الجهة الأخرى، يعني غياب مؤشرات الأمّ أن اجتياز الشجرة لا بدّ أن يتمّ تعاوديًا أو باستعمال مكدس صريح (explicit stack). كما أنّ بعض الطرائق الأخرى (مثل الإدراج أو الحذف في بعض أنواع أشجار البحث الثنائية المتوازنة) تتعقّد بسبب غياب مؤشرات الأمّ. أمّا قرار التصميم الآخر فيتعلّق بكيفية تخزين مؤشرات الأمّ والابنة اليسرى والابنة اليمنى عند العقدة. وفي التنفيذ المعروض هنا، تُخزَّن هذه المؤشرات في متغيّرات منفصلة. وخيار آخر هو تخزينها في مصفوفة، ، طولها 3، بحيث تكون هي الابنة اليسرى لـ ، و هي الابنة اليمنى لـ ، و هي الأمّ لـ . واستعمال المصفوفة بهذه الطريقة يعني أنّ بعض السلاسل من جمل يمكن تبسيطها إلى تعبيرات جبرية. ومن أمثلة هذا التبسيط ما يحدث أثناء اجتياز الشجرة. فإذا وصل الاجتياز إلى عقدة، ، من ، فإنّ العقدة التالية في الاجتياز هي . وتتكاثر الأمثلة المماثلة عند وجود تناظر بين اليسار واليمين. فمثلًا، أخت (sibling) هي . وتعمل هذه الحيلة سواء كانت ابنةً يسرى ( ) أو ابنةً يمنى ( ) لـ . وفي بعض الحالات يعني ذلك أنّ شيفرةً معقّدة كانت ستحتاج لولا ذلك إلى نسختين، نسخة لليسار وأخرى لليمين، يمكن كتابتها مرّة واحدة فقط. انظر الدالتين و في صفحة 
مثالًا على ذلك. التمرين 6.1 أثبت أنّ شجرة ثنائية فيها عقدة لديها حافة.
التمرين 6.2 أثبت أنّ شجرة ثنائية ذات عقدة حقيقية تضمّ عقدة خارجية.
التمرين 6.3 أثبت أنّه إذا كانت الشجرة الثنائية تملك ورقة واحدة على الأقلّ، فإنّه إمّا (a) أن يكون لجذر ابنة واحدة على الأكثر، أو (b) أن تملك أكثر من ورقة.
التمرين 6.4 نفّذ دالة غير تعاودية، ، تحسب حجم الشجرة الفرعية المجذّرة عند العقدة .
التمرين 6.5 اكتب دالة غير تعاودية، ، تحسب ارتفاع العقدة في BinaryTree.
التمرين 6.6 الشجرة الثنائية متوازنة الحجم (size-balanced) إذا كان، لكل عقدة ، حجمَا الشجرتين الفرعيتين المجذّرتين عند و يختلفان بواقع واحد على الأكثر. اكتب دالة تعاودية، ، تختبر ما إذا كانت شجرة ثنائية متوازنة. وينبغي أن تعمل دالتك في زمن . (واحرص على اختبار شيفرتك على بعض الأشجار الكبيرة ذات الأشكال المختلفة؛ فمن السهل كتابة دالة تستغرق زمنًا أطول بكثير من .)
الاجتياز بالترتيب المسبق (pre-order traversal) لشجرة ثنائية هو اجتياز يزور كل عقدة، ، قبل أيٍّ من ابنتَيها. والاجتياز بالترتيب الوسطي (in-order traversal) يزور بعد زيارة جميع عقد الشجرة الفرعية اليسرى لـ وقبل زيارة أيٍّ من عقد الشجرة الفرعية اليمنى لـ . أمّا الاجتياز بالترتيب اللاحق (post-order traversal) فيزور فقط بعد زيارة سائر عقد الشجرة الفرعية لـ . أمّا ترقيم شجرة بترتيب مسبق أو وسطي أو لاحق (pre/in/post-order numbering) فيُسند إلى عقد الشجرة الأعداد الصحيحة بالترتيب الذي تصادفها به اجتيازٌ مسبق أو وسطي أو لاحق. انظر الشكّل 6.10 مثالًا. الشكّل 6.10: الترقيم المسبق واللاتح والوسطي لشجرة ثنائية. 
التمرين 6.7 أنشئ صنفًا فرعيًا من BinaryTree تكون لعقده حقول لتخزين الأرقام المسبقة واللاتحقة والوسطية. واكتب دوالًا تعاودية و و تُسند هذه الأرقام على الوجه الصحيح. وينبغي أن تعمل كلٌّ من هذه الدوال في زمن .
التمرين 6.8 نفّذ الدوال غير التعاودية و و التي تُرجع العقدة التي تلي في اجتيازٍ بالترتيب المسبق أو الوسطي أو اللاحق على التوالي. وينبغي أن تستهلك هذه الدوال زمنًا ثابتًا مُطفأ (amortized constant time)؛ فإذا بدأنا من أي عقدة وكرّرنا استدعاء إحدى هذه الدوال وأسندنا القيمة المُرجعة إلى حتى يبلغ ، فينبغي أن تكون تكلفة كل هذه الاستدعاءات .
التمرين 6.9 نفترض أنّ لدينا شجرة ثنائية أُسند إلى عقدها أرقامٌ بالترتيب المسبق واللاتح والوسطي. بيّن كيف يمكن استعمال هذه الأرقام للإجابة عن كلٍّ من الأسئلة التالية في زمن ثابت: أعطِ عقدة ، فحدّد حجم الشجرة الفرعية المجذّرة عند . وأعطِ عقدة ، فحدّد عمق . وأعطِ عقدتين و ، فحدّد ما إذا كان سلفًا لـ
التمرين 6.10 نفترض أنّ لديك قائمة عقد أُسند إليها أرقام بالترتيب المسبق والوسطي. أثبت أنّه توجد شجرة واحدة على الأكثر بهذا الترقيم المسبق/الوسطي، وبيّن كيفية بنائها.
التمرين 6.11 بيّن أنّ شكل أي شجرة ثنائية على عقد يمكن تمثيله بـ بت على الأكثر. (تلميح: فكّر في تسجيل ما يجري أثناء اجتياز، ثم إعادة تشغيل ذلك التسجيل لإعادة بناء الشجرة.)
التمرين 6.12 بيّن ما يحدث عند إضافة القيمة ثم القيمة 4.5 إلى شجرة البحث الثنائية في الشكّل 6.5.
التمرين 6.13 بيّن ما يحدث عند حذف القيمة ثم القيمة 5 من شجرة البحث الثنائية في الشكّل 6.5.
التمرين 6.14 نفّذ دالة في BinarySearchTree، ، تُرجع قائمةً بكل العناصر الموجودة في الشجرة التي هي أصغر من أو مساوية لها. وينبغي أن يكون زمن تنفيذ دالتك هو حيث هو عدد العناصر الأصغر من أو المساوية لها، و هو ارتفاع الشجرة.
التمرين 6.15 صِف كيف تضيف العناصر إلى BinarySearchTree فارغة في البداية بحيث يصبح ارتفاع الشجرة الناتجة . وفي كم طريقة يمكن ذلك؟
التمرين 6.16 إذا كانت لدينا شجرة BinarySearchTree ونفّذنا العملية تلتها العملية (بالقيمة نفسها لـ )، فهل نعود بالضرورة إلى الشجرة الأصلية؟
التمرين 6.17 هل تستطيع عملية زيادة ارتفاع أي عقدة في BinarySearchTree؟ وإن كان كذلك، فبكم؟
التمرين 6.18 هل تستطيع عملية زيادة ارتفاع أي عقدة في BinarySearchTree؟ وهل تستطيع زيادة ارتفاع الشجرة؟ وإن كان كذلك، فبكم؟
التمرين 6.19 صمّم ونفّذ نسخة من BinarySearchTree تحتفظ فيها كل عقدة، ، بالقيم (حجم الشجرة الفرعية المجذّرة عند ) و (عمق ) و (ارتفاع الشجرة الفرعية المجذّرة عند ). وينبغي صيانة هذه القيم، حتى أثناء استدعاءات عمليتَي و ، من دون أن تزيد ذلك تكلفة هاتين العمليتين بمعامل ثابت أكثر.