[Powered by Google Translate] [بحث ثنائي] [باتريك شميد - جامعة هارفارد] [هذا CS50. - CS50.TV] 

إذا أعطيت لك قائمة بأسماء حرف ديزني بالترتيب الأبجدي ويطلب منك أن تجد ميكي ماوس، كيف يمكنك أن تذهب نحو القيام بذلك؟ يمكن للمرء أن يكون طريقة واضحة لمسح القائمة من بداية وتحقق كل اسم لمعرفة ما اذا كان ميكي. ولكن كما تقرأ علاء الدين، أليس، ارييل، وهكذا دواليك، فسوف ندرك بسرعة أن تبدأ في الجزء الأمامي من قائمة ليست فكرة جيدة. حسنا، ربما يجب أن تبدأ العمل الى الوراء من نهاية القائمة. الآن تقرأ طرزان، الابره، سنو وايت، وهكذا دواليك. ومع ذلك، هذا لا يبدو وكأنه أفضل وسيلة للذهاب حول هذا الموضوع. 

حسنا، هناك طريقة اخرى انه يمكنك الذهاب عن القيام بذلك هو محاولة لتضييق لائحة الأسماء التي لديك للنظر في. منذ كنت تعرف أنهم في الترتيب الأبجدي، هل يمكن أن مجرد إلقاء نظرة على الأسماء الموجودة في منتصف القائمة ومعرفة ما اذا كان ميكي ماوس هو قبل أو بعد هذا الاسم. النظر في الاسم الأخير في العمود الثاني كنت أدرك أن لM ميكي يأتي بعد J للالياسمين، لذلك كنت ببساطة تجاهل النصف الأول من القائمة. ثم ننظر ربما كنت في الجزء العلوي من العمود الأخير ونرى أنه يبدأ رابونزيل. ميكي يأتي قبل رابونزيل، يبدو أننا يمكن تجاهل العمود الأخير أيضا. استمرارا للاستراتيجية البحث، سترى بسرعة أن ميكي في النصف الأول من القائمة المتبقية من أسماء وأخيرا وجدت ميكي يختبئ بين ميرلين وميني. 

وكان ما فعلت فقط البحث الثنائية أساسا. لأن هذا يوحي الاسم، فإنه يؤدي استراتيجيتها البحث في مسألة ثنائية. ماذا يعني هذا؟ كذلك، ونظرا لقائمة العناصر التي تم فرزها، خوارزمية البحث الثنائي قرارا ثنائي - إلى اليسار أو اليمين، أكبر من أو أقل من، أبجديا قبل أو بعد - في كل نقطة. الآن أن لدينا الاسم الذي يسير جنبا إلى جنب مع هذه الخوارزمية البحث، دعونا ننظر في مثال آخر، ولكن هذه المرة مع قائمة من الأرقام التي تم فرزها. ويقول نحن نبحث عن عدد 144 في هذه القائمة من الأرقام التي تم فرزها. تماما مثل من قبل، نجد أن هذا العدد في منتصف - وهو في هذه الحالة هو 13 - 144 ومعرفة ما إذا كان أكبر من أو أقل من 13. لأنه من الواضح أن أكبر من 13، يمكن لنا أن نتجاهل كل ما هو 13 أو أقل والتركيز فقط على النصف المتبقي. لأن لدينا الآن عدد من البنود حتى غادر، نحن ببساطة اختيار عدد والمقرب من وسطها. في هذه الحالة نختار 55. يمكن أن يكون بسهولة مثلما اختار 89. حسنا. مرة أخرى، 144 أكبر من 55، لذلك نذهب إلى اليمين. لحسن الحظ بالنسبة لنا، وعدد الأوسط التالي هو 144، واحد ونحن تبحث عنه. في ذلك من أجل العثور على 144 باستخدام بحث ثنائي، ونحن قادرون على العثور عليه في 3 خطوات فقط. إذا كنا قد استخدمت خطية البحث هنا، لكان قد اتخذ لنا 12 خطوات. كما واقع الأمر، لأن هذا الأسلوب البحث نصفين عدد العناصر ذلك أن ينظر إلى في كل خطوة، وسوف تجد هذا البند انها تبحث عن في حوالي سجل من عدد العناصر في القائمة. والآن بعد أن رأينا 2 أمثلة، دعونا نلقي نظرة على بعض شبة الكود لوظيفة العودية التي تطبق بحث ثنائية. ابتداء من الأعلى، ونحن نرى أن لدينا لإيجاد الوظيفة التي تستغرق 4 وسائط: الرئيسية، مجموعة، دقيقة، والحد الأقصى. المفتاح هو الرقم الذي نحن نبحث عن، 144 وذلك في المثال السابق. مجموعة لائحة الأرقام التي نحن نبحث. Min و Max هي مؤشرات لمواقف الحد الأدنى والحد الأقصى أننا نبحث حاليا في. لذلك عندما نبدأ، وسوف يكون الحد الأدنى والحد الأقصى الصفر ستكون مؤشر الحد الأقصى للمجموعة. ونحن تضييق نطاق البحث إلى أسفل، وسوف نقوم بتحديث Min و Max ليكون مجرد النطاق الذي لا نزال نبحث فيها 

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

