1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [بائنری تلاش کریں]

2
00:00:02,000 --> 00:00:04,000
[پیٹرک Schmid - ہارورڈ یونیورسٹی]

3
00:00:04,000 --> 00:00:07,000
یہ [CS50 ہے. CS50.TV] -

4
00:00:07,000 --> 00:00:09,000
>> اگر میں آپ کو حروف تہجی کی ترتیب میں دی ڈزنی کے کردار کے ناموں کی ایک فہرست

5
00:00:09,000 --> 00:00:11,000
اور آپ سے کہا کہ مکی ماؤس کو تلاش کرنے کے لئے،

6
00:00:11,000 --> 00:00:13,000
آپ کو ایسا کرنے کے بارے میں کیسے جا سکتا ہے؟

7
00:00:13,000 --> 00:00:15,000
ایک واضح راستہ شروع سے فہرست کو اسکین ہوگا

8
00:00:15,000 --> 00:00:18,000
اور ہر اگر یہ مکی ہے دیکھنے کے نام چیک کرنے کے لیے ہیں.

9
00:00:18,000 --> 00:00:22,000
لیکن، جیسا کہ آپ علاء، یلس، ایریل، پڑھیں اور وغیرہ

10
00:00:22,000 --> 00:00:25,000
آپ کو تیزی سے احساس ہوگا کہ فہرست کے سامنے سے شروع ایک اچھا خیال نہیں تھا.

11
00:00:25,000 --> 00:00:29,000
ٹھیک ہے، ہو سکتا ہے کہ آپ کی فہرست کے آخر سے پیچھے کی طرف کام کرنا شروع کر دینا چاہئے.

12
00:00:29,000 --> 00:00:33,000
اب آپ ٹارجن، سلائی، ہمشوےت، اور وغیرہ پڑھیں.

13
00:00:33,000 --> 00:00:36,000
پھر بھی، یہ اس کے بارے میں جانے کے لئے سب سے بہتر طریقہ کی طرح نہیں لگتا ہے.

14
00:00:36,000 --> 00:00:38,000
>> ٹھیک ہے، ایک اور راستہ ہے جس سے کہ آپ کو ایسا کرنے کے بارے میں جا سکتے ہیں کو محدود کرنے کی کوشش کریں

15
00:00:38,000 --> 00:00:41,000
ان کے ناموں کی فہرست ہے کہ آپ کو دیکھنے کے لئے ہے.

16
00:00:41,000 --> 00:00:43,000
چونکہ تم جانتے ہو کہ وہ حروف تہجی کی ترتیب میں ہیں،

17
00:00:43,000 --> 00:00:45,000
آپ کو فہرست کے وسط میں نام پر ذرا دیکھو سکتا ہے

18
00:00:45,000 --> 00:00:49,000
چیک کرنے کے لیے اور اگر مکی ماؤس سے پہلے یا اس کے بعد اس کا نام یہ ہے.

19
00:00:49,000 --> 00:00:51,000
دوسرے کالم کی تلاش میں آخری نام

20
00:00:51,000 --> 00:00:54,000
تمہیں احساس ہے کہ مکی کے لئے M جیسمین کے لئے J بعد آتا ہے چاہتے ہیں،

21
00:00:54,000 --> 00:00:57,000
تو آپ کو فہرست کی پہلی ششماہی صرف نظر انداز تھا.

22
00:00:57,000 --> 00:00:59,000
اس وقت تم گزشتہ کالم کے سب سے اوپر دیئے گئے شاید لگوگی

23
00:00:59,000 --> 00:01:02,000
دیکھ کر اور یہ کہ اس Rapunzel کے ساتھ شروع ہوتی ہے.

24
00:01:02,000 --> 00:01:06,000
مکی Rapunzel کے سامنے آتا ہے، جیسا کہ ہم گزشتہ کالم کو نظر انداز کے طور پر کر سکتے ہیں لگتا ہے.

25
00:01:06,000 --> 00:01:08,000
تلاش کی حکمت عملی جاری، آپ کو فوری طور پر دیکھیں گے کہ مکی

26
00:01:08,000 --> 00:01:11,000
ناموں کی باقی فہرست کی پہلی ششماہی میں ہے

27
00:01:11,000 --> 00:01:14,000
اور آخر میں تلاش مکی مرلن اور Minnie کے درمیان چھپے.

28
00:01:14,000 --> 00:01:17,000
>> تم نے ابھی کیا کیا وہ بنیادی طور پر بائنری تلاش تھی.

29
00:01:17,000 --> 00:01:22,000
جیسا کہ اس کے نام کا مطلب ہے، یہ ایک بائنری معاملے میں اس کی تلاش کی حکمت عملی انجام دیتا ہے.

