كتب infinite trees

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

الشرط الأساسي للمسح هو زيارة كل رأس في نهاية المطاف. بالنسبة إلى الأشجار اللانهائية، غالبًا ما تفشل الخوارزميات البسيطة في ذلك. على سبيل المثال، في حالة وجود شجرة ثنائية ذات عمق غير محدود، فإن بحث العمق أولاً سيذهب في جانب واحد (عن طريق الجانب الأيسر) من الشجرة، ولن يزور الباقي أبدًا، ومن المؤكد أن المسح بالترتيب اللاحق أو الترتيب السابق لن يزور أية رأس، لأنها لم تصل إلى ورقة (وفي الواقع لن تفعل ذلك أبدا). على النقيض من ذلك، فإن مسح العرض أولا (ترتيب المستوى) سيعبر شجرة ثنائية ذات عمق لا متناهٍ دون مشكلة، وفي الواقع سيمسح أي شجرة بعامل تفرع محدد.

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

يمكن تقديم تحليل أكثر تطوراً لوقت التشغيل عبر الأرقام الترتيبية اللانهائية ؛ على سبيل المثال، سيتخذ بحث العرض لشجرة العمق 2 أعلاه خطوات ω · 2: ω للمستوى الأول، ثم ω للمستوى الثاني.

وبالتالي، فإن عمليات البحث البسيطة الأولى أو العميقة الأولى لا تجتاز كل شجرة لا نهائية، وليست فعالة في الأشجار الكبيرة جدًا. ومع ذلك، يمكن للطرق الهجينة اجتياز أي شجرة لا حصر لها (قابلة للعد)، وذلك بشكل أساسي عبر وسيطة قطرية ("قطري" - مزيج من الرأسي والأفقي - يتوافق مع مزيج من العمق والاتساع).

بشكل ملموس، بالنظر إلى شجرة المتفرعة بلا حدود من العمق اللانهائي، قم بتسمية الجذر ()، أبناء الجذر (1)، (2)،...، أحفاد (1، 1)، (1، 2)،...، (2)، 1)، (2، 2)،...، وهلم جرا. العقد هي بالتالي في واحد الى واحد مراسلات مع تسلسل محدود (ربما فارغة) من أرقام موجبة، والتي هي قابل للعد ويمكن وضعها في الدرجة الأولى من مجموع الإدخالات، ومن ثم من قبل النظام lexicographic ضمن مبلغ معين (إلا بشكل محدود تُلخص العديد من التسلسلات بقيمة معينة، وبالتالي يتم الوصول إلى جميع المدخلات - هناك عددًا محدودًا من التراكيب ذات العدد الطبيعي المحدد، وتحديداً التراكيب 2 ^{n − 1} من n ≥ 1 )، والتي تعطي اجتيازًا. صراحة:

0: () 1: (1) 2: (1، 1) (2) 3: (1، 1، 1) (1، 2) (2، 1) (3) 4: (1، 1، 1، 1) (1، 1، 2) (1، 2، 1) (1، 3) (2، 1، 1) (2، 2) (3، 1) (4)

إلخ

يمكن تفسير ذلك على أنه تعيين الشجرة الثنائية العمق اللانهائية على هذه الشجرة ثم تطبيق بحث اتساع: استبدل الحواف "السفلية" التي تربط العقدة الرئيسية بأطفالها الثانيين واللاحقين بأطراف "يمينية" من الطفل الأول إلى الثاني الطفل، من الطفل الثاني إلى الطفل الثالث، إلخ. وبالتالي في كل خطوة، يمكن للمرء إما النزول (إلحاق (، 1) إلى النهاية) أو الانتقال يمينًا (إضافة واحد إلى الرقم الأخير) (باستثناء الجذر، وهو إضافي ويمكنه فقط)، مما يدل على المراسلات بين الشجرة الثنائية اللانهائية والترقيم أعلاه ؛ مجموع المدخلات (ناقص واحد) يتوافق مع المسافة من الجذر، والتي تتفق مع العقد 2 ^{n −1} على عمق n − 1 في الشجرة الثنائية اللانهائية (2 يتوافق مع الثنائية).