books derivation of the mean case

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

فيما يأتي، من أجل عمليات البحث الناجحة، سيُفترض أن البحث الثنائي يحصل بصورة متكافئة عن كل عنصر في المصفوفة، أمَّا من أجل عمليات البحث غير الناجحة، فسيُفترض أن البحث الثنائي يحصل بصورة متكافئة على الفواصل بين العناصر غير الموجودة في المصفوفة وعلى الفواصل بين العناصر غير الموجودة وتلك الموجودة في المصفوفة.

عمليات البحث الناجحة

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

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

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

أمَّا متوسط عدد التكرارات فيمكن أن يحسب وفق معادلة الحالة المتوسطة وتكون قيمته: .

ويمكن أيضاً تبسيط طول المسارات الداخلية أيضاً وفق ما يأتي:

وإذا عُوِّضت القيمة السابقة لطول المسارات الداخلية في معادلة حساب متوسط عدد التكرارات لعملية بحث ناجحة، أي ، فإنها تؤول إلى الشكل التالي:

من أجل عدد صحيح ما ، فإن هذه العلاقة تكافئ تلك المُستعملة لحساب الحالة المتوسطة في بحث ناجح.

عمليات البحث غير الناجحة

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

يُعرَّف المسار الخارجي بأنه مسارٌ يبدأ من الجذر وينتهي في عقدة خارجية، وطول المسار الخارجي نحو عنصر ما بأنه عدد الوصلات فيه، وطول المسار الخارجي هو مجموع أطوال المسارات الخارجية نحو عناصر المصفوفة جميعها.

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

قُسِّم طول المسار الخارجي على بدلًا من لأن هناك مساراً خارجياً، يمثل الفواصل بين عناصر المصفوفة نفسهم وبين عناصر المصفوفة والعناصر الخارجية.

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

بتعويض القيمة الناتجة لطول المسار الخارجي في معادلة حساب متوسط عدد التكرارات لعملية بحث غير ناجح ، يمكن الحصول على المعادلة التالية: