1
00:00:00,000 --> 00:00:02,994
>> [عزف الموسيقى]

2
00:00:02,994 --> 00:00:05,426

3
00:00:05,426 --> 00:00:08,550
DOUG لويد: هكذا كنا يقترب
وأقرب أن الكأس المقدسة البيانات

4
00:00:08,550 --> 00:00:13,050
الهياكل، واحدة أن نتمكن من إدراج
إلى، حذف منها، والبحث عن

5
00:00:13,050 --> 00:00:15,440
في وقت ثابت.

6
00:00:15,440 --> 00:00:16,270
الصحيح.

7
00:00:16,270 --> 00:00:17,280
هذا النوع من المرمى.

8
00:00:17,280 --> 00:00:19,720
نحن نريد أن تكون قادرة على القيام
الأشياء بسرعة شديدة جدا.

9
00:00:19,720 --> 00:00:22,580
>> هل لديك وجدنا أنه عندما هنا
نحن نتحدث عن محاولات؟

10
00:00:22,580 --> 00:00:23,670
حسنا، دعونا نلقي نظرة.

11
00:00:23,670 --> 00:00:25,628
لذلك رأينا العديد من
هياكل بيانات مختلفة

12
00:00:25,628 --> 00:00:28,680
التي تتعامل مع رسم خرائط ل
ما يسمى أزواج قيمة المفتاح،

13
00:00:28,680 --> 00:00:32,080
رسم بعض قطعة من البيانات
لبعض قطعة أخرى من البيانات

14
00:00:32,080 --> 00:00:36,020
حتى نعرف أين تجد
المعلومات الواردة في الهيكل.

15
00:00:36,020 --> 00:00:40,060
>> وذلك لمجموعة، على سبيل المثال،
المفتاح هو مؤشر عنصر أو مجموعة

16
00:00:40,060 --> 00:00:42,600
0 موقع أو مجموعة 1 وهلم جرا.

17
00:00:42,600 --> 00:00:46,140
وكانت قيمة البيانات
موجود في ذلك المكان.

18
00:00:46,140 --> 00:00:48,550
فما يتم تخزينها في مجموعة 0؟

19
00:00:48,550 --> 00:00:54,290
ما يتم تخزينها في مجموعة 1 مقابل فقط
0 و 1، والتي ستكون المفاتيح.

20
00:00:54,290 --> 00:00:56,360
>> مع جدول تجزئة انها
نوع من الفكرة نفسها.

21
00:00:56,360 --> 00:01:00,690
مع جدول تجزئة، لدينا هذه البعثرة
وظيفة أن يولد رموز التجزئة.

22
00:01:00,690 --> 00:01:03,670
وبالتالي فإن الحل هو رمز تجزئة البيانات.

23
00:01:03,670 --> 00:01:06,530
والقيمة، وخاصة
تحدثنا حول تسلسل

24
00:01:06,530 --> 00:01:10,590
في الفيديو على الجداول التجزئة،
هي أن قائمة مرتبطة البيانات

25
00:01:10,590 --> 00:01:12,550
أن يفرم إلى أن hashcode.

26
00:01:12,550 --> 00:01:14,050
الصحيح.

27
00:01:14,050 --> 00:01:16,050
ماذا عن نهج آخر
هذا الأسلوب، على الرغم من؟

28
00:01:16,050 --> 00:01:21,000
ماذا عن طريقة حيث
مكفول المفتاح لتكون فريدة من نوعها،

29
00:01:21,000 --> 00:01:25,410
خلافا لجدول التجزئة، حيث استطعنا
ينتهي مع قطعتين من البيانات

30
00:01:25,410 --> 00:01:27,200
لها نفس hashcode.

31
00:01:27,200 --> 00:01:30,020
ثم علينا أن نتعامل مع
هذا إما عن طريق التحقيق أو أكثر

32
00:01:30,020 --> 00:01:33,340
ويفضل أن يكون تسلسل لإصلاح هذه المشكلة.

33
00:01:33,340 --> 00:01:37,520
>> وحتى الآن يمكننا ضمان
هذا المفتاح لدينا وسوف تكون فريدة من نوعها.

34
00:01:37,520 --> 00:01:39,690
وماذا لو كانت قيمة لدينا
مجرد شيء سهلا

35
00:01:39,690 --> 00:01:44,080
صحيح كما وكاذبة أن يقول لنا ما إذا كان
أو ليس هذا قطعة من المعلومات

36
00:01:44,080 --> 00:01:45,610
موجود في بنية؟

37
00:01:45,610 --> 00:01:48,180
A منطقية يمكن أن تكون بسيطة مثل قليلا.

38
00:01:48,180 --> 00:01:52,660
واقعيا هو على الأرجح
البايت أكثر عرضة من بعض الشيء.

39
00:01:52,660 --> 00:01:55,410
ولكن هذا أصغر كثيرا من
تخزين ربما سلسلة 50 حرف،

40
00:01:55,410 --> 00:01:57,360
على سبيل المثال.

41
00:01:57,360 --> 00:02:02,210
>> لذلك يحاول، على غرار تجزئة الجداول،
التي تجمع بين المصفوفات وقائمة مرتبطة،

42
00:02:02,210 --> 00:02:05,790
يحاول الجمع بين المصفوفات،
الهياكل، ومؤشرات

43
00:02:05,790 --> 00:02:08,509
معا لتخزين البيانات في
طريقة مثيرة للاهتمام هذا

44
00:02:08,509 --> 00:02:11,550
مختلفة جدا من
أي شيء رأيناه حتى الآن.

45
00:02:11,550 --> 00:02:16,750
ونحن الآن استخدام البيانات بمثابة خارطة الطريق
للتنقل هذه البنية البيانات.

46
00:02:16,750 --> 00:02:18,710
واذا كنا نستطيع متابعة
خارطة الطريق، اذا كنا نستطيع

47
00:02:18,710 --> 00:02:22,390
اتبع البيانات من
البداية إلى النهاية، وسوف نقوم