كنت قد لاحظت أن لهذه الخوارزمية في العمل، قائمة أرقام لابد من فرزها. وبعبارة أخرى، يمكن أن نجد فقط 144 باستخدام البحث الثنائية إذا تنظم جميع الأرقام من الأدنى إلى الأعلى. لو كان هذا ليس هو الحال، ونحن لن تكون قادرة على استبعاد نصف العدد في كل خطوة. لذلك لدينا 2 خيارات. إما أن نأخذ قائمة لم يتم فرزها وفرزها من قبل باستخدام البحث الثنائية، أو يمكن أن نتأكد من أن يتم فرز قائمة الأرقام ونحن إضافة أرقام لها. وهكذا، بدلا من الفرز فقط عندما لدينا للبحث، لماذا لا تبقي قائمة تم فرزها في جميع الأوقات؟ 

طريقة واحدة للحفاظ على قائمة أرقام مصنفة في الوقت الذي تسمح في وقت واحد واحد لإضافة أو نقل الأرقام من هذه القائمة هو عن طريق استخدام ما يسمى شجرة البحث الثنائية. شجرة البحث الثنائية هو بنية البيانات التي تحتوي على 3 خصائص. أولا، الشجرة الفرعية الأيسر من أي عقدة فقط يحتوي على قيم التي هي أقل من أو تساوي القيمة للعقدة. الثانية، الشجرة الفرعية حق عقدة يحتوي فقط على القيم التي هي أكبر من أو تساوي القيمة للعقدة. وأخيرا، فإن كلا من الأشجار الفرعية الأيسر والأيمن من كافة العقد هي أيضا أشجار البحث الثنائية. دعونا ننظر إلى مثال على ذلك مع الأرقام التي استخدمناها في وقت سابق نفس. لأولئك منكم الذين لم يروا شجرة علوم الكمبيوتر من قبل، اسمحوا لي أن أبدأ أقول لك أن شجرة تنمو إلى أسفل علوم الكمبيوتر. نعم، على عكس الأشجار كنت معتادا على، جذر شجرة كمبيوتر العلم هو في القمة، ويترك هي في القاع. ويسمى كل مربع القليل عقدة، وترتبط العقد مع بعضها البعض عن طريق الحواف. وبالتالي فإن جذور هذه الشجرة هي قيمة عقدة مع القيمة 13، التي لديها 2 أطفال العقد مع القيم 5 و 34. شجرة فرعية هي الشجرة التي تتكون فقط من خلال النظر في القسم الفرعي من شجرة بأكملها. 

