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
داگ لوید: بنابراین ما شده میدل ایست ژورنال را نزدیک تر
و نزدیک تر که جام مقدس از داده

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
یک بولی می تواند به عنوان ساده به عنوان یک بیت.

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
می دانم که آیا که داده
در این درخت وجود دارد.

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
ایده اصلی در پشت یک درخت پیشوندی
این است که ما باید یک مسیر مرکزی.

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
و اساسا ایده
یک درخت پیشوندی است دقیقا همان است،

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
اگر ما می خواهیم به قرار دادن یک عنصر
به این درخت، همه ما نیاز به انجام

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
ما قصد داریم به تعریف یک داده جدید
ساختار برای یک گره جدید به نام یک درخت پیشوندی.

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
بنابراین اجازه دهید یک درخت پیشوندی ساخت.

116
00:05:41,060 --> 00:05:44,860
اجازه دهید وارد کردن یک زن و شوهر
از آیتم ها به درخت است.

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 گره درخت.

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
به شما در تنظیم یکی دیگر از اشاره گر
به ریشه های برابر، مانند TRAV،

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
>> به شما در تنظیم یکی دیگر از اشاره گر
نام TRAV برای پیمایش.

128
00:06:13,320 --> 00:06:15,890
و شما با استفاده TRAV به حرکت
از طریق ساختار داده ها.

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 گره در این درخت.

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
اجازه دهید وارد دانشگاه
دانشگاه هاروارد به این درخت که

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
رفتن به ذخیره هاروارد در این درخت.

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
ریشه مثل هر است
گره دیگر از این درخت به.

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
و بنابراین اگر من می خواهم برای قرار دادن
دانشگاه هاروارد به این درخت،

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
بنابراین اگر من می خواهم برای ادامه این مسیر
برای وارد کردن این عنصر به درخت،

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
در ریشه درخت یا
درخت و 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
بنابراین در حال حاضر من کلید من استفاده می شود به قرار دادن ایجاد
گره ها و شروع به ساخت این درخت.

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
اجازه دهید وارد دانشگاه ییل به این درخت.

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
من آن را پاک قبلا وقتی که من
شد قرار دادن دانشگاه هاروارد در 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
من راه در 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
و در حال حاضر متوجه میشوید که من هستم مرتب سازی بر
از این subbranch جدید است.

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
من به وضوح می تواند هر جای دریافت کنید.

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
>> و بنابراین در حال حاضر اگر من همیشه نیاز به دیدن اگر ییل
در این درخت به، من در ریشه شروع،

263
00:11:24,660 --> 00:11:27,060
من پایین 1701 رفت، و نگاه کردن.

264
00:11:27,060 --> 00:11:30,030
و اگر من اسپری ییل را ببینید
نقاشی بر روی زمین، پس از آن

265
00:11:30,030 --> 00:11:32,200
من می دانم که ییل در این درخت وجود دارد.

266
00:11:32,200 --> 00:11:32,950
اجازه دهید یکی بیشتر انجام دهد.

267
00:11:32,950 --> 00:11:36,430
اجازه دهید وارد کردن دارتموث به این
پیشوندی، که در سال 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
و من قرار داده ام
دارتموث به این درخت.

286
00:12:20,710 --> 00:12:23,450
>> به طوری که قرار دادن
همه چیز را به این درخت.

287
00:12:23,450 --> 00:12:25,384
حالا ما می خواهیم به جستجو برای چیزهایی.

288
00:12:25,384 --> 00:12:27,050
چگونه ما برای چیزهایی در این درخت را جستجو کنم؟

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
به جایی که ما می خواهیم در این درخت.

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
>> بنابراین اجازه دهید برای جستجو
دانشگاه هاروارد در این درخت.

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
اگر چه من به دنبال
است در این درخت نیست، هر چند.

336
00:14:13,980 --> 00:14:17,200
چه می شود اگر من به دنبال پرینستون،
که در سال 1746 تاسیس شد.

337
00:14:17,200 --> 00:14:20,875
و به این ترتیب 1746 کلید من می شود
به این درخت به حرکت.

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
اگر پرینستون در این درخت بود، که 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
پرینستون می کند در این درخت وجود ندارد.

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
اما توجه کنید هر زمان که ما را به خواست
بررسی کنید که آیا چیزی در این درخت بود،

363
00:15:13,480 --> 00:15:15,000
ما تنها تا به حال به 4 حرکت می کند.

364
00:15:15,000 --> 00:15:17,208
>> هر بار که ما می خواستیم
قرار دادن چیزی در این درخت،

365
00:15:17,208 --> 00:15:20,440
ما را به 4 حرکت می کند، احتمالا
mallocing برخی از مسائل در طول راه.

366
00:15:20,440 --> 00:15:23,482
اما همانطور که ما را دیدم زمانی که ما وارد می
دارتموث به این درخت،

367
00:15:23,482 --> 00:15:25,940
گاهی اوقات برخی از مسیر
ممکن است در حال حاضر برای ما پاک شود.

368
00:15:25,940 --> 00:15:30,520
و بنابراین به عنوان درخت ما می شود بزرگتر و
بزرگتر، ما باید کار کمتری انجام هر زمان

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
معاوضه، البته، این است که
این درخت، همانطور که شما احتمالا می توانید بگویید،

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