[Powered by Google Translate] [بائنری تلاش کریں] [پیٹرک Schmid - ہارورڈ یونیورسٹی] یہ [CS50 ہے. CS50.TV] - 

اگر میں آپ کو حروف تہجی کی ترتیب میں دی ڈزنی کے کردار کے ناموں کی ایک فہرست اور آپ سے کہا کہ مکی ماؤس کو تلاش کرنے کے لئے، آپ کو ایسا کرنے کے بارے میں کیسے جا سکتا ہے؟ ایک واضح راستہ شروع سے فہرست کو اسکین ہوگا اور ہر اگر یہ مکی ہے دیکھنے کے نام چیک کرنے کے لیے ہیں. لیکن، جیسا کہ آپ علاء، یلس، ایریل، پڑھیں اور وغیرہ آپ کو تیزی سے احساس ہوگا کہ فہرست کے سامنے سے شروع ایک اچھا خیال نہیں تھا. ٹھیک ہے، ہو سکتا ہے کہ آپ کی فہرست کے آخر سے پیچھے کی طرف کام کرنا شروع کر دینا چاہئے. اب آپ ٹارجن، سلائی، ہمشوےت، اور وغیرہ پڑھیں. پھر بھی، یہ اس کے بارے میں جانے کے لئے سب سے بہتر طریقہ کی طرح نہیں لگتا ہے. 

ٹھیک ہے، ایک اور راستہ ہے جس سے کہ آپ کو ایسا کرنے کے بارے میں جا سکتے ہیں کو محدود کرنے کی کوشش کریں ان کے ناموں کی فہرست ہے کہ آپ کو دیکھنے کے لئے ہے. چونکہ تم جانتے ہو کہ وہ حروف تہجی کی ترتیب میں ہیں، آپ کو فہرست کے وسط میں نام پر ذرا دیکھو سکتا ہے چیک کرنے کے لیے اور اگر مکی ماؤس سے پہلے یا اس کے بعد اس کا نام یہ ہے. دوسرے کالم کی تلاش میں آخری نام تمہیں احساس ہے کہ مکی کے لئے M جیسمین کے لئے J بعد آتا ہے چاہتے ہیں، تو آپ کو فہرست کی پہلی ششماہی صرف نظر انداز تھا. اس وقت تم گزشتہ کالم کے سب سے اوپر دیئے گئے شاید لگوگی دیکھ کر اور یہ کہ اس Rapunzel کے ساتھ شروع ہوتی ہے. مکی Rapunzel کے سامنے آتا ہے، جیسا کہ ہم گزشتہ کالم کو نظر انداز کے طور پر کر سکتے ہیں لگتا ہے. تلاش کی حکمت عملی جاری، آپ کو فوری طور پر دیکھیں گے کہ مکی ناموں کی باقی فہرست کی پہلی ششماہی میں ہے اور آخر میں تلاش مکی مرلن اور Minnie کے درمیان چھپے. 

