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

التعليمات

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

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

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

التنفيذ

يُعدّ تنفيذ بنية شجرة فعّالة وقابلة للتعديل في Cairo (أو في أي لغة وظيفية بحتة ذات ذاكرة غير قابلة للتغيير) أمرًا صعبًا، لأن هذه اللغات مصمَّمة لتجنّب تغيير البيانات بعد إنشائها. يعني هذا الثبات أنه بدلًا من تحديث عقدة الشجرة مباشرةً، يجب إنشاء نسخة جديدة من الشجرة كلما عدّلتها.

لتوضيح سبب ذلك، تخيّل بنية شجرة ثنائية بسيطة، حيث لكل عقدة ابن أيسر وابن أيمن. لنفترض أننا نبدأ بشجرة صغيرة كهذه:

       1
      / \
     2   3

الآن، لنفترض أننا نريد إضافة عقدة جديدة 4 كابن أيسر للعقدة 2. في لغة وظيفية بحتة (مثل Cairo أو Haskell)، الذاكرة غير قابلة للتغيير، لذلك لا يمكننا ببساطة إضافة العقدة 4 مباشرةً إلى 2. بدلًا من ذلك، علينا إنشاء نسخة جديدة من كل عقدة على طول المسار من الجذر إلى العقدة المعدَّلة، لأن كل عقدة على هذا المسار تشير الآن إلى شجرة فرعية جديدة أو معدَّلة.

وهذا ما ستبدو عليه العملية:

1. أضف العقدة 4 إلى العقدة 2:

   • أنشئ نسخة جديدة من العقدة 2، صار فيها 4 ابنًا أيسر.

       2'
      / 
     4   
   

2. حدّث العقدة الجذرية:

   • بما أن العقدة 1 كانت تشير أصلًا إلى العقدة 2 القديمة، ننشئ نسخة جديدة من العقدة الجذرية 1' تشير الآن إلى العقدة المحدَّثة 2' على اليسار، وتُبقي العقدة 3 على اليمين.

       1'
      / \
     2'  3
   

وبذلك تصبح الشجرة الناتجة:

       1'
      / \
     2'  3
    /
   4

لا تزال هذه الشجرة الجديدة (1') تشبه الأصلية، لكن بمسار محدَّث. النقطة الجوهرية هي أننا اضطررنا إلى إعادة إنشاء كل عقدة على طول المسار (من 1 إلى 2) للحفاظ على الثبات، لأن العقد الموجودة لا يمكن تعديلها في مكانها. لا تزال الشجرة الأصلية موجودة (على سبيل المثال، بالنسبة إلى جميع المراجع التي تشير إلى جذرها الأصلي 1)، بينما تمثّل هذه الشجرة الجديدة الحالة المعدَّلة.

في الأشجار الكبيرة، قد يصبح هذا الأسلوب مكلفًا، إذ يتطلّب كل تعديل جديد إعادة إنشاء مسار من العقد يمتد من الجذر إلى العقدة المحدَّثة، حتى لو لم يتغيّر فعليًا إلا جزء صغير من الشجرة.