30
00:01:22,000 --> 00:01:24,000
اس کا کیا مطلب ہے؟

31
00:01:24,000 --> 00:01:27,000
ٹھیک ہے، کے مطابق اشیاء کی ایک فہرست دی گئی ہے، بائنری تلاش الگورتھم میں ایک بائنری فیصلہ کرتا ہے -

32
00:01:27,000 --> 00:01:33,000
بائیں یا دائیں یا اس سے زیادہ سے کم، انگریزی حروف تہجی کے پہلے یا بعد میں - ہر موڑ پر.

33
00:01:33,000 --> 00:01:35,000
اب جب کہ ہم ایک نام ہے جو اس تلاش کے الگورتھم کے ساتھ ساتھ جاتا ہے ہے،

34
00:01:35,000 --> 00:01:38,000
کی ایک اور مثال کو دیکھو، لیکن کے مطابق تعداد کی ایک فہرست کے ساتھ اس وقت.

35
00:01:38,000 --> 00:01:43,000
کہو کہ ہم کے مطابق تعداد کے اس فہرست میں 144 نمبر کے لئے تلاش کر رہے ہیں.

36
00:01:43,000 --> 00:01:46,000
بس پہلے کی طرح، ہم نمبر ہے کہ درمیان میں ہے تلاش کریں -

37
00:01:46,000 --> 00:01:50,000
جو اس کیس میں 13 ہے - اور اگر 144 یا اس سے زیادہ 13 سے کم ہے دیکھ.

38
00:01:50,000 --> 00:01:54,000
چونکہ یہ واضح طور پر 13 سے زیادہ ہے، ہم سب کچھ نظر انداز کر سکتے ہیں جو 13 یا اس سے کم ہے

39
00:01:54,000 --> 00:01:57,000
اور باقی نصف پر توجہ.

40
00:01:57,000 --> 00:01:59,000
چونکہ اب ہم اشیاء کی بھی تعداد کو چھوڑ دیا ہے،

41
00:01:59,000 --> 00:02:01,000
ہم صرف ایک بڑی تعداد ہے جو مشرق قریب ہے کو منتخب کریں.

42
00:02:01,000 --> 00:02:03,000
اس صورت میں ہم 55 کا انتخاب کرتے ہیں.

43
00:02:03,000 --> 00:02:06,000
ہم بالکل اسی طرح جیسے آسانی سے 89 کا انتخاب کیا جا سکتا ہے.

44
00:02:06,000 --> 00:02:11,000
ٹھیک ہے. ایک بار پھر، 144 55 سے بڑا ہے، تو ہم حق پر ہیں.

45
00:02:11,000 --> 00:02:14,000
خوش قسمتی سے ہمارے لئے، اگلے مشرق کی تعداد 144 ہے،

46
00:02:14,000 --> 00:02:16,000
جس سے ہم کے لئے تلاش کر رہے ہیں.

47
00:02:16,000 --> 00:02:21,000
لہذا اس میں حکم 144 ایک بائنری تلاش کا استعمال کرتے ہوئے تلاش کرنے کے لئے، ہم اسے صرف 3 اقدامات میں تلاش کرنے کے قابل ہو.

48
00:02:21,000 --> 00:02:24,000
اگر ہم لکیری تلاش یہاں استعمال کیا جاتا ہے، یہ ہمیں 12 اقدامات کریں گے لیا ہے.

49
00:02:24,000 --> 00:02:28,000
حقیقت تو یہ ہے کے طور پر، کے بعد سے اس تلاش کے طریقہ کار اشیاء کی تعداد حصوں

50
00:02:28,000 --> 00:02:31,000
اس کے ہر قدم پر کو دیکھنے کے لئے ہے، یہ آئٹم مل جائے گا اس کے لئے تلاش کر رہا ہے

51
00:02:31,000 --> 00:02:35,000
میں فہرست میں اشیاء کی تعداد کے لاگ ان کے بارے میں.

52
00:02:35,000 --> 00:02:37,000
اب کہ ہم نے 2 مثال کے طور پر دیکھا ہے، پر ایک نظر ڈالیں

53
00:02:37,000 --> 00:02:41,000
ایک پنراورتی تقریب ہے جو بائنری تلاش نافذ کے لئے کچھ pseudocode.

54
00:02:41,000 --> 00:02:44,000
سب سے اوپر شروع ہو رہا ہے، ہم دیکھتے ہیں کہ ہم نے ایک تقریب ہے جو 4 دلائل لیتا ہے تلاش کرنے کے لئے ہے:

55
00:02:44,000 --> 00:02:47,000
کلید، صف، کم از کم، اور زیادہ سے زیادہ.

56
00:02:47,000 --> 00:02:51,000
کلید نمبر پر ہے کہ ہم نے کے لئے، گزشتہ مثال میں 144 تلاش کر رہے ہیں ہے.

57
00:02:51,000 --> 00:02:54,000
صف نمبروں کی فہرست ہے کہ ہم تلاش کر رہے ہیں ہے.

58
00:02:54,000 --> 00:02:57,000
کم از کم اور زیادہ سے زیادہ کم از کم اور زیادہ سے زیادہ پوزیشن کے سوچکانکوں ہیں

59
00:02:57,000 --> 00:02:59,000
کہ ہم فی الحال کر رہے ہیں.

60
00:02:59,000 --> 00:03:03,000
تو جب ہم شروع منٹ صفر ہو جائے گا اور زیادہ سے زیادہ صف کی زیادہ سے زیادہ فہرست ہو جائے گا.

61
00:03:03,000 --> 00:03:07,000
جب ہم تلاش نیچے محدود، ہم کم از کم اور زیادہ سے زیادہ اپ ڈیٹ ہو جائے گا

62
00:03:07,000 --> 00:03:10,000
صرف رینج کہ ہم ابھی بھی اندر تلاش کر رہے ہیں.

63
00:03:10,000 --> 00:03:12,000
>> دلچسپ حصہ میں سب سے پہلے پر دو

64
00:03:12,000 --> 00:03:14,000
پہلی بات ہم کرتے ہیں midpoint تلاش،

65
00:03:14,000 --> 00:03:19,000
انڈیکس نصف صف کہ ہم اب بھی غور کر رہے ہیں کم از کم اور زیادہ سے زیادہ کے درمیان ہے.

66
00:03:19,000 --> 00:03:22,000
اس کے بعد ہم صف کی قدر میں اس midpoint مقام پر نظر

67
00:03:22,000 --> 00:03:25,000
دیکھتے ہیں اور اگر نمبر پر ہے کہ ہم تلاش کر رہے ہیں اس چابی سے بھی کم ہے.

68
00:03:25,000 --> 00:03:27,000
اگر اس پوزیشن میں تعداد کم ہے،

69
00:03:27,000 --> 00:03:31,000
تو اس کا مطلب ہے کہ چابی اس کی حیثیت کو بائیں تمام نمبر سے بڑا ہے.

70
00:03:31,000 --> 00:03:33,000
تو ہم بائنری سرچ فنکشن کو پھر سے فون کر سکتے ہیں،

71
00:03:33,000 --> 00:03:36,000
لیکن اس وقت کم از کم اور زیادہ سے زیادہ پیرامیٹرز کو اپ ڈیٹ کر صرف آدھے پڑھ

72
00:03:36,000 --> 00:03:40,000
یا اس سے زیادہ قیمت ہم صرف کی طرف دیکھ رہے تھے کے برابر ہے.

73
00:03:40,000 --> 00:03:44,000
دوسری طرف، اگر چابی صف کی موجودہ midpoint تعداد سے کم ہے،

74
00:03:44,000 --> 00:03:47,000
ہم بائیں طرف جانے کے لئے اور تمام نمبر زیادہ ہیں کو نظر انداز کرنا چاہتے ہیں.

75
00:03:47,000 --> 00:03:52,000
ایک بار پھر، ہم کم از کم اور زیادہ سے زیادہ تازہ کاری کی حد کے ساتھ بائنری تلاش ہے لیکن اس بار فون

76
00:03:52,000 --> 00:03:54,000
صرف کم نصف شامل کرنے کے لئے.

77
00:03:54,000 --> 00:03:57,000
اگر صف میں موجودہ midpoint قدر ہے نہ

78
00:03:57,000 --> 00:04:01,000
سے بڑا اور نہ ہی چابی سے چھوٹا ہے، تو یہ چابی کے برابر ہونا چاہیے.

79
00:04:01,000 --> 00:04:05,000
اس طرح، ہم موجودہ midpoint انڈیکس صرف، واپس اور ہم کیا کر رہے ہیں کر سکتے ہیں.

80
00:04:05,000 --> 00:04:09,000
آخر میں، یہ یہاں چیک کیس کے لئے یہ ہے کہ تعداد

81
00:04:09,000 --> 00:04:11,000
اصل تعداد ہم تلاش کر رہے ہیں کی صف میں نہیں ہے.

82
00:04:11,000 --> 00:04:14,000
اگر حد سے زیادہ سے زیادہ انڈیکس ہے کہ ہم تلاش کر رہے ہیں

83
00:04:14,000 --> 00:04:17,000
کبھی بھی کم از کم سے کم ہے، کا مطلب ہے کہ ہم بہت دور چلی گئی ہے.

84
00:04:17,000 --> 00:04:20,000
چونکہ نمبر ان پٹ صف میں نہیں تھا، ہم -1 واپس

85
00:04:20,000 --> 00:04:24,000
کہ کچھ نہیں پر دلالت پایا گیا تھا.

86
00:04:24,000 --> 00:04:26,000
>> تم نے کہ یہ الگورتھم کے لئے کام کرنے کے لئے محسوس کیا ہو سکتا ہے،

87
00:04:26,000 --> 00:04:28,000
نمبروں کی فہرست کے مطابق ہے.

88
00:04:28,000 --> 00:04:31,000
دوسرے الفاظ میں، ہم نے 144 صرف بائنری تلاش کا استعمال کرتے ہوئے تلاش کر سکتے ہیں

89
00:04:31,000 --> 00:04:34,000
اگر تمام کی تعداد سب سے زیادہ سے سب سے کم کرنے کا حکم دیا ہے.

90
00:04:34,000 --> 00:04:38,000
اگر یہ معاملہ نہیں تھے، ہم نے ہر قدم پر کی تعداد کے نصف پر خارج کرنے کے قابل نہیں ہو گا.

91
00:04:38,000 --> 00:04:40,000
تو ہم 2 اختیارات ہیں.

92
00:04:40,000 --> 00:04:43,000
یا تو ہم نے ایک ناچھانٹا ہوا کی فہرست لے لو اور بائنری تلاش کا استعمال کرتے ہوئے کرنے سے پہلے یہ ترتیب کر سکتے ہیں،

93
00:04:43,000 --> 00:04:48,000
یا ہم اس بات کا یقین کر لیں کہ کہ نمبروں کی فہرست کے طور پر ہم اس تعداد کو شامل کے مطابق ہے کر سکتے ہیں.

94
00:04:48,000 --> 00:04:50,000
اس طرح، جب ہم تلاش ہے حل کرنے کے بجائے،

95
00:04:50,000 --> 00:04:53,000
ہر وقت کے مطابق فہرست کو برقرار رکھنے کیوں نہیں؟

96
00:04:53,000 --> 00:04:57,000
>> کرتے ہوئے ایک اعداد کی ایک فہرست کو برقرار رکھنے کا ایک طریقہ کے مطابق بیک وقت کی اجازت دی

97
00:04:57,000 --> 00:04:59,000
ایک یا ایک سے منتقل کی تعداد کو اس فہرست سے شامل

98
00:04:59,000 --> 00:05:02,000
ملاقات کی ایک بائنری تلاش درخت کچھ کا استعمال کرتے ہوئے کی طرف سے ہے.

99
00:05:02,000 --> 00:05:05,000
ایک بائنری تلاش درخت ایک آنکڑا ڈھانچہ ہے کہ 3 خصوصیات ہے ہے.

100
00:05:05,000 --> 00:05:09,000
سب سے پہلے، کسی نوڈ کے بائیں subtree اس سے بھی کم ہیں صرف اقدار پر مشتمل ہے

101
00:05:09,000 --> 00:05:11,000
نوڈ قیمت کے برابر یا اس.

102
00:05:11,000 --> 00:05:15,000
دوسرا، ایک نوڈ کا حق ہے subtree صرف اقدار کو اس سے بھی زیادہ ہیں پر مشتمل ہے

103
00:05:15,000 --> 00:05:17,000
نوڈ قیمت کے برابر یا اس.

104
00:05:17,000 --> 00:05:20,000
اور، آخر میں، تمام مراکز کی دونوں بائیں اور دائیں subtrees

105
00:05:20,000 --> 00:05:23,000
بھی بائنری تلاش کے پیڑ ہیں.

106
00:05:23,000 --> 00:05:26,000
چلو ہم پہلے کرتے تھے اسی تعداد کے ساتھ ایک مثال کو دیکھو.

107
00:05:26,000 --> 00:05:30,000
، تم میں سے ان لوگوں کو جو دیکھا کمپیوٹر سائنس کے درخت سے پہلے کبھی نہیں کے لئے

108
00:05:30,000 --> 00:05:34,000
کے وزٹرز کا ریکارڈ رکھا جائے گا. میرے تم سے کہہ رہی ہے کہ کمپیوٹر سائنس کے درخت کے نیچے اگنے کی طرف سے شروع.

109
00:05:34,000 --> 00:05:36,000
جی ہاں،، درخت آپ عادی رہے ہیں کے برعکس

110
00:05:36,000 --> 00:05:38,000
کمپیوٹر سائنس کے درخت کی جڑ سب سے اوپر ہے،

111
00:05:38,000 --> 00:05:41,000
اور پتیوں کے نیچے دیے گئے ہیں.

112
00:05:41,000 --> 00:05:45,000
ہر چھوٹا خانہ ایک نوڈ کہا جاتا ہے، اور نوڈس کناروں کی طرف سے ایک دوسرے سے جڑے ہوئے ہیں.

113
00:05:45,000 --> 00:05:48,000
تو اس درخت کی جڑ میں 13 کی قیمت کے ساتھ ایک نوڈ قیمت ہے،

114
00:05:48,000 --> 00:05:52,000
جو 2 اقدار 5 اور 34 کے ساتھ بچوں نوڈس ہے.

115
00:05:52,000 --> 00:05:57,000
A subtree درخت ہے جو صرف پورے درخت کی subsection میں دیکھ کر تشکیل میں حصہ لیا ہے.

116
00:05:57,000 --> 00:06:03,000
>> مثال کے طور پر، نوڈ 3 0 نوڈس، 1، اور 2 کی طرف سے پیدا بائیں subtree درخت ہے.

117
00:06:03,000 --> 00:06:06,000
تو، اگر ہم ایک بائنری تلاش کے درخت کی خصوصیات میں واپس جانا

118
00:06:06,000 --> 00:06:09,000
ہم دیکھتے ہیں کہ درخت میں ہر نوڈ تمام 3 خصوصیات، یعنی conforms

119
00:06:09,000 --> 00:06:15,000
صرف بائیں subtree اقدار سے کم نوڈ قیمت کے برابر یا اس پر مشتمل ہے؛

120
00:06:15,000 --> 00:06:16,000
تمام مراکز کی subtree

121
00:06:16,000 --> 00:06:19,000
صرف اقدار اس سے بڑا یا نوڈ قیمت کے برابر ہیں پر مشتمل ہے، اور

122
00:06:19,000 --> 00:06:25,000
تمام مراکز کی بائیں اور دائیں دونوں subtrees بھی بائنری تلاش کے درخت ہیں.

123
00:06:25,000 --> 00:06:28,000
اگرچہ یہ درخت مختلف لگ رہا ہے، یہ ایک درست بائنری تلاش درخت ہے

124
00:06:28,000 --> 00:06:30,000
کی تعداد کے ایک ہی سیٹ کے لئے.

125
00:06:30,000 --> 00:06:32,000
حقیقت تو یہ ہے کے طور پر، بہت ممکن ہے کہ تشکیل دے سکتے ہیں ہیں

126
00:06:32,000 --> 00:06:35,000
ان کی تعداد کی طرف سے ایک درست بائنری تلاش درخت.

127
00:06:35,000 --> 00:06:38,000
چلو، سب سے پہلے ہمیں پیدا کیا واپس جانا ہے.

128
00:06:38,000 --> 00:06:40,000
تو کیا ہم ان درختوں کے ساتھ کیا کر سکتے ہیں؟

129
00:06:40,000 --> 00:06:44,000
ٹھیک ہے، ہم کم از کم اور زیادہ سے زیادہ اقدار بہت آسانی سے حاصل کر سکتے ہیں.

130
00:06:44,000 --> 00:06:46,000
کم از کم اقدار ہمیشہ بائیں طرف جا کر پایا جا سکتا ہے

131
00:06:46,000 --> 00:06:48,000
تک نہیں مراکز کا دورہ کر رہے ہیں.

132
00:06:48,000 --> 00:06:53,000
کے برعکس، زیادہ سے زیادہ ایک کو تلاش کرنے کے لئے صرف صرف ہر وقت حق نیچے جاتا ہے.

133
00:06:54,000 --> 00:06:56,000
>> کسی دوسرے نمبر کی تلاش ہے کہ کم از کم یا زیادہ سے زیادہ نہیں ہے

134
00:06:56,000 --> 00:06:58,000
کے طور پر آسان ہے.

135
00:06:58,000 --> 00:07:00,000
کا کہنا ہے کہ ہم نے 89 نمبر کے لئے تلاش کر رہے ہیں.

136
00:07:00,000 --> 00:07:03,000
ہم صرف ہر نوڈ کی قدر کی جانچ پڑتال کریں اور بائیں یا دائیں،

137
00:07:03,000 --> 00:07:06,000
پر منحصر ہے کیا نوڈ کی قیمت سے کم یا اس سے بڑا ہے

138
00:07:06,000 --> 00:07:08,000
جس سے ہم کے لئے تلاش کر رہے ہیں.

139
00:07:08,000 --> 00:07:11,000
لہذا، ہم نے 13 کی جڑ میں شروع ہونے والے دیکھ سکتے ہیں کہ 89 بڑی اور عظیم چیز ہے،

140
00:07:11,000 --> 00:07:13,000
اور ہم کو درست کرنے میں جانا.

141
00:07:13,000 --> 00:07:16,000
پھر ہم 34 کے لئے نوڈ کو دیکھنے، اور پھر ہم حق پر ہیں.

142
00:07:16,000 --> 00:07:20,000
89 اب بھی 55 سے بڑھ کر ہے، لہذا ہم حق پر جا رہیں.

143
00:07:20,000 --> 00:07:24,000
پھر ہم 144 کی قدر کے ساتھ ایک نوڈ کے ساتھ آئے گا اور بائیں.

144
00:07:24,000 --> 00:07:26,000
دیکھو اور دیکھو، 89 وہیں ہے.

145
00:07:26,000 --> 00:07:31,000
>> ایک دوسری بات یہ ہے کہ ہم کیا کر سکتے ہیں ہے ایک inorder traversal کارکردگی کا مظاہرہ کر کے تمام نمبرز پرنٹ کریں.

146
00:07:31,000 --> 00:07:35,000
ایک inorder traversal سب کچھ بائیں subtree میں پرنٹ کا مطلب ہے

147
00:07:35,000 --> 00:07:37,000
نوڈ خود چھپائی کے بعد

148
00:07:37,000 --> 00:07:40,000
اور پھر بعد سب کچھ درست subtree میں چھپائی سے ہٹ کر ہے.

149
00:07:40,000 --> 00:07:43,000
مثال کے طور پر، ہمارے پسندیدہ بائنری تلاش درخت

150
00:07:43,000 --> 00:07:46,000
اور باہر کے مطابق ترتیب میں تعداد کو پرنٹ کریں.

151
00:07:46,000 --> 00:07:49,000
ہم نے 13 کی جڑ میں شروع، لیکن 13 پرنٹنگ سے پہلے ہم باہر پرنٹ کرنے کے لئے ہے

152
00:07:49,000 --> 00:07:51,000
بائیں subtree میں سب کچھ ہے.

153
00:07:51,000 --> 00:07:55,000
تو ہم 5. ہم اب بھی درخت میں گہری نیچے جانا ہوگا جب تک کہ ہم نوڈ بائیں سب سے زیادہ ملے ہیں،

154
00:07:55,000 --> 00:07:57,000
جو صفر ہے.

155
00:07:57,000 --> 00:08:00,000
صفر پرنٹنگ کے بعد، ہم نے 1 واپس جاؤ اور باہر کہ پرنٹ.

156
00:08:00,000 --> 00:08:03,000
پھر ہم صحیح subtree، جو 2 ہے، اور کہ پرنٹ.

157
00:08:03,000 --> 00:08:05,000
اب جب کہ ہم نے کہ subtree کے ساتھ کیا کیا ہے،

158
00:08:05,000 --> 00:08:07,000
ہم واپس جا 3 اور اسے باہر پرنٹ کر سکتے ہیں.

159
00:08:07,000 --> 00:08:11,000
بیک اپ جاری، ہم 5 پرنٹ اور پھر 8.

160
00:08:11,000 --> 00:08:13,000
اب جب کہ ہم پورے مکمل کر لیا ہے subtree چھوڑ دیا،

161
00:08:13,000 --> 00:08:17,000
ہم 13 پرنٹ اور درست subtree پر کام کر شروع کر سکتے ہیں.

162
00:08:17,000 --> 00:08:21,000
ہم 34 ہاپ، لیکن 34 پرنٹنگ اس سے پہلے کہ ہم اس کے بائیں subtree پرنٹ ہے.

163
00:08:21,000 --> 00:08:27,000
تو ہم باہر 21 پرنٹ کریں، پھر ہم باہر 34 پرنٹ اور اس کے حق subtree کا دورہ کریں.

164
00:08:27,000 --> 00:08:31,000
چونکہ 55 نہیں بائیں subtree ہے، ہم اسے باہر پرنٹ اور اس کے صحیح subtree جاری ہے.

165
00:08:31,000 --> 00:08:36,000
144 بائیں subtree ہے، اور ہم باہر 89 پرنٹ، اس کے بعد 144،

166
00:08:36,000 --> 00:08:39,000
اور 233 کے آخر میں دائیں سب سے زیادہ نوڈ.

167
00:08:39,000 --> 00:08:44,000
وہاں تمہارے پاس ہے، تمام اعداد و شمار سے کم از کم سب سے زیادہ کے لئے میں طباعت ہیں.

168
00:08:44,000 --> 00:08:47,000
>> درخت سے کچھ کو شامل کرنے کے ساتھ ساتھ نسبتا پیڑارہت ہے.

169
00:08:47,000 --> 00:08:51,000
ہمیں کیا کرنا ہے اس بات کا یقین کر لیں کہ ہم 3 بائنری تلاش کے درخت کی خصوصیات پر عمل بنانے کے ہے

170
00:08:51,000 --> 00:08:53,000
اور پھر قدر داخل جہاں جگہ ہے.

171
00:08:53,000 --> 00:08:55,000
چلو کا کہنا ہے کہ ہم 7 کی قیمت کو شامل کرنے کے لئے چاہتے ہیں.

172
00:08:55,000 --> 00:08:58,000
چونکہ 7 سے کم 13 ہے، ہم بائیں طرف جانا.

173
00:08:58,000 --> 00:09:01,000
لیکن یہ 5 سے زیادہ ہے، اس لئے ہم حق گزرنا.

174
00:09:01,000 --> 00:09:04,000
چونکہ یہ سے کم 8 اور 8 پتی کی نوڈ ہے، ہم 8 کے بائیں بچے کو 7 شامل کریں.

175
00:09:04,000 --> 00:09:09,000
Voila! ہم ہمارے بائنری تلاش کے درخت میں ایک نمبر کا اضافہ کیا ہے.

176
00:09:09,000 --> 00:09:12,000
>> اگر ہم چیزیں شامل کر سکتے ہیں، ہم بہتر چیزوں کے طور پر حذف کرنے کے قابل ہو جائے.

177
00:09:12,000 --> 00:09:14,000
بد قسمتی سے ہمارے لئے، حذف کرنے سے تھوڑا سا زیادہ پیچیدہ ہے -

178
00:09:14,000 --> 00:09:16,000
زیادہ نہیں، لیکن صرف تھوڑا سا.

179
00:09:16,000 --> 00:09:18,000
3 مختلف منظرناموں ہے کہ ہم اس پر غور کرنا ہوگا

180
00:09:18,000 --> 00:09:21,000
بائنری تلاش کے پیڑ سے عناصر جب حذف کرنے.

181
00:09:21,000 --> 00:09:24,000
سب سے پہلے، سب سے آسان معاملہ ہے کہ عنصر پتی کی نوڈ ہے.

182
00:09:24,000 --> 00:09:27,000
اس صورت میں، ہم صرف اس کو خارج کر دیں اور ہمارے کاروبار کے ساتھ جاؤ.

183
00:09:27,000 --> 00:09:30,000
کہو کہ ہم 7 کہ ہم صرف شامل کو حذف کرنا چاہتے ہیں.

184
00:09:30,000 --> 00:09:34,000
ٹھیک ہے، ہم صرف اس تلاش کو ہٹانے کے، اور یہ کہ یہ ہے.

185
00:09:35,000 --> 00:09:37,000
اگلے معاملہ ہے اگر نوڈ صرف 1 بچہ ہے.

186
00:09:37,000 --> 00:09:40,000
ہم یہاں نوڈ کو حذف، لیکن ہم سب سے پہلے اس بات کا یقین کرنے کے لئے ہے کر سکتے ہیں

187
00:09:40,000 --> 00:09:42,000
کو subtree کہ اب parentless رہ گیا ہے مربوط کرنے کے لئے

188
00:09:42,000 --> 00:09:44,000
نوڈ کے والدین پر ہم صرف خارج کر دیا ہے.

189
00:09:44,000 --> 00:09:47,000
کہو کہ ہم ہمارے درخت سے 3 کو حذف کرنا چاہتے ہیں.

190
00:09:47,000 --> 00:09:50,000
ہم اس نوڈ کے بچے عنصر اور نوڈ کے والدین پر منسلک ہیں.

191
00:09:50,000 --> 00:09:54,000
اس صورت میں، ہم نے اب 5 1 رہے ہیں منسلک.

192
00:09:54,000 --> 00:09:57,000
یہ ایک مسئلہ کے بغیر کام کرتا ہے کیونکہ ہم جانتے ہیں بائنری تلاش کے درخت جائیداد کے مطابق،

193
00:09:57,000 --> 00:10:01,000
3 کے بائیں subtree میں ہے کہ ہر چیز سے بھی کم 5 تھا.

194
00:10:01,000 --> 00:10:05,000
اب جب کہ 3 subtree خیال رکھا ہے، ہم اسے خارج کر سکتے ہیں.

195
00:10:05,000 --> 00:10:08,000
تیسرے اور آخری کیس کے سب سے زیادہ پیچیدہ ہے.

196
00:10:08,000 --> 00:10:11,000
یہ اس وقت ہے جب نوڈ ہم کو خارج کرنا چاہتے ہیں 2 بچے ہیں.

197
00:10:11,000 --> 00:10:15,000
کے لئے ایسا کرنے کے لئے، ہم سب سے پہلے نوڈ کہ اگلے سب سے بڑی قیمت ہے تلاش کرنے کے لئے ہے،

198
00:10:15,000 --> 00:10:18,000
دو تبادلہ کریں، اور تو سوال میں نوڈ کو حذف کریں.

199
00:10:18,000 --> 00:10:22,000
نوڈ ہے جو اگلے سب سے بڑی قیمت 2 بچے ہیں نہیں خود کر سکتے ہیں نوٹس