على سبيل المثال، الشجرة الفرعية اليسرى من 3 عقدة الشجرة التي أنشأتها العقد 0، 1، و 2. لذا، إذا رجعنا إلى خصائص ثنائي شجرة البحث، ونحن نرى أن كل عقدة في شجرة يتوافق مع كافة الخصائص 3، أي، الشجرة الفرعية اليسار يحتوي فقط على القيم التي هي أقل من أو يساوي قيمة عقدة؛ الشجرة الفرعية حق كافة العقد يحتوي فقط على القيم التي هي أكبر من أو يساوي قيمة للعقدة، و الأشجار الفرعية كل من اليسار واليمين من كافة العقد أيضا أشجار البحث الثنائية. على الرغم من أن هذه الشجرة تبدو مختلفة، وهذا هو البحث الثنائي صالح شجرة لنفس المجموعة من الأرقام. كما واقع الأمر، هناك العديد من السبل الممكنة التي يمكن أن تخلق بحث ثنائي صالحة شجرة من هذه الأرقام. حسنا، دعونا نعود لأول واحد خلقنا. ذلك ما يمكن أن نقوم به مع هذه الأشجار؟ حسنا، يمكننا ببساطة شديدة العثور على قيم الحد الأدنى والحد الأقصى. يمكن العثور على قيم الحد الأدنى عن طريق الذهاب دائما إلى اليسار حتى هناك عقد لا أكثر لهذه الزيارة. وعلى العكس، إلى العثور على واحد فقط كحد أقصى ببساطة تنخفض هذه النسبة إلى الحق في كل مرة. 

العثور على أي رقم آخر ليس هذا هو الحد الأدنى أو الحد الأقصى لل هو بنفس السهولة. ويقول نحن نبحث عن عدد 89. نحن ببساطة تحقق قيمة كل عقدة وانتقل إلى اليسار أو اليمين، اعتمادا على ما إذا القيمة للعقدة أقل من أو أكبر من واحد ونحن تبحث عنه. لذلك، ابتداء من الجذر من 13، ونحن نرى أن 89 أكبر، وهكذا نذهب إلى اليمين. ثم نرى عقدة لمدة 34، ومرة ​​أخرى نذهب إلى اليمين. 89 هو لا يزال أكبر من 55، لذلك نحن مواصلة الذهاب إلى اليمين. نأتي بعد ذلك مع عقدة مع القيمة من 144 ويذهب إلى اليسار. وها، 89 هو حق هناك. 

شيء آخر يمكن أن نفعله هو طباعة جميع الأرقام عن طريق إجراء اجتياز اتباعها. ويعني اجتياز اتباعها لطباعة كل شيء في الشجرة الفرعية اليسار تليها طباعة العقدة نفسها ثم يتبع ذلك الطباعة في الشجرة الفرعية كل شيء حق. على سبيل المثال، دعونا نلقي بحثنا ثنائي المفضلة شجرة وطباعة الأرقام في ترتيب فرزها. نبدأ في جذور 13، ولكن قبل الطباعة لدينا 13 لطباعة كل شيء في الشجرة الفرعية اليسار. لذلك نحن نذهب إلى 5. لا يزال لدينا للذهاب أعمق الأعماق في شجرة حتى نجد العقدة أقصى اليسار، الذي هو صفر. بعد الطباعة الصفر، نعود حتى 1 و طباعة إلى ذلك. ثم نذهب إلى الشجرة الفرعية الحق، الذي هو 2، وطباعة إلى ذلك. والآن بعد أن ننتهي مع أن الشجرة الفرعية، يمكننا العودة حتى 3 و طباعته. استمرار النسخ الاحتياطي، ونحن طباعة 5 و ثم 8. غادر الآن أننا قد أكملت كامل الشجرة الفرعية، يمكننا طباعة ال 13 وبدء العمل على الشجرة الفرعية حق. نحن هوب وصولا الى 34، ولكن قبل الطباعة لدينا 34 لطباعة الشجرة الفرعية اليسرى. لذلك نحن طباعة 21؛ ثم نصل إلى طباعة 34 وزيارته الشجرة الفرعية الصحيح. منذ 55 ليس لديه الشجرة الفرعية اليسرى، ونحن طباعته وتستمر على الشجرة الفرعية لحقها. 144 لديه الشجرة الفرعية اليسار، ولذا فإننا طباعة ال 89، تليها 144، وأخيرا العقدة أقصى اليمين من 233. فإنه يوجد لديك، ويتم طباعة كافة الأرقام في ترتيب من الأدنى إلى الأعلى. 