48
00:02:22,390 --> 00:02:24,945
معرفة ما إذا كانت هذه البيانات
موجودة في TRIE.

49
00:02:24,945 --> 00:02:28,310
>> وإذا كنا لا نستطيع تتبع خريطة
من معنى ليغلق عند كل شيء،

50
00:02:28,310 --> 00:02:30,600
البيانات لا يمكن أن توجد.

51
00:02:30,600 --> 00:02:32,890
مرة أخرى، مفاتيح هنا
يضمن أن تكون فريدة من نوعها.

52
00:02:32,890 --> 00:02:36,020
وذلك خلافا جدول تجزئة، وسوف نقوم أبدا
لديك للتعامل مع الاصطدامات هنا.

53
00:02:36,020 --> 00:02:39,090
وليس قطعتين من البيانات
لدينا بالضبط نفس خارطة الطريق

54
00:02:39,090 --> 00:02:40,530
إلا أن البيانات متطابقة.

55
00:02:40,530 --> 00:02:44,580
>> إذا كان لنا أن إدراج جون، ثم
نحن نبحث عن جون.

56
00:02:44,580 --> 00:02:47,430
هذا هو قطعتين متطابقتين
البيانات، والحق، نحن نبحث عن طريق.

57
00:02:47,430 --> 00:02:49,880
لكن على خلاف ذلك، أي
قطعتين من البيانات

58
00:02:49,880 --> 00:02:52,750
مضمونة لدينا خرائط فريدة من نوعها
من خلال هذه البنية البيانات.

59
00:02:52,750 --> 00:02:56,210
ونحن في طريقنا لنلقي نظرة على
البصرية من هذا في مجرد لحظة.

60
00:02:56,210 --> 00:02:58,810
>> سنفعل ذلك من خلال محاولة ل
إنشاء بنية البيانات الجديدة،

61
00:02:58,810 --> 00:03:00,564
رسم أزواج قيمة المفتاح التالي.

62
00:03:00,564 --> 00:03:03,480
في هذه الحالة، نحن لا تنوي استخدام
شيء بسيط مثل منطقية.

63
00:03:03,480 --> 00:03:06,200
ونحن في الواقع سيتم تخزين السلسلة.

64
00:03:06,200 --> 00:03:08,690
وهذه السلسلة هو الذهاب الى
يكون اسم الجامعة.

65
00:03:08,690 --> 00:03:12,140
>> والمفتاح سيكون العام
عندما تأسست تلك الجامعة.

66
00:03:12,140 --> 00:03:15,380
جميع السنوات للجامعات
ستكون أربعة أرقام.

67
00:03:15,380 --> 00:03:19,840
ولذا فإننا سوف تستخدم هذه الأرقام الأربعة ل
التنقل عبر هذه البنية البيانات.

68
00:03:19,840 --> 00:03:22,270
وسنرى، مرة أخرى، كيف
نفعل ذلك فقط في الثانية.

69
00:03:22,270 --> 00:03:25,110
>> في نهاية المسار،
سنرى اسم

70
00:03:25,110 --> 00:03:30,250
الجامعة الذي يتوافق
لهذا المفتاح، تلك الأرقام الأربعة.

71
00:03:30,250 --> 00:03:34,390
الفكرة الأساسية وراء TRIE
هو لدينا طريقا المركزي.

72
00:03:34,390 --> 00:03:35,640
حتى تفكر في ذلك مثل شجرة.

73
00:03:35,640 --> 00:03:39,211
وهذا هو مماثل في الإملاء
ومفهوم إلى شجرة.

74
00:03:39,211 --> 00:03:41,460
عموما عندما نفكر
الأشجار في العالم الحقيقي،

75
00:03:41,460 --> 00:03:44,090
لديهم الجذر الذي هو في
الأرض وأنها تنمو إلى الأعلى

76
00:03:44,090 --> 00:03:46,830
ولها فروع
ولديهم الأوراق.

77
00:03:46,830 --> 00:03:49,450
وأساسا فكرة
وTRIE هو نفسه تماما،

78
00:03:49,450 --> 00:03:51,755
إلا يرتكز أن الجذر
في مكان ما في السماء.

79
00:03:51,755 --> 00:03:53,130
والأوراق في الجزء السفلي.

80
00:03:53,130 --> 00:03:55,750
>> لذلك نوع من مثل أخذ شجرة
وعادل التقليب رأسا على عقب.

81
00:03:55,750 --> 00:03:56,880
لكن لا تزال هناك فروع.

82
00:03:56,880 --> 00:03:59,463
وتلك ستكون مسارات لدينا،
تلك ستكون لدينا اتصالات

83
00:03:59,463 --> 00:04:02,220
من الجذر إلى الأوراق.

84
00:04:02,220 --> 00:04:04,200
في هذه الحالة، تلك
مسارات، تلك الفروع

85
00:04:04,200 --> 00:04:08,490
وصفت مع الأرقام التي تخبرنا
وسيلة للذهاب من حيث نحن.

86
00:04:08,490 --> 00:04:11,800
>> إذا كنا نرى 0، نذهب إلى أسفل هذا الفرع،
إذا كان لنا أن نرى 1، ونحن ننزل هذا الفرع،

87
00:04:11,800 --> 00:04:12,900
وهكذا وهلم جرا.

88
00:04:12,900 --> 00:04:14,060
حسنا، ماذا يعني هذا؟

89
00:04:14,060 --> 00:04:16,519
حسنا، هذا يعني أن
في كل نقطة تقاطع

90
00:04:16,519 --> 00:04:19,260
وكل عقدة في
وسط وكل فرع،

91
00:04:19,260 --> 00:04:23,020
هناك 10 ممكن
الأماكن التي يمكننا أن نذهب.

92
00:04:23,020 --> 00:04:27,690
لذلك هناك 10 مؤشرات
من كل مكان.

93
00:04:27,690 --> 00:04:30,610
>> وهذا هو المكان الذي يمكن أن يحاول الحصول على
قليلا تخويف لشخص

94
00:04:30,610 --> 00:04:34,460
من هو لا يملك الكثير من
الخبرة في علوم الكمبيوتر من قبل.

95
00:04:34,460 --> 00:04:35,960
ولكن محاولات حقا رهيبة جدا.

96
00:04:35,960 --> 00:04:37,793
وإذا كان لديك
فرصة للعمل معهم

97
00:04:37,793 --> 00:04:40,420
وكنت على استعداد للحفر في
وتجربة معهم،

98
00:04:40,420 --> 00:04:44,234
انهم حقا مثيرة للاهتمام للغاية
هياكل البيانات للعمل مع.

99
00:04:44,234 --> 00:04:46,900
إذا كنا نريد لادخال عنصر
في TRIE، كل ما عليك القيام به

100
00:04:46,900 --> 00:04:51,360
وبناء على المسار الصحيح
من الجذر إلى الأوراق.

101
00:04:51,360 --> 00:04:55,390
وهنا ما كل خطوة على طول
الطريقة قد تبدو.

102
00:04:55,390 --> 00:04:59,660
ونحن في طريقنا لتحديد البيانات الجديدة
هيكل لعقدة جديدة تسمى TRIE.

103
00:04:59,660 --> 00:05:02,560
>> وداخل تلك البيانات
هيكل هناك قطعتين.

104
00:05:02,560 --> 00:05:05,460
ونحن في طريقنا لتخزين
اسم الجامعة.

105
00:05:05,460 --> 00:05:09,410
ونحن في طريقنا للتخزين
مجموعة من المؤشرات

106
00:05:09,410 --> 00:05:12,190
إلى العقد الأخرى من نفس النوع.

107
00:05:12,190 --> 00:05:14,780
لذلك، مرة أخرى، وهذا هو هذا النوع
من مفهوم في كل مكان

108
00:05:14,780 --> 00:05:18,567
نحن، ونحن في 10 ممكن
الأماكن التي يمكن أن تذهب.

109
00:05:18,567 --> 00:05:20,150
إذا كنا نرى 0، نذهب إلى أسفل هذا الفرع.

110
00:05:20,150 --> 00:05:22,690
إذا كان لنا أن نرى 1، هذا الفرع،
وهلم جرا وهلم جرا وهلم جرا.

111
00:05:22,690 --> 00:05:25,160
لو قلنا 9، نذهب إلى أسفل هذا الفرع.

112
00:05:25,160 --> 00:05:28,220
لذلك عند كل نقطة تقاطع،
يمكننا أن نذهب 10 أماكن محتملة.

113
00:05:28,220 --> 00:05:35,740
لذلك كل عقدة يجب أن تحتوي على 10 مؤشرات
إلى العقد الأخرى، إلى 10 العقد الأخرى.

114
00:05:35,740 --> 00:05:39,810
>> والبيانات نحن تخزين غير
مجرد اسم الجامعة.

115
00:05:39,810 --> 00:05:41,060
لذلك دعونا بناء TRIE.

116
00:05:41,060 --> 00:05:44,860
دعونا إدراج زوجين
من العناصر في TRIE لدينا.

117
00:05:44,860 --> 00:05:46,740
حتى في أعلى جدا،
هذا هو العقدة الجذرية لدينا.

118
00:05:46,740 --> 00:05:49,740
هذا من المحتمل ان يكون شيئا
وأنت تسير على الصعيد العالمي تعلن.

119
00:05:49,740 --> 00:05:53,450
وأنت تسير على الصعيد العالمي المحافظة
مؤشر إلى هذه العقدة دائما.

120
00:05:53,450 --> 00:05:55,360
>> كنت سأقول،
يساوي الجذر، وكنت

121
00:05:55,360 --> 00:05:57,580
الذهاب إلى malloc نفسك عقدة TRIE.

122
00:05:57,580 --> 00:05:59,850
وأنت تسير أبدا
لمسة الجذر مرة أخرى.

123
00:05:59,850 --> 00:06:02,300
في كل مرة تريد
بدء التنقل من خلال،

124
00:06:02,300 --> 00:06:05,802
قمت بتعيين مؤشر آخر
يساوي الجذر، مثل بالسفر،

125
00:06:05,802 --> 00:06:07,760
وهو المثال الأول
استخدام في العديد من أشرطة الفيديو الخاصة بي

126
00:06:07,760 --> 00:06:11,090
هنا على المداخن وطوابير
وقوائم الارتباط وهلم جرا.

127
00:06:11,090 --> 00:06:13,320
>> قمت بتعيين مؤشر آخر
دعا بالسفر لاجتياز.

128
00:06:13,320 --> 00:06:15,890
وكنت تستخدم بالسفر للتنقل
من خلال بنية البيانات.

129
00:06:15,890 --> 00:06:17,500
لذلك دعونا نرى كيف أن هذا قد يبدو.

130
00:06:17,500 --> 00:06:19,880
حتى الآن، ما
لا عقدة تبدو وكأنها؟

131
00:06:19,880 --> 00:06:22,920
حسنا، تماما كما بياناتنا
وأشار البيان هيكل،

132
00:06:22,920 --> 00:06:26,906
لدينا السلسلة، والذي
في هذه الحالة فارغ.

133
00:06:26,906 --> 00:06:27,780
لا يوجد شيء هنا.

134
00:06:27,780 --> 00:06:29,550
>> ومجموعة من 10 مؤشرات.

135
00:06:29,550 --> 00:06:31,790
والآن، ونحن فقط
لديك 1 عقدة في هذا TRIE.

136
00:06:31,790 --> 00:06:33,110
لا يوجد شيء آخر في ذلك.

137
00:06:33,110 --> 00:06:36,020
لذلك كل 10 من هؤلاء
نقطة مؤشرات لاغية.

138
00:06:36,020 --> 00:06:38,090
وهذا ما يشير إلى الأحمر.

139
00:06:38,090 --> 00:06:39,500
>> دعونا إدراج سلسلة هارفارد.

140
00:06:39,500 --> 00:06:41,999
دعونا إدراج جامعة
جامعة هارفارد في هذا TRIE، التي

141
00:06:41,999 --> 00:06:43,940
تأسست في العام 1636.

142
00:06:43,940 --> 00:06:48,220
نحن نريد استخدام المفتاح،
1636، ليقول لنا أين نحن

143
00:06:48,220 --> 00:06:50,140
الذهاب لتخزين هارفارد في TRIE.

144
00:06:50,140 --> 00:06:51,470
الآن، كيف يمكن لنا أن نفعل ذلك؟

145
00:06:51,470 --> 00:06:52,886
>> قد تبدو شيئا من هذا القبيل.

146
00:06:52,886 --> 00:06:54,160
نبدأ من جذورها.

147
00:06:54,160 --> 00:06:56,920
ونحن لدينا هذه 10 أماكن يمكن أن نذهب.

148
00:06:56,920 --> 00:06:59,900
الجذر هو تماما مثل أي
عقدة أخرى من TRIE.

149
00:06:59,900 --> 00:07:02,850
هناك 10 أماكن يمكن أن نذهب من هنا.

150
00:07:02,850 --> 00:07:07,215
>> أين نحن ربما تريد
للذهاب إذا كان المفتاح هو 1636؟

151
00:07:07,215 --> 00:07:08,340
هناك حقا الخيارين.

152
00:07:08,340 --> 00:07:08,450
الصحيح.

153
00:07:08,450 --> 00:07:10,825
يمكننا أن نبني المفتاح من
اليمين إلى اليسار وتبدأ 6.

154
00:07:10,825 --> 00:07:14,000
أو يمكننا أن نبني المفتاح من
من اليسار إلى اليمين وتبدأ 1.

155
00:07:14,000 --> 00:07:16,140
>> هو على الأرجح أكثر
بديهية كإنسان

156
00:07:16,140 --> 00:07:18,110
لفهم سنقوم
اذهبوا اليسار إلى اليمين.

157
00:07:18,110 --> 00:07:21,140
وحتى لو كنت تريد إدراج
جامعة هارفارد في هذا TRIE،

158
00:07:21,140 --> 00:07:23,560
أنا ربما تريد أن تبدأ
من خلال البدء في الجذر،

159
00:07:23,560 --> 00:07:25,720
أبحث في خياراتي 10
أمامي، وقوله

160
00:07:25,720 --> 00:07:28,700
أريد أن أذهب في الطريق 1.

161
00:07:28,700 --> 00:07:29,700
حسنا.

162
00:07:29,700 --> 00:07:31,810
>> الآن، 1 مسار باطل حاليا.

163
00:07:31,810 --> 00:07:35,920
لذلك إذا كنت تريد أن المضي قدما في هذا الطريق
لإدراج هذا العنصر في TRIE،

164
00:07:35,920 --> 00:07:42,040
لا بد لي من malloc عقدة جديدة، لديها 1
نقطة هناك، ثم أنا على ما يرام.

165
00:07:42,040 --> 00:07:46,460
>> لذلك أنا في الأساس أنا في
حيث نقطة انا واقفة

166
00:07:46,460 --> 00:07:50,270
في جذور شجرة أو
TRIE وهناك 10 فرعا.

167
00:07:50,270 --> 00:07:52,260
ولكن كل فرع لديه
بوابة أمامه.

168
00:07:52,260 --> 00:07:53,060
الصحيح.

169
00:07:53,060 --> 00:07:54,850
لأنه لا يوجد أي شيء آخر هناك.

170
00:07:54,850 --> 00:07:56,522
لا ممر آمن.

171
00:07:56,522 --> 00:07:58,980
وهذا يعني أن هناك شيء
أسفل أي من تلك الفروع.

172
00:07:58,980 --> 00:08:02,532
إذا كنت تريد أن تبدأ بناء
شيء، أريد أن إزالة البوابة.

173
00:08:02,532 --> 00:08:04,490
أريد أن إزالة البوابة
أمام عدد 1.

174
00:08:04,490 --> 00:08:05,698
وأريد أن السير في هذا.

175
00:08:05,698 --> 00:08:08,060
وأريد أن أبني
مكان آخر بالنسبة لي للذهاب.

176
00:08:08,060 --> 00:08:09,470
>> وهذا ما قمت به هنا.

177
00:08:09,470 --> 00:08:11,430
حتى 1 لم يعد يشير إلى قيمة خالية.

178
00:08:11,430 --> 00:08:13,830
قلت انها آمنة للذهاب إلى هنا الآن.

179
00:08:13,830 --> 00:08:15,789
لقد بنيت عقدة أخرى.

180
00:08:15,789 --> 00:08:18,330
وعندما أحصل على تلك العقدة، وأنا
على قرار آخر لجعل.

181
00:08:18,330 --> 00:08:20,890
أين أنا ذاهب لنذهب من هنا؟

182
00:08:20,890 --> 00:08:22,700
>> حسنا، لقد ذهبت بالفعل إلى أسفل 1.

183
00:08:22,700 --> 00:08:24,470
أنا حتى الآن ربما تريد أن تذهب إلى أسفل 6.

184
00:08:24,470 --> 00:08:24,970
الصحيح.

185
00:08:24,970 --> 00:08:27,100
مرة أخرى، ولدي 10 موقعا يمكنني أن تختار.

186
00:08:27,100 --> 00:08:30,060
لذلك دعونا نذهب الآن إلى أسفل رقم 6.

187
00:08:30,060 --> 00:08:32,280
لذلك أنا مسح البوابة
أمام عدد 6.

188
00:08:32,280 --> 00:08:33,250
وأنا السير هناك.

189
00:08:33,250 --> 00:08:34,580
وأبني عقدة أخرى.

190
00:08:34,580 --> 00:08:37,630
ولقد وصلت نقطة تقاطع آخر.

191
00:08:37,630 --> 00:08:40,289
>> مرة أخرى، ولدي 10 الخيارات
لتعرف أين يمكنني أن أذهب.

192
00:08:40,289 --> 00:08:42,799
لقد انتقلت 1-6.

193
00:08:42,799 --> 00:08:44,215
حتى الآن أنا ربما تريد أن تذهب إلى 3.

194
00:08:44,215 --> 00:08:45,381
3، لا يوجد مكان يمكنني أن أذهب.

195
00:08:45,381 --> 00:08:48,980
لذلك يجب أن تمهد الطريق
وبناء نفسي فضاء جديد.

196
00:08:48,980 --> 00:08:50,870
ثم من 3، أين أريد أن أذهب؟

197
00:08:50,870 --> 00:08:52,450
أريد أن أذهب إلى أسفل 6.

198
00:08:52,450 --> 00:08:54,770
>> ومرة أخرى، كان لي ل
تمهيد الطريق لتحقيق ذلك.

199
00:08:54,770 --> 00:08:59,179
أنا حتى الآن قد استخدمت مفتاح بلدي لادخال خلق
العقد والبدء في بناء هذا TRIE.

200
00:08:59,179 --> 00:09:00,220
لقد بدأت في جذورها.

201
00:09:00,220 --> 00:09:03,666
لقد ذهبت إلى أسفل 1636.

202
00:09:03,666 --> 00:09:05,540
والآن أنا في القاع
هناك على هذه العقدة.

203
00:09:05,540 --> 00:09:06,610
وكنت قد تكون قادرة على
رؤيته على الشاشة.

204
00:09:06,610 --> 00:09:07,735
>> إلقاء الضوء عليها باللون الأصفر.

205
00:09:07,735 --> 00:09:10,020
هذا هو مكاني حاليا.

206
00:09:10,020 --> 00:09:11,300
ويتم مفتاح بلدي.

207
00:09:11,300 --> 00:09:13,030
لقد استنفدت كل موقف في مفتاح بلدي.

208
00:09:13,030 --> 00:09:15,040
لذلك لا أستطيع أن أذهب إلى أبعد من ذلك.

209
00:09:15,040 --> 00:09:17,720
حتى في هذه المرحلة، كل ما
تحتاج حقا القيام به هو القول، OK.

210
00:09:17,720 --> 00:09:18,990
انها نوع من مثل أبحث
إلى الأرض،

211
00:09:18,990 --> 00:09:21,115
إذا كنت تتصور
نفسك هذا النوع من مسار

212
00:09:21,115 --> 00:09:22,350
مع اتصالات مختلفة.

213
00:09:22,350 --> 00:09:25,800
نوع من غمط ونوع من
رذاذ الطلاء هارفارد على أرض الواقع.

214
00:09:25,800 --> 00:09:26,800
هذا هو اسم هذا.

215
00:09:26,800 --> 00:09:28,300
أعلم أن هذا ما هو على هذا الموقع.

216
00:09:28,300 --> 00:09:31,870
إذا بدأنا في جذور وننزل
1 ثم 6 ثم 3 ثم 6،

217
00:09:31,870 --> 00:09:32,780
اين انت؟

218
00:09:32,780 --> 00:09:35,640
حسنا إذا كنا ننظر إلى أسفل
ونحن نرى في جامعة هارفارد، ثم

219
00:09:35,640 --> 00:09:38,960
ونحن نعلم أن جامعة هارفارد وكان
تأسست في عام 1636 على اساس طريقة

220
00:09:38,960 --> 00:09:41,400
نحن نقوم بتنفيذ هذه البنية البيانات.

221
00:09:41,400 --> 00:09:43,177
بحيث كانت واضحة نأمل.

222
00:09:43,177 --> 00:09:44,760
ونحن في طريقنا للقيام اثنين من أكثر الإدراج.

223
00:09:44,760 --> 00:09:50,060
ونأمل انها سوف تساعد على
نرى هذا عمله مرتين أكثر من ذلك.

224
00:09:50,060 --> 00:09:52,210
>> الآن، دعونا إدراج جامعة أخرى.

225
00:09:52,210 --> 00:09:54,630
دعونا إدراج ييل في هذا TRIE.

226
00:09:54,630 --> 00:09:57,037
تأسست جامعة ييل عام 1701.

227
00:09:57,037 --> 00:09:58,870
لذلك سنبدأ في
الجذر، كما نفعل دائما.

228
00:09:58,870 --> 00:09:59,890
وضعنا مؤشر اجتياز.

229
00:09:59,890 --> 00:10:01,624
ونحن في طريقنا لاستخدام ذلك للتحرك من خلال.

230
00:10:01,624 --> 00:10:03,790
أول شيء نريد أن
القيام به هو السير في طريق 1.

231
00:10:03,790 --> 00:10:05,830
هذا هو الرقم الأول من المفتاح لدينا.

232
00:10:05,830 --> 00:10:08,420
لحسن الحظ، على الرغم من أننا لا
لديهم للقيام بأي عمل هذا الوقت.

233
00:10:08,420 --> 00:10:09,919
وقد تم بالفعل في تمهيد الطريق 1.

234
00:10:09,919 --> 00:10:13,520
I مسح عليه في السابق عندما كنت
تم إدراج هارفارد في 1636.

235
00:10:13,520 --> 00:10:18,090
حتى أتمكن من التحرك بأمان
بنسبة 1 ومجرد الذهاب الى هناك.

236
00:10:18,090 --> 00:10:20,150
إذا يمكن أن تتحرك إلى أسفل 1.

237
00:10:20,150 --> 00:10:22,930
>> الآن، على الرغم من أنني أريد أن أذهب إلى 7.

238
00:10:22,930 --> 00:10:24,280
I مهدت الطريق في 6.

239
00:10:24,280 --> 00:10:27,050
وأنا أعلم أنني يمكن بأمان
المضي قدما في الطريق 6.

240
00:10:27,050 --> 00:10:29,220
ولكني في حاجة إلى المضي قدما على طريق 7.

241
00:10:29,220 --> 00:10:30,580
فماذا يجب أن أفعل؟

242
00:10:30,580 --> 00:10:35,070
حسنا، تماما مثل قبل، أنا فقط بحاجة
لمسح البوابة، والخروج من الطريق،

243
00:10:35,070 --> 00:10:38,740
وبناء عقدة جديدة من مسار 7.

244
00:10:38,740 --> 00:10:40,250
تماما مثل هذا.

245
00:10:40,250 --> 00:10:42,930
>> أنا حتى الآن قد انتقلت 1 ثم 7.

246
00:10:42,930 --> 00:10:45,550
والآن لاحظت، وأنا الفرز
من على هذا فرع ثانوي جديد.

247
00:10:45,550 --> 00:10:46,050
الصحيح.

248
00:10:46,050 --> 00:10:49,260
كل شيء آخر من 16
على، وأنا لا يهمني.

249
00:10:49,260 --> 00:10:50,720
أنا لا أفعل أي شيء 16.

250
00:10:50,720 --> 00:10:51,750
أفعله 17 الاشياء.

251
00:10:51,750 --> 00:10:58,380
>> وحتى الآن من 17 يوم، لا بد لي
نوع من ارتياد آفاق جديدة هنا.

252
00:10:58,380 --> 00:11:00,462
الرقم التالي مفتاحي هو 0.

253
00:11:00,462 --> 00:11:01,670
I الواضح أنه لا يمكن الحصول على أي مكان.

254
00:11:01,670 --> 00:11:02,628
لقد بنيت فقط هذه العقدة.

255
00:11:02,628 --> 00:11:04,550
إذا كنت لا تعرف لا يوجد
مسارات قدما من هنا.

256
00:11:04,550 --> 00:11:06,370
لذلك يجب أن يجعل واحدة نفسي.

257
00:11:06,370 --> 00:11:09,360
>> لذلك أنا malloc عقدة جديدة
ولها 0 نقطة هناك.

258
00:11:09,360 --> 00:11:12,770
وبعد ذلك واحدة لمزيد من الوقت، وأنا malloc ل
عقدة جديدة ولها نقطة واحدة هناك.

259
00:11:12,770 --> 00:11:15,870
مرة أخرى، لقد استنفدت مفتاحي، 1701.

260
00:11:15,870 --> 00:11:18,472
لذلك أنا ننظر إلى أسفل وأنا رذاذ الطلاء ييل.

261
00:11:18,472 --> 00:11:19,680
هذا هو اسم هذه العقدة.

262
00:11:19,680 --> 00:11:24,660
>> وحتى الآن ما إذا كنت من أي وقت مضى بحاجة إلى معرفة ما إذا كان ييل
تم في هذا TRIE، وأبدأ في الجذر،

263
00:11:24,660 --> 00:11:27,060
I النزول 1701، وننظر إلى أسفل.

264
00:11:27,060 --> 00:11:30,030
وإذا أرى رذاذ ييل
رسمت على الأرض، ثم

265
00:11:30,030 --> 00:11:32,200
وأنا أعلم ييل موجود في هذا TRIE.

266
00:11:32,200 --> 00:11:32,950
دعونا نفعل أكثر واحد.

267
00:11:32,950 --> 00:11:36,430
دعونا إدراج دارتموث في هذا
TRIE، التي تأسست في عام 1769.

268
00:11:36,430 --> 00:11:37,750
>> تبدأ في الجذر مرة أخرى.

269
00:11:37,750 --> 00:11:39,445
أول أرقام نظري مفتاح بلدي هو 1.

270
00:11:39,445 --> 00:11:40,820
يمكنني التحرك بأمان في هذا الطريق.

271
00:11:40,820 --> 00:11:42,400
ما هو موجود بالفعل.

272
00:11:42,400 --> 00:11:44,040
الرقم التالي من مفتاحي هو 7.

273
00:11:44,040 --> 00:11:45,890
يمكنني التحرك بأمان في هذا الطريق.

274
00:11:45,890 --> 00:11:47,540
كان موجودا أيضا.

275
00:11:47,540 --> 00:11:49,000
>> وجهتي المقبلة هو 6.

276
00:11:49,000 --> 00:11:52,860
من هنا، من أين أنا حاليا
باللون الأصفر هناك في تلك العقدة الوسطى،

277
00:11:52,860 --> 00:11:56,060
6 مقفلة حاليا خارج.

278
00:11:56,060 --> 00:11:58,830
إذا كنت تريد أن تذهب في هذا الطريق،
لدي لبناء بنفسي.

279
00:11:58,830 --> 00:12:02,250
ولذا فإنني سوف malloc عقدة جديدة
ولها 6 نقطة هناك.

280
00:12:02,250 --> 00:12:04,250
وبعد ذلك، مرة أخرى، وأنا
اشتعلت فيه النيران مسارات جديدة هنا.

281
00:12:04,250 --> 00:12:10,750
>> لذلك أنا malloc عقدة جديدة بحيث من
هذا العدد مسار node-- 9-- ثم الآن

282
00:12:10,750 --> 00:12:13,584
إذا أسافر 1769، وأنا أتطلع إلى أسفل.

283
00:12:13,584 --> 00:12:15,500
لا يوجد شيء حاليا
رذاذ رسمت هناك.

284
00:12:15,500 --> 00:12:16,930
أستطيع أن أكتب دارتموث.

285
00:12:16,930 --> 00:12:20,710
ولقد أدرجت
دارتموث في TRIE.

286
00:12:20,710 --> 00:12:23,450
>> ذلك أن إدراج
الأشياء في TRIE.

287
00:12:23,450 --> 00:12:25,384
الآن نريد للبحث عن الأشياء.

288
00:12:25,384 --> 00:12:27,050
كيف يمكننا البحث عن الأشياء في TRIE؟

289
00:12:27,050 --> 00:12:29,170
حسنا، انها الى حد كبير نفس الفكرة.

290
00:12:29,170 --> 00:12:33,620
الآن نحن فقط استخدام الأرقام المفتاح
لنرى اذا كنا نستطيع التنقل من جذورها

291
00:12:33,620 --> 00:12:37,170
إلى أين نريد أن نذهب في TRIE.

292
00:12:37,170 --> 00:12:41,620
>> إذا ضربنا طريق مسدود في أي لحظة، ثم
ونحن نعلم أن هذا العنصر لا يمكن موجود

293
00:12:41,620 --> 00:12:44,500
وإلا سيكون هذا الطريق
وقد تم بالفعل تطهيرها.

294
00:12:44,500 --> 00:12:45,930
إذا كان لنا أن تجعل من كل وسيلة ل
في النهاية، كل ما عليك القيام به

295
00:12:45,930 --> 00:12:48,471
هو أن ننظر إلى أسفل ومعرفة ما إذا كان هذا
العنصر الذي نبحث عنه.

296
00:12:48,471 --> 00:12:49,335
إذا كان هذا هو النجاح.

297
00:12:49,335 --> 00:12:52,610
إذا لم تكن كذلك، تفشل.

298
00:12:52,610 --> 00:12:54,940
>> لذلك دعونا بحث عن
جامعة هارفارد في هذا TRIE.

299
00:12:54,940 --> 00:12:56,020
نبدأ من جذورها.

300
00:12:56,020 --> 00:12:58,228
ومرة أخرى، نحن في طريقنا لل
إنشاء مؤشر اجتياز

301
00:12:58,228 --> 00:12:59,390
للقيام التحركات بالنسبة لنا.

302
00:12:59,390 --> 00:13:02,080
من جذورها ونحن نعلم أن
المقام الأول نحتاج للذهاب 1،

303
00:13:02,080 --> 00:13:03,390
يمكننا أن نفعل ذلك؟

304
00:13:03,390 --> 00:13:03,982
نعم نستطيع.

305
00:13:03,982 --> 00:13:04,690
في حالة وجود بأمان.

306
00:13:04,690 --> 00:13:06,660
يمكننا الذهاب إلى هناك.

307
00:13:06,660 --> 00:13:08,440
>> الآن، والمكان القادمة ونحن في حاجة للذهاب هو 6.

308
00:13:08,440 --> 00:13:10,557
لا وجود مسار 6 من هنا؟

309
00:13:10,557 --> 00:13:11,140
نعم، فإنه لا.

310
00:13:11,140 --> 00:13:12,690
يمكننا السير في طريق 6.

311
00:13:12,690 --> 00:13:13,905
ونحن في نهاية المطاف هنا.

312
00:13:13,905 --> 00:13:16,130
>> يمكننا السير في الطريق 3 من هنا؟

313
00:13:16,130 --> 00:13:18,450
حسنا، كما اتضح،
نعم، موجود أيضا.

314
00:13:18,450 --> 00:13:20,790
ويمكن أن نحصل على الطريق 6 من هنا؟

315
00:13:20,790 --> 00:13:21,982
نعم نستطيع.

316
00:13:21,982 --> 00:13:24,002
>> ونحن لم يستجب تماما
السؤال حتى الآن.

317
00:13:24,002 --> 00:13:25,710
لا يزال هناك أكثر من
الخطوة، التي هي الآن

318
00:13:25,710 --> 00:13:28,520
علينا أن ننظر إلى أسفل و
معرفة ما إذا كان هذا actually--

319
00:13:28,520 --> 00:13:32,660
إذا نحن نبحث عن جامعة هارفارد، هو أن
ما نجده بعد أن يستنفد المفتاح؟

320
00:13:32,660 --> 00:13:35,430
في المثال نستخدمه هنا،
السنوات هي دائما أربعة أرقام.

321
00:13:35,430 --> 00:13:40,280
ولكن هل يمكن أن يكون باستخدام المثال حيث
يتم تخزين قاموس من الكلمات.

322
00:13:40,280 --> 00:13:44,060
>> وذلك بدلا من الاضطرار 10 مؤشرات
لموقعي، قد يكون لديك 26.

323
00:13:44,060 --> 00:13:46,040
واحد لكل حرف من الحروف الأبجدية.

324
00:13:46,040 --> 00:13:50,350
وهناك بعض الكلمات مثل الخفافيش،
وهي مجموعة فرعية من دفعة، على سبيل المثال.

325
00:13:50,350 --> 00:13:53,511
وحتى لو تحصل على
نهاية مفتاح وأنت تنظر إلى أسفل،

326
00:13:53,511 --> 00:13:55,260
قد لا نرى ما
كنت أبحث عنه.

327
00:13:55,260 --> 00:13:58,500
>> ولذلك عليك دائما أن تجتاز
كامل مسار ومن ثم

328
00:13:58,500 --> 00:14:01,540
إذا كنت قادرا بنجاح
لاجتياز المسار بالكامل،

329
00:14:01,540 --> 00:14:03,440
ننظر إلى أسفل والقيام التأكيد النهائي واحد.

330
00:14:03,440 --> 00:14:05,120
غير أن ما أبحث عنه؟

331
00:14:05,120 --> 00:14:07,740
حسنا، أنا ننظر إلى أسفل بعد بدء
في الجزء العلوي والذهاب 1636.

332
00:14:07,740 --> 00:14:08,240
أنا أنظر إلى أسفل.

333
00:14:08,240 --> 00:14:09,400
أرى هارفارد.

334
00:14:09,400 --> 00:14:11,689
لذا، نعم، لقد نجحت.

335
00:14:11,689 --> 00:14:13,980
ماذا لو كان ما أنا أبحث عن
ليس في TRIE، وإن كان.

336
00:14:13,980 --> 00:14:17,200
ماذا لو أنا أبحث عن برينستون،
التي تأسست في عام 1746.

337
00:14:17,200 --> 00:14:20,875
وهكذا يصبح 1746 مفتاحي
للتنقل عبر TRIE.

