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

التعليمات

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

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

لنفترض أن لدينا المصفوفة [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

شكر وتقدير

أنشأ habere-et-dispertire هذه الصور باستخدام PGF/TikZ من تأليف Till Tantau.

تعليمات خاصة بـ CoffeeScript

يجب أن تحتوي نسخة BinarySearchTree على 3 خصائص: data وleft وright.

ويجب أن تحتوي النسخة على هذه الطرق:

• insert التي تضيف بيانات جديدة إلى الشجرة. وستضيف عقدة "ورقة" جديدة في مكان ما من الشجرة.
• each التي تأخذ وسيطًا هو "callback". أي دالة ستُستدعى على كل قطعة بيانات في الشجرة بالترتيب.

هذا التمرين مكان رائع للتدرب على الاستدعاء الذاتي.