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

التعليمات

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

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

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