إضافة شيء إلى شجرة غير مؤلم نسبيا أيضا. كل ما عليك القيام به هو التأكد من أن نتبع 3 خصائص شجرة ثنائية البحث ثم قم بإدراج القيمة حيث هناك مساحة. دعونا نقول أننا نريد أن تضاف قيمة 7. منذ 7 هو أقل من 13، نذهب إلى اليسار. ولكن هذا أكبر من 5، لذلك نحن تعبر إلى اليمين. نظرا لأنه أقل من 8 و 8 هو عقدة طرفية، نضيف 7 إلى الطفل الأيسر من 8. فويلا! لقد أضفنا عددا لدينا ثنائي شجرة البحث. 

إذا يمكننا أن نضيف الأمور، علينا أن نكون أكثر قدرة على حذف الأشياء أيضا. لسوء الحظ بالنسبة لنا، وحذف قليلا أكثر تعقيدا - ليس كثيرا، ولكن قليلا فقط. هناك 3 سيناريوهات المختلفة التي علينا أن ننظر عند حذف عناصر من أشجار البحث الثنائية. الأولى، وأسهل الحالة هو أن العنصر هو عقدة طرفية. في هذه الحالة، ونحن ببساطة حذف ذلك والمضي قدما في أعمالنا. نقول أننا نريد حذف 7 أن أضفنا للتو. حسنا، نجد ببساطة، إزالته، وهذا كل شيء. حالة المقبل هو إذا كانت العقدة لديها سوى 1 طفل. هنا يمكننا حذف العقدة، ولكن علينا أولا أن نتأكد من للاتصال الشجرة الفرعية ما تبقى الآن بلا أب إلى الوالد من العقدة حذفنا فقط. نقول أننا نريد حذف 3 من شجرة لدينا. أخذنا عنصر تابع لتلك العقدة ونعلق عليه إلى الأصل للعقدة. في هذه الحالة، نحن الآن إرفاق 1 إلى 5. هذا يعمل دون مشكلة لأننا نعرف، وفقا لشجرة الملكية ثنائي البحث، هي أن كل شيء في الشجرة الفرعية اليسرى من 3 أقل من 5. والآن بعد أن أخذ في 3 الشجرة الفرعية رعاية، يمكننا حذفه. الحالة الثالثة والأخيرة هي الأكثر تعقيدا. هذا هو الحال عندما نريد أن عقدة حذف يوجد 2 الأطفال. من أجل القيام بذلك، علينا أولا أن تجد العقدة التي لديها قيمة أكبر المقبلة، مبادلة اثنين، ثم قم بحذف عقدة في السؤال. لاحظت العقدة التي لديها قيمة أكبر المقبلة لا يمكن أن يكون في حد ذاته 2 الأطفال حيث أن الطفل في اليسار يكون أفضل مرشح لأكبر المقبلة. ولذلك، وحذف عقدة مع 2 الأطفال تبلغ من 2 مبادلة العقد، ومن ثم تتم معالجة حذف من 1 من المادتين 2 المذكورة أعلاه. على سبيل المثال، دعنا نقول أننا نريد أن حذف العقدة الجذر، 13. أول شيء نقوم به هو أن نجد أكبر قيمة تالية في شجرة التي، في هذه الحالة، هو 21. نحن مبادلة ثم العقد 2، مما يجعل 13 ألف ورقة و 21 عقدة مجموعة الوسطى. الآن يمكننا ببساطة حذف 13. 

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

فإنه يوجد لديك. تعرف الآن حول البحث الثنائية والأشجار البحث الثنائي. أنا باتريك شميد، وهذا هو CS50. [CS50.TV] يمكن للمرء أن يكون طريقة واضحة لمسح القائمة من ... [صوت] ... عدد العناصر ... نعم [يضحك] أضف ... عقدة augh ... 234. ياي >>! كان ذلك -