338
00:14:20,875 --> 00:14:22,040
حسنا، وأبدأ في جذورها.

339
00:14:22,040 --> 00:14:24,760
والمقام الأول أريد
ليذهب في الطريق 1.

340
00:14:24,760 --> 00:14:25,590
هل يمكن ان افعلها؟

341
00:14:25,590 --> 00:14:26,490
نعم استطيع.

342
00:14:26,490 --> 00:14:28,730
>> يمكنني السير في الطريق 7 من هناك؟

343
00:14:28,730 --> 00:14:29,230
نعم استطيع.

344
00:14:29,230 --> 00:14:30,750
موجود أيضا.

345
00:14:30,750 --> 00:14:32,460
ولكن يمكنني السير في طريق 4 من هنا؟

346
00:14:32,460 --> 00:14:35,550
هذا مثل طرح السؤال، يمكن
أنا نسير في هذا الميدان الصغير

347
00:14:35,550 --> 00:14:37,114
أنني قد سلط الضوء باللون الأصفر؟

348
00:14:37,114 --> 00:14:38,030
لا يوجد شيء هناك.

349
00:14:38,030 --> 00:14:38,610
الصحيح.

350
00:14:38,610 --> 00:14:41,310
>> ليس هناك طريقة للمضي قدما في الطريق (4).

351
00:14:41,310 --> 00:14:46,480
إذا كان برينستون في هذا TRIE، أن 4
قد تم تطهيرها بالنسبة لنا بالفعل.

352
00:14:46,480 --> 00:14:49,130
وحتى في هذه النقطة
لقد وصلت إلى طريق مسدود.

353
00:14:49,130 --> 00:14:50,250
لا نستطيع أن نذهب إلى أبعد من ذلك.

354
00:14:50,250 --> 00:14:53,440
وهكذا يمكن القول، بصورة نهائية، لا.

355
00:14:53,440 --> 00:14:56,760
برينستون غير موجود في هذا TRIE.

356
00:14:56,760 --> 00:14:58,860
>> فماذا يعني كل هذا؟

357
00:14:58,860 --> 00:14:59,360
الصحيح.

358
00:14:59,360 --> 00:15:01,000
هناك الكثير مما يجري هنا.

359
00:15:01,000 --> 00:15:02,500
هناك مؤشرات في كل مكان.

360
00:15:02,500 --> 00:15:04,249
وكما ترون
فقط من الرسم البياني،

361
00:15:04,249 --> 00:15:07,010
هناك الكثير من العقد التي
هي نوع من تحلق حولها.

362
00:15:07,010 --> 00:15:13,480
ولكن لاحظ في كل مرة أردنا أن
تحقق ما إذا كان شيء ما في TRIE،

363
00:15:13,480 --> 00:15:15,000
كان لدينا فقط لجعل 4 التحركات.

364
00:15:15,000 --> 00:15:17,208
>> في كل مرة كنا نريد ل
إدراج شيء في TRIE،

365
00:15:17,208 --> 00:15:20,440
لدينا لجعل 4 خطوات، وربما
mallocing بعض الاشياء على طول الطريق.

366
00:15:20,440 --> 00:15:23,482
ولكن كما رأينا عندما أدخلنا
دارتموث في TRIE،

367
00:15:23,482 --> 00:15:25,940
أحيانا بعض الطريق
قد يكون تم مسح بالنسبة لنا.

368
00:15:25,940 --> 00:15:30,520
وذلك كما يحصل TRIE لدينا أكبر و
أكبر، كنا نفعل عمل أقل في كل مرة

369
00:15:30,520 --> 00:15:32,270
لإدراج الأشياء الجديدة
لأننا بالفعل

370
00:15:32,270 --> 00:15:35,746
بنيت الكثير من وسيطة
فروع على طول الطريق.

371
00:15:35,746 --> 00:15:38,370
إذا كان لدينا أي وقت مضى إلا أن ننظر
4 أشياء، 4 هو مجرد ثابت.

372
00:15:38,370 --> 00:15:41,750
نحن حقا هي نوع من الاقتراب
ثابت الإدراج الوقت

373
00:15:41,750 --> 00:15:44,501
وبحث مستمر الوقت.

374
00:15:44,501 --> 00:15:47,500
المفاضلة، بطبيعة الحال، ويجري ذلك
هذا TRIE، كما يمكنك أن أقول ربما،

375
00:15:47,500 --> 00:15:49,030
ضخمة.

376
00:15:49,030 --> 00:15:51,040
كل واحد من هذه العقد
يستغرق الكثير من المساحة.

377
00:15:51,040 --> 00:15:52,090
>> ولكن هذا هو المقايضة.

378
00:15:52,090 --> 00:15:55,260
إذا كنا نريد حقا سريعة
الإدراج أو الحذف سريع حقا،

379
00:15:55,260 --> 00:15:59,630
وبحث سريع حقا، علينا أن
لديهم الكثير من البيانات تحلق حولها.

380
00:15:59,630 --> 00:16:03,590
علينا أن جانبا الكثير من الفضاء
والذاكرة لهذا بنية البيانات

381
00:16:03,590 --> 00:16:04,290
في الوجود.

382
00:16:04,290 --> 00:16:05,415
>> وذلك أن المفاضلة.

383
00:16:05,415 --> 00:16:07,310
ولكن يبدو أننا
ربما وجدت.

384
00:16:07,310 --> 00:16:09,560
ونحن قد وجدت أن
الكأس المقدسة من هياكل البيانات

385
00:16:09,560 --> 00:16:12,264
مع الإدراج السريع،
الحذف، والبحث.

386
00:16:12,264 --> 00:16:14,430
وربما سيكون هذا
هيكل البيانات المناسبة

387
00:16:14,430 --> 00:16:18,890
استخدام لأي من المعلومات
نحن نحاول أن المخزن.

388
00:16:18,890 --> 00:16:21,860
أنا دوغ ويد، وهذا هو cs50.

389
00:16:21,860 --> 00:16:23,433