200
00:10:22,000 --> 00:10:26,000
کے بعد سے اس کے بائیں بچے اگلے سب سے بڑی کے لئے ایک بہتر امیدوار ہو جائے گی.

201
00:10:26,000 --> 00:10:30,000
لہذا، 2 بچوں کے ساتھ نوڈ حذف کرنے 2 مراکز کی گماگمن کرنے کے مترادف ہے،

202
00:10:30,000 --> 00:10:33,000
اور پھر حذف کرنے سے 1 2 مذکورہ بالا قوانین کے سنبھالا ہے.

203
00:10:33,000 --> 00:10:37,000
مثال کے طور پر، دو کا کہنا ہے کہ ہمیں جڑ نوڈ، 13 کو حذف کرنا چاہتے ہیں.

204
00:10:37,000 --> 00:10:39,000
پہلی بات ہم کرتے ہیں ہم نے درخت میں اگلے سب سے بڑی قیمت معلوم

205
00:10:39,000 --> 00:10:41,000
جو، اس معاملے میں، 21 ہے.

206
00:10:41,000 --> 00:10:46,000
ہم تو 2 نوڈس تبادلہ، 13 پتی اور 21 مرکزی گروپ نوڈ بنانے کے.

207
00:10:46,000 --> 00:10:49,000
اب ہم 13 صرف اسے خارج کر سکتے ہیں.

208
00:10:50,000 --> 00:10:53,000
>> پہلے alluded، بہت ممکن ہے ایک درست بائنری تلاش کے درخت بنانے کے لئے طریقے ہیں.

209
00:10:53,000 --> 00:10:56,000
بدقسمتی سے ہمارے لئے، کچھ دوسروں سے بھی بدتر ہیں.

210
00:10:56,000 --> 00:10:59,000
مثال کے طور پر، کیا ہوتا ہے جب ہم ایک بائنری تلاش درخت تعمیر

211
00:10:59,000 --> 00:11:01,000
کی تعداد کے مطابق فہرست سے؟

212
00:11:01,000 --> 00:11:04,000
تمام اعداد و شمار صرف ہر قدم پر حق شامل ہیں.

213
00:11:04,000 --> 00:11:06,000
جب ہم ایک نمبر کے لئے تلاش کرنا چاہتے ہیں،

214
00:11:06,000 --> 00:11:08,000
ہمارے پاس اور کوئی چارہ نہیں ہے، لیکن صرف ہر قدم پر حق کو دیکھنے کے لئے.

215
00:11:08,000 --> 00:11:11,000
یہ بالکل لکیری تلاش سے بہتر نہیں ہے.

216
00:11:11,000 --> 00:11:13,000
اگرچہ ہم نے انہیں یہاں کا احاطہ نہیں کیا جائے گا، اس کے علاوہ، زیادہ پیچیدہ ہوتے ہیں،

217
00:11:13,000 --> 00:11:16,000
ڈیٹا ڈھانچے جو اس بات کا یقین کر لیں کہ اس سے نہیں ہوتا ہے.

218
00:11:16,000 --> 00:11:18,000
تاہم، ایک عام بات ہے کہ اس سے بچنے کے لئے کیا جا سکتا ہے ہے

219
00:11:18,000 --> 00:11:21,000
تصادفی ان پٹ اقدار شفل.

220
00:11:21,000 --> 00:11:26,000
یہ بہت زیادہ امکان نہیں ہے کہ بے ترتیب موقع کی طرف سے کی تعداد کے shuffled فہرست کے مطابق ہے.

221
00:11:26,000 --> 00:11:29,000
اگر یہ معاملہ کاروبار میں جوئے بازی کے اڈوں رہنا طویل وقت تک نہیں کریں گے.

222
00:11:29,000 --> 00:11:31,000
>> وہاں تمہارے پاس ہے.

223
00:11:31,000 --> 00:11:34,000
اب آپ بائنری تلاش اور بائنری تلاش کے درخت کے بارے میں جانتے ہیں.

224
00:11:34,000 --> 00:11:36,000
میں پیٹرک Schmid ہوں، اور اس CS50 ہے.

225
00:11:36,000 --> 00:11:38,000
[CS50.TV]

226
00:11:38,000 --> 00:11:43,000
ایک واضح طریقہ سے کی فہرست اسکین ... [بیپ]

227
00:11:43,000 --> 00:11:46,000
... اشیاء کی تعداد ... جی ہاں

228
00:11:46,000 --> 00:11:50,000
[ہنسی]

229
00:11:50,000 --> 00:11:55,000
... 234 ... augh نوڈ پوسٹ.

230
00:11:55,000 --> 00:11:58,000
>> Yay! تھا -