تم نے ابھی کیا کیا وہ بنیادی طور پر بائنری تلاش تھی. جیسا کہ اس کے نام کا مطلب ہے، یہ ایک بائنری معاملے میں اس کی تلاش کی حکمت عملی انجام دیتا ہے. اس کا کیا مطلب ہے؟ ٹھیک ہے، کے مطابق اشیاء کی ایک فہرست دی گئی ہے، بائنری تلاش الگورتھم میں ایک بائنری فیصلہ کرتا ہے - بائیں یا دائیں یا اس سے زیادہ سے کم، انگریزی حروف تہجی کے پہلے یا بعد میں - ہر موڑ پر. اب جب کہ ہم ایک نام ہے جو اس تلاش کے الگورتھم کے ساتھ ساتھ جاتا ہے ہے، کی ایک اور مثال کو دیکھو، لیکن کے مطابق تعداد کی ایک فہرست کے ساتھ اس وقت. کہو کہ ہم کے مطابق تعداد کے اس فہرست میں 144 نمبر کے لئے تلاش کر رہے ہیں. بس پہلے کی طرح، ہم نمبر ہے کہ درمیان میں ہے تلاش کریں - جو اس کیس میں 13 ہے - اور اگر 144 یا اس سے زیادہ 13 سے کم ہے دیکھ. چونکہ یہ واضح طور پر 13 سے زیادہ ہے، ہم سب کچھ نظر انداز کر سکتے ہیں جو 13 یا اس سے کم ہے اور باقی نصف پر توجہ. چونکہ اب ہم اشیاء کی بھی تعداد کو چھوڑ دیا ہے، ہم صرف ایک بڑی تعداد ہے جو مشرق قریب ہے کو منتخب کریں. اس صورت میں ہم 55 کا انتخاب کرتے ہیں. ہم بالکل اسی طرح جیسے آسانی سے 89 کا انتخاب کیا جا سکتا ہے. ٹھیک ہے. ایک بار پھر، 144 55 سے بڑا ہے، تو ہم حق پر ہیں. خوش قسمتی سے ہمارے لئے، اگلے مشرق کی تعداد 144 ہے، جس سے ہم کے لئے تلاش کر رہے ہیں. لہذا اس میں حکم 144 ایک بائنری تلاش کا استعمال کرتے ہوئے تلاش کرنے کے لئے، ہم اسے صرف 3 اقدامات میں تلاش کرنے کے قابل ہو. اگر ہم لکیری تلاش یہاں استعمال کیا جاتا ہے، یہ ہمیں 12 اقدامات کریں گے لیا ہے. حقیقت تو یہ ہے کے طور پر، کے بعد سے اس تلاش کے طریقہ کار اشیاء کی تعداد حصوں اس کے ہر قدم پر کو دیکھنے کے لئے ہے، یہ آئٹم مل جائے گا اس کے لئے تلاش کر رہا ہے میں فہرست میں اشیاء کی تعداد کے لاگ ان کے بارے میں. اب کہ ہم نے 2 مثال کے طور پر دیکھا ہے، پر ایک نظر ڈالیں ایک پنراورتی تقریب ہے جو بائنری تلاش نافذ کے لئے کچھ pseudocode. سب سے اوپر شروع ہو رہا ہے، ہم دیکھتے ہیں کہ ہم نے ایک تقریب ہے جو 4 دلائل لیتا ہے تلاش کرنے کے لئے ہے: کلید، صف، کم از کم، اور زیادہ سے زیادہ. کلید نمبر پر ہے کہ ہم نے کے لئے، گزشتہ مثال میں 144 تلاش کر رہے ہیں ہے. صف نمبروں کی فہرست ہے کہ ہم تلاش کر رہے ہیں ہے. کم از کم اور زیادہ سے زیادہ کم از کم اور زیادہ سے زیادہ پوزیشن کے سوچکانکوں ہیں کہ ہم فی الحال کر رہے ہیں. تو جب ہم شروع منٹ صفر ہو جائے گا اور زیادہ سے زیادہ صف کی زیادہ سے زیادہ فہرست ہو جائے گا. جب ہم تلاش نیچے محدود، ہم کم از کم اور زیادہ سے زیادہ اپ ڈیٹ ہو جائے گا صرف رینج کہ ہم ابھی بھی اندر تلاش کر رہے ہیں. 

