1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [بحث ثنائي]

2
00:00:02,000 --> 00:00:04,000
[باتريك شميد - جامعة هارفارد]

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
ونرى أنه يبدأ رابونزيل.

24
00:01:02,000 --> 00:01:06,000
ميكي يأتي قبل رابونزيل، يبدو أننا يمكن تجاهل العمود الأخير أيضا.

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
وأخيرا وجدت ميكي يختبئ بين ميرلين وميني.

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
بعض شبة الكود لوظيفة العودية التي تطبق بحث ثنائية.

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
Min و Max هي مؤشرات لمواقف الحد الأدنى والحد الأقصى

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
ونحن تضييق نطاق البحث إلى أسفل، وسوف نقوم بتحديث Min و Max

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
أول شيء نقوم به هو العثور على نقطة الوسط،

65
00:03:14,000 --> 00:03:19,000
الفهرس الذي هو في منتصف الطريق بين الحد الأدنى والحد الأقصى للمجموعة التي مازلنا ندرس.

66
00:03:19,000 --> 00:03:22,000
ثم ننظر إلى قيمة من الصفيف في ذلك الموقع منتصف

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
من ناحية أخرى، إذا كان المفتاح هو أقل من عدد في منتصف الحالية للمجموعة،

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
إذا كانت القيمة في منتصف الحالية في مجموعة ليست

78
00:03:57,000 --> 00:04:01,000
أكبر من أو أصغر من المفتاح، ثم يجب أن يكون مساويا لمفتاح.

79
00:04:01,000 --> 00:04:05,000
وهكذا، يمكن أن نعود ببساطة مؤشر منتصف الحالي، وننتهي.

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
أولا، الشجرة الفرعية الأيسر من أي عقدة فقط يحتوي على قيم التي هي أقل من

101
00:05:09,000 --> 00:05:11,000
أو تساوي القيمة للعقدة.

102
00:05:11,000 --> 00:05:15,000
الثانية، الشجرة الفرعية حق عقدة يحتوي فقط على القيم التي هي أكبر من

103
00:05:15,000 --> 00:05:17,000
أو تساوي القيمة للعقدة.

104
00:05:17,000 --> 00:05:20,000
وأخيرا، فإن كلا من الأشجار الفرعية الأيسر والأيمن من كافة العقد

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
شجرة فرعية هي الشجرة التي تتكون فقط من خلال النظر في القسم الفرعي من شجرة بأكملها.

116
00:05:57,000 --> 00:06:03,000
>> على سبيل المثال، الشجرة الفرعية اليسرى من 3 عقدة الشجرة التي أنشأتها العقد 0، 1، و 2.

117
00:06:03,000 --> 00:06:06,000
لذا، إذا رجعنا إلى خصائص ثنائي شجرة البحث،

118
00:06:06,000 --> 00:06:09,000
ونحن نرى أن كل عقدة في شجرة يتوافق مع كافة الخصائص 3، أي،

119
00:06:09,000 --> 00:06:15,000
الشجرة الفرعية اليسار يحتوي فقط على القيم التي هي أقل من أو يساوي قيمة عقدة؛

120
00:06:15,000 --> 00:06:16,000
الشجرة الفرعية حق كافة العقد

121
00:06:16,000 --> 00:06:19,000
يحتوي فقط على القيم التي هي أكبر من أو يساوي قيمة للعقدة، و

122
00:06:19,000 --> 00:06:25,000
الأشجار الفرعية كل من اليسار واليمين من كافة العقد أيضا أشجار البحث الثنائية.

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
>> شيء آخر يمكن أن نفعله هو طباعة جميع الأرقام عن طريق إجراء اجتياز اتباعها.

146
00:07:31,000 --> 00:07:35,000
ويعني اجتياز اتباعها لطباعة كل شيء في الشجرة الفرعية اليسار

147
00:07:35,000 --> 00:07:37,000
تليها طباعة العقدة نفسها

148
00:07:37,000 --> 00:07:40,000
ثم يتبع ذلك الطباعة في الشجرة الفرعية كل شيء حق.

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
كل شيء في الشجرة الفرعية اليسار.

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
ثم نذهب إلى الشجرة الفرعية الحق، الذي هو 2، وطباعة إلى ذلك.

157
00:08:03,000 --> 00:08:05,000
والآن بعد أن ننتهي مع أن الشجرة الفرعية،

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
غادر الآن أننا قد أكملت كامل الشجرة الفرعية،

161
00:08:13,000 --> 00:08:17,000
يمكننا طباعة ال 13 وبدء العمل على الشجرة الفرعية حق.

162
00:08:17,000 --> 00:08:21,000
نحن هوب وصولا الى 34، ولكن قبل الطباعة لدينا 34 لطباعة الشجرة الفرعية اليسرى.

163
00:08:21,000 --> 00:08:27,000
لذلك نحن طباعة 21؛ ثم نصل إلى طباعة 34 وزيارته الشجرة الفرعية الصحيح.

164
00:08:27,000 --> 00:08:31,000
منذ 55 ليس لديه الشجرة الفرعية اليسرى، ونحن طباعته وتستمر على الشجرة الفرعية لحقها.

165
00:08:31,000 --> 00:08:36,000
144 لديه الشجرة الفرعية اليسار، ولذا فإننا طباعة ال 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 هو عقدة طرفية، نضيف 7 إلى الطفل الأيسر من 8.

175
00:09:04,000 --> 00:09:09,000
فويلا! لقد أضفنا عددا لدينا ثنائي شجرة البحث.

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
للاتصال الشجرة الفرعية ما تبقى الآن بلا أب

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
في هذه الحالة، نحن الآن إرفاق 1 إلى 5.

192
00:09:54,000 --> 00:09:57,000
هذا يعمل دون مشكلة لأننا نعرف، وفقا لشجرة الملكية ثنائي البحث،

193
00:09:57,000 --> 00:10:01,000
هي أن كل شيء في الشجرة الفرعية اليسرى من 3 أقل من 5.

194
00:10:01,000 --> 00:10:05,000
والآن بعد أن أخذ في 3 الشجرة الفرعية رعاية، يمكننا حذفه.

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
>> ألمح في وقت سابق إلى و، وهناك العديد من السبل الممكنة لجعل البحث الثنائية صالحة شجرة.

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
انه من غير المحتمل إلى حد كبير أن طريق الصدفة العشوائية يتم فرز قائمة تعديلا من الأرقام.

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
أنا باتريك شميد، وهذا هو 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
أضف ... عقدة augh ... 234.

230
00:11:55,000 --> 00:11:58,000
ياي >>! كان ذلك -