شجرة البحث الثنائية

التعليمات

أدرِج الأعداد وابحث عنها في شجرة ثنائية.

عندما نحتاج إلى تمثيل بيانات مرتّبة، لا تُعدّ المصفوفة بنية بيانات جيدة.

لنفترض أن لدينا المصفوفة [1, 3, 4, 5]، وأضفنا إليها 2 فأصبحت [1, 3, 4, 5, 2]، والآن علينا أن نرتّب المصفوفة كاملة من جديد! يمكننا تحسين هذا إذا أدركنا أننا لا نحتاج إلا إلى إفساح مكان للعنصر الجديد [1, nil, 3, 4, 5]، ثم نضيف العنصر في المكان الذي أفسحناه. لكن هذا لا يزال يتطلب منّا إزاحة عناصر كثيرة بمقدار موضع واحد.

أما أشجار البحث الثنائية، فيمكنها التعامل مع البيانات المرتّبة بكفاءة أكبر بكثير.

تتكوّن شجرة البحث الثنائية من مجموعة من العُقد المتّصلة. كل عقدة تحتوي على قطعة من البيانات (مثل العدد 3)، ومتغيّر اسمه left، ومتغيّر اسمه right. ويشير المتغيّران left وright إلى nil أو إلى عُقد أخرى. وبما أن هذه العُقد الأخرى لها بدورها عُقد تحتها، فإننا نقول إن المتغيّرين left وright يشيران إلى أشجار فرعية. كل البيانات في الشجرة الفرعية اليسرى أقل من بيانات العقدة الحالية أو تساويها، وكل البيانات في الشجرة الفرعية اليمنى أكبر من بيانات العقدة الحالية.

على سبيل المثال، إذا كانت لدينا عقدة تحتوي على البيانات 4، وأضفنا البيانات 2، فستبدو شجرتنا هكذا:

  4
 /
2

وإذا أضفنا بعد ذلك 6، فستبدو هكذا:

  4
 / \
2   6

وإذا أضفنا بعد ذلك 3، فستبدو هكذا

   4
 /   \
2     6
 \
  3

وإذا أضفنا بعد ذلك 1 و5 و7، فستبدو هكذا

      4
    /   \
   /     \
  2       6
 / \     / \
1   3   5   7