دلچسپ حصہ میں سب سے پہلے پر دو پہلی بات ہم کرتے ہیں midpoint تلاش، انڈیکس نصف صف کہ ہم اب بھی غور کر رہے ہیں کم از کم اور زیادہ سے زیادہ کے درمیان ہے. اس کے بعد ہم صف کی قدر میں اس midpoint مقام پر نظر دیکھتے ہیں اور اگر نمبر پر ہے کہ ہم تلاش کر رہے ہیں اس چابی سے بھی کم ہے. اگر اس پوزیشن میں تعداد کم ہے، تو اس کا مطلب ہے کہ چابی اس کی حیثیت کو بائیں تمام نمبر سے بڑا ہے. تو ہم بائنری سرچ فنکشن کو پھر سے فون کر سکتے ہیں، لیکن اس وقت کم از کم اور زیادہ سے زیادہ پیرامیٹرز کو اپ ڈیٹ کر صرف آدھے پڑھ یا اس سے زیادہ قیمت ہم صرف کی طرف دیکھ رہے تھے کے برابر ہے. دوسری طرف، اگر چابی صف کی موجودہ midpoint تعداد سے کم ہے، ہم بائیں طرف جانے کے لئے اور تمام نمبر زیادہ ہیں کو نظر انداز کرنا چاہتے ہیں. ایک بار پھر، ہم کم از کم اور زیادہ سے زیادہ تازہ کاری کی حد کے ساتھ بائنری تلاش ہے لیکن اس بار فون صرف کم نصف شامل کرنے کے لئے. اگر صف میں موجودہ midpoint قدر ہے نہ سے بڑا اور نہ ہی چابی سے چھوٹا ہے، تو یہ چابی کے برابر ہونا چاہیے. اس طرح، ہم موجودہ midpoint انڈیکس صرف، واپس اور ہم کیا کر رہے ہیں کر سکتے ہیں. آخر میں، یہ یہاں چیک کیس کے لئے یہ ہے کہ تعداد اصل تعداد ہم تلاش کر رہے ہیں کی صف میں نہیں ہے. اگر حد سے زیادہ سے زیادہ انڈیکس ہے کہ ہم تلاش کر رہے ہیں کبھی بھی کم از کم سے کم ہے، کا مطلب ہے کہ ہم بہت دور چلی گئی ہے. چونکہ نمبر ان پٹ صف میں نہیں تھا، ہم -1 واپس کہ کچھ نہیں پر دلالت پایا گیا تھا. 

تم نے کہ یہ الگورتھم کے لئے کام کرنے کے لئے محسوس کیا ہو سکتا ہے، نمبروں کی فہرست کے مطابق ہے. دوسرے الفاظ میں، ہم نے 144 صرف بائنری تلاش کا استعمال کرتے ہوئے تلاش کر سکتے ہیں اگر تمام کی تعداد سب سے زیادہ سے سب سے کم کرنے کا حکم دیا ہے. اگر یہ معاملہ نہیں تھے، ہم نے ہر قدم پر کی تعداد کے نصف پر خارج کرنے کے قابل نہیں ہو گا. تو ہم 2 اختیارات ہیں. یا تو ہم نے ایک ناچھانٹا ہوا کی فہرست لے لو اور بائنری تلاش کا استعمال کرتے ہوئے کرنے سے پہلے یہ ترتیب کر سکتے ہیں، یا ہم اس بات کا یقین کر لیں کہ کہ نمبروں کی فہرست کے طور پر ہم اس تعداد کو شامل کے مطابق ہے کر سکتے ہیں. اس طرح، جب ہم تلاش ہے حل کرنے کے بجائے، ہر وقت کے مطابق فہرست کو برقرار رکھنے کیوں نہیں؟ 

کرتے ہوئے ایک اعداد کی ایک فہرست کو برقرار رکھنے کا ایک طریقہ کے مطابق بیک وقت کی اجازت دی ایک یا ایک سے منتقل کی تعداد کو اس فہرست سے شامل ملاقات کی ایک بائنری تلاش درخت کچھ کا استعمال کرتے ہوئے کی طرف سے ہے. ایک بائنری تلاش درخت ایک آنکڑا ڈھانچہ ہے کہ 3 خصوصیات ہے ہے. سب سے پہلے، کسی نوڈ کے بائیں subtree اس سے بھی کم ہیں صرف اقدار پر مشتمل ہے نوڈ قیمت کے برابر یا اس. دوسرا، ایک نوڈ کا حق ہے subtree صرف اقدار کو اس سے بھی زیادہ ہیں پر مشتمل ہے نوڈ قیمت کے برابر یا اس. اور، آخر میں، تمام مراکز کی دونوں بائیں اور دائیں subtrees بھی بائنری تلاش کے پیڑ ہیں. چلو ہم پہلے کرتے تھے اسی تعداد کے ساتھ ایک مثال کو دیکھو. ، تم میں سے ان لوگوں کو جو دیکھا کمپیوٹر سائنس کے درخت سے پہلے کبھی نہیں کے لئے کے وزٹرز کا ریکارڈ رکھا جائے گا. میرے تم سے کہہ رہی ہے کہ کمپیوٹر سائنس کے درخت کے نیچے اگنے کی طرف سے شروع. جی ہاں،، درخت آپ عادی رہے ہیں کے برعکس کمپیوٹر سائنس کے درخت کی جڑ سب سے اوپر ہے، اور پتیوں کے نیچے دیے گئے ہیں. ہر چھوٹا خانہ ایک نوڈ کہا جاتا ہے، اور نوڈس کناروں کی طرف سے ایک دوسرے سے جڑے ہوئے ہیں. تو اس درخت کی جڑ میں 13 کی قیمت کے ساتھ ایک نوڈ قیمت ہے، جو 2 اقدار 5 اور 34 کے ساتھ بچوں نوڈس ہے. A subtree درخت ہے جو صرف پورے درخت کی subsection میں دیکھ کر تشکیل میں حصہ لیا ہے. 

مثال کے طور پر، نوڈ 3 0 نوڈس، 1، اور 2 کی طرف سے پیدا بائیں subtree درخت ہے. تو، اگر ہم ایک بائنری تلاش کے درخت کی خصوصیات میں واپس جانا ہم دیکھتے ہیں کہ درخت میں ہر نوڈ تمام 3 خصوصیات، یعنی conforms صرف بائیں subtree اقدار سے کم نوڈ قیمت کے برابر یا اس پر مشتمل ہے؛ تمام مراکز کی subtree صرف اقدار اس سے بڑا یا نوڈ قیمت کے برابر ہیں پر مشتمل ہے، اور تمام مراکز کی بائیں اور دائیں دونوں subtrees بھی بائنری تلاش کے درخت ہیں. اگرچہ یہ درخت مختلف لگ رہا ہے، یہ ایک درست بائنری تلاش درخت ہے کی تعداد کے ایک ہی سیٹ کے لئے. حقیقت تو یہ ہے کے طور پر، بہت ممکن ہے کہ تشکیل دے سکتے ہیں ہیں ان کی تعداد کی طرف سے ایک درست بائنری تلاش درخت. چلو، سب سے پہلے ہمیں پیدا کیا واپس جانا ہے. تو کیا ہم ان درختوں کے ساتھ کیا کر سکتے ہیں؟ ٹھیک ہے، ہم کم از کم اور زیادہ سے زیادہ اقدار بہت آسانی سے حاصل کر سکتے ہیں. کم از کم اقدار ہمیشہ بائیں طرف جا کر پایا جا سکتا ہے تک نہیں مراکز کا دورہ کر رہے ہیں. کے برعکس، زیادہ سے زیادہ ایک کو تلاش کرنے کے لئے صرف صرف ہر وقت حق نیچے جاتا ہے. 

کسی دوسرے نمبر کی تلاش ہے کہ کم از کم یا زیادہ سے زیادہ نہیں ہے کے طور پر آسان ہے. کا کہنا ہے کہ ہم نے 89 نمبر کے لئے تلاش کر رہے ہیں. ہم صرف ہر نوڈ کی قدر کی جانچ پڑتال کریں اور بائیں یا دائیں، پر منحصر ہے کیا نوڈ کی قیمت سے کم یا اس سے بڑا ہے جس سے ہم کے لئے تلاش کر رہے ہیں. لہذا، ہم نے 13 کی جڑ میں شروع ہونے والے دیکھ سکتے ہیں کہ 89 بڑی اور عظیم چیز ہے، اور ہم کو درست کرنے میں جانا. پھر ہم 34 کے لئے نوڈ کو دیکھنے، اور پھر ہم حق پر ہیں. 89 اب بھی 55 سے بڑھ کر ہے، لہذا ہم حق پر جا رہیں. پھر ہم 144 کی قدر کے ساتھ ایک نوڈ کے ساتھ آئے گا اور بائیں. دیکھو اور دیکھو، 89 وہیں ہے. 

ایک دوسری بات یہ ہے کہ ہم کیا کر سکتے ہیں ہے ایک inorder traversal کارکردگی کا مظاہرہ کر کے تمام نمبرز پرنٹ کریں. ایک inorder traversal سب کچھ بائیں subtree میں پرنٹ کا مطلب ہے نوڈ خود چھپائی کے بعد اور پھر بعد سب کچھ درست subtree میں چھپائی سے ہٹ کر ہے. مثال کے طور پر، ہمارے پسندیدہ بائنری تلاش درخت اور باہر کے مطابق ترتیب میں تعداد کو پرنٹ کریں. ہم نے 13 کی جڑ میں شروع، لیکن 13 پرنٹنگ سے پہلے ہم باہر پرنٹ کرنے کے لئے ہے بائیں subtree میں سب کچھ ہے. تو ہم 5. ہم اب بھی درخت میں گہری نیچے جانا ہوگا جب تک کہ ہم نوڈ بائیں سب سے زیادہ ملے ہیں، جو صفر ہے. صفر پرنٹنگ کے بعد، ہم نے 1 واپس جاؤ اور باہر کہ پرنٹ. پھر ہم صحیح subtree، جو 2 ہے، اور کہ پرنٹ. اب جب کہ ہم نے کہ subtree کے ساتھ کیا کیا ہے، ہم واپس جا 3 اور اسے باہر پرنٹ کر سکتے ہیں. بیک اپ جاری، ہم 5 پرنٹ اور پھر 8. اب جب کہ ہم پورے مکمل کر لیا ہے subtree چھوڑ دیا، ہم 13 پرنٹ اور درست subtree پر کام کر شروع کر سکتے ہیں. ہم 34 ہاپ، لیکن 34 پرنٹنگ اس سے پہلے کہ ہم اس کے بائیں subtree پرنٹ ہے. تو ہم باہر 21 پرنٹ کریں، پھر ہم باہر 34 پرنٹ اور اس کے حق subtree کا دورہ کریں. چونکہ 55 نہیں بائیں subtree ہے، ہم اسے باہر پرنٹ اور اس کے صحیح subtree جاری ہے. 144 بائیں subtree ہے، اور ہم باہر 89 پرنٹ، اس کے بعد 144، اور 233 کے آخر میں دائیں سب سے زیادہ نوڈ. وہاں تمہارے پاس ہے، تمام اعداد و شمار سے کم از کم سب سے زیادہ کے لئے میں طباعت ہیں. 

درخت سے کچھ کو شامل کرنے کے ساتھ ساتھ نسبتا پیڑارہت ہے. ہمیں کیا کرنا ہے اس بات کا یقین کر لیں کہ ہم 3 بائنری تلاش کے درخت کی خصوصیات پر عمل بنانے کے ہے اور پھر قدر داخل جہاں جگہ ہے. چلو کا کہنا ہے کہ ہم 7 کی قیمت کو شامل کرنے کے لئے چاہتے ہیں. چونکہ 7 سے کم 13 ہے، ہم بائیں طرف جانا. لیکن یہ 5 سے زیادہ ہے، اس لئے ہم حق گزرنا. چونکہ یہ سے کم 8 اور 8 پتی کی نوڈ ہے، ہم 8 کے بائیں بچے کو 7 شامل کریں. Voila! ہم ہمارے بائنری تلاش کے درخت میں ایک نمبر کا اضافہ کیا ہے. 

اگر ہم چیزیں شامل کر سکتے ہیں، ہم بہتر چیزوں کے طور پر حذف کرنے کے قابل ہو جائے. بد قسمتی سے ہمارے لئے، حذف کرنے سے تھوڑا سا زیادہ پیچیدہ ہے - زیادہ نہیں، لیکن صرف تھوڑا سا. 3 مختلف منظرناموں ہے کہ ہم اس پر غور کرنا ہوگا بائنری تلاش کے پیڑ سے عناصر جب حذف کرنے. سب سے پہلے، سب سے آسان معاملہ ہے کہ عنصر پتی کی نوڈ ہے. اس صورت میں، ہم صرف اس کو خارج کر دیں اور ہمارے کاروبار کے ساتھ جاؤ. کہو کہ ہم 7 کہ ہم صرف شامل کو حذف کرنا چاہتے ہیں. ٹھیک ہے، ہم صرف اس تلاش کو ہٹانے کے، اور یہ کہ یہ ہے. اگلے معاملہ ہے اگر نوڈ صرف 1 بچہ ہے. ہم یہاں نوڈ کو حذف، لیکن ہم سب سے پہلے اس بات کا یقین کرنے کے لئے ہے کر سکتے ہیں کو subtree کہ اب parentless رہ گیا ہے مربوط کرنے کے لئے نوڈ کے والدین پر ہم صرف خارج کر دیا ہے. کہو کہ ہم ہمارے درخت سے 3 کو حذف کرنا چاہتے ہیں. ہم اس نوڈ کے بچے عنصر اور نوڈ کے والدین پر منسلک ہیں. اس صورت میں، ہم نے اب 5 1 رہے ہیں منسلک. یہ ایک مسئلہ کے بغیر کام کرتا ہے کیونکہ ہم جانتے ہیں بائنری تلاش کے درخت جائیداد کے مطابق، 3 کے بائیں subtree میں ہے کہ ہر چیز سے بھی کم 5 تھا. اب جب کہ 3 subtree خیال رکھا ہے، ہم اسے خارج کر سکتے ہیں. تیسرے اور آخری کیس کے سب سے زیادہ پیچیدہ ہے. یہ اس وقت ہے جب نوڈ ہم کو خارج کرنا چاہتے ہیں 2 بچے ہیں. کے لئے ایسا کرنے کے لئے، ہم سب سے پہلے نوڈ کہ اگلے سب سے بڑی قیمت ہے تلاش کرنے کے لئے ہے، دو تبادلہ کریں، اور تو سوال میں نوڈ کو حذف کریں. نوڈ ہے جو اگلے سب سے بڑی قیمت 2 بچے ہیں نہیں خود کر سکتے ہیں نوٹس کے بعد سے اس کے بائیں بچے اگلے سب سے بڑی کے لئے ایک بہتر امیدوار ہو جائے گی. لہذا، 2 بچوں کے ساتھ نوڈ حذف کرنے 2 مراکز کی گماگمن کرنے کے مترادف ہے، اور پھر حذف کرنے سے 1 2 مذکورہ بالا قوانین کے سنبھالا ہے. مثال کے طور پر، دو کا کہنا ہے کہ ہمیں جڑ نوڈ، 13 کو حذف کرنا چاہتے ہیں. پہلی بات ہم کرتے ہیں ہم نے درخت میں اگلے سب سے بڑی قیمت معلوم جو، اس معاملے میں، 21 ہے. ہم تو 2 نوڈس تبادلہ، 13 پتی اور 21 مرکزی گروپ نوڈ بنانے کے. اب ہم 13 صرف اسے خارج کر سکتے ہیں. 

پہلے alluded، بہت ممکن ہے ایک درست بائنری تلاش کے درخت بنانے کے لئے طریقے ہیں. بدقسمتی سے ہمارے لئے، کچھ دوسروں سے بھی بدتر ہیں. مثال کے طور پر، کیا ہوتا ہے جب ہم ایک بائنری تلاش درخت تعمیر کی تعداد کے مطابق فہرست سے؟ تمام اعداد و شمار صرف ہر قدم پر حق شامل ہیں. جب ہم ایک نمبر کے لئے تلاش کرنا چاہتے ہیں، ہمارے پاس اور کوئی چارہ نہیں ہے، لیکن صرف ہر قدم پر حق کو دیکھنے کے لئے. یہ بالکل لکیری تلاش سے بہتر نہیں ہے. اگرچہ ہم نے انہیں یہاں کا احاطہ نہیں کیا جائے گا، اس کے علاوہ، زیادہ پیچیدہ ہوتے ہیں، ڈیٹا ڈھانچے جو اس بات کا یقین کر لیں کہ اس سے نہیں ہوتا ہے. تاہم، ایک عام بات ہے کہ اس سے بچنے کے لئے کیا جا سکتا ہے ہے تصادفی ان پٹ اقدار شفل. یہ بہت زیادہ امکان نہیں ہے کہ بے ترتیب موقع کی طرف سے کی تعداد کے shuffled فہرست کے مطابق ہے. اگر یہ معاملہ کاروبار میں جوئے بازی کے اڈوں رہنا طویل وقت تک نہیں کریں گے. 

وہاں تمہارے پاس ہے. اب آپ بائنری تلاش اور بائنری تلاش کے درخت کے بارے میں جانتے ہیں. میں پیٹرک Schmid ہوں، اور اس CS50 ہے. [CS50.TV] ایک واضح طریقہ سے کی فہرست اسکین ... [بیپ] ... اشیاء کی تعداد ... جی ہاں [ہنسی] ... 234 ... augh نوڈ پوسٹ. >> Yay! تھا -