1
00:00:00,000 --> 00:00:02,994
>> [MUSIC PLAYING]

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

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Beləliklə, biz yaxın inching olduğunuz
və yaxın veri müqəddəs grail

4
00:00:08,550 --> 00:00:13,050
biz əlavə edə bilərsiniz strukturları bir
daxil silmek və yuxarı baxmaq

5
00:00:13,050 --> 00:00:15,440
daimi vaxt.

6
00:00:15,440 --> 00:00:16,270
Right.

7
00:00:16,270 --> 00:00:17,280
Ki, məqsəd sort var.

8
00:00:17,280 --> 00:00:19,720
Biz bunu etmək istəyirəm
şeyi çox, çox tez.

9
00:00:19,720 --> 00:00:22,580
>> Biz burada zaman gördük
biz çalışır bəhs edirik?

10
00:00:22,580 --> 00:00:23,670
Yaxşı, bir nəzər salaq.

11
00:00:23,670 --> 00:00:25,628
Beləliklə, biz bir neçə gördüm
müxtəlif məlumat strukturları

12
00:00:25,628 --> 00:00:28,680
ki, birdən idarə
əsas dəyər cüt qondarma,

13
00:00:28,680 --> 00:00:32,080
məlumatların bəzi parça Xəritəçəkmə
məlumatların bəzi digər parça

14
00:00:32,080 --> 00:00:36,020
belə ki, biz tapmaq üçün harada
strukturunda məlumat.

15
00:00:36,020 --> 00:00:40,060
>> Belə ki array üçün, məsələn,
əsas element index və ya array var

16
00:00:40,060 --> 00:00:42,600
yeri 0 və ya array 1 və s.

17
00:00:42,600 --> 00:00:46,140
Və dəyəri data
ki, yeri var.

18
00:00:46,140 --> 00:00:48,550
Belə ki, serialın 0 nə saxlanılır?

19
00:00:48,550 --> 00:00:54,290
Nə yalnız qarşı array 1 saxlanılır
0 və 1, düymələri olacaq.

20
00:00:54,290 --> 00:00:56,360
>> Bir hash masa ilə bu
Eyni fikir sort.

21
00:00:56,360 --> 00:01:00,690
Bir hash masa ilə, bu hash var
hash kodları yaradır fəaliyyət göstərir.

22
00:01:00,690 --> 00:01:03,670
Belə ki, əsas məlumatların hash kodu.

23
00:01:03,670 --> 00:01:06,530
Və dəyəri, xüsusilə
biz zəncirləmə haqqında danışdı

24
00:01:06,530 --> 00:01:10,590
hash masalar video,
məlumatların ki, bağlı siyahısı

25
00:01:10,590 --> 00:01:12,550
ki hashcode üçün hashes.

26
00:01:12,550 --> 00:01:14,050
Right.

27
00:01:14,050 --> 00:01:16,050
Başqa yanaşma haqqında nə
bu üsul olsa?

28
00:01:16,050 --> 00:01:21,000
Bir üsul haqqında nə olduğu
əsas, unikal olması təmin edilir

29
00:01:21,000 --> 00:01:25,410
bir hash masa, biz bilər fərqli
məlumatların iki ədəd ilə başa

30
00:01:25,410 --> 00:01:27,200
Eyni hashcode olan.

31
00:01:27,200 --> 00:01:30,020
Və sonra biz ilə məşğul
ki, ya probing və ya daha çox

32
00:01:30,020 --> 00:01:33,340
üstünlük problemi həll etmək chaining.

33
00:01:33,340 --> 00:01:37,520
>> Belə ki, indi biz təmin edə bilər
ki, əsas unikal olacaq.

34
00:01:37,520 --> 00:01:39,690
Və dəyəri nə idi
asan kimi yalnız bir şey

35
00:01:39,690 --> 00:01:44,080
olub bizə deyir ki, doğru və yalan
məlumat və ya deyil ki, parça

36
00:01:44,080 --> 00:01:45,610
tərkibində mövcuddur?

37
00:01:45,610 --> 00:01:48,180
A Boolean bir az kimi sadə ola bilər.

38
00:01:48,180 --> 00:01:52,660
Real yəqin ki, bir
bir az daha çox ehtimal byte.

39
00:01:52,660 --> 00:01:55,410
Amma bu çox kiçik
50 xarakter string bəlkə saxlanılması,

40
00:01:55,410 --> 00:01:57,360
misal üçün.

41
00:01:57,360 --> 00:02:02,210
>> Çalışır, belə ki, masalar hash oxşar,
olan birləşdirmək seriallarda və bağlı siyahısı,

42
00:02:02,210 --> 00:02:05,790
çalışır Diziler birləşdirmək,
strukturları və göstəricilər

43
00:02:05,790 --> 00:02:08,509
birlikdə veri
ki, bir maraqlı yol

44
00:02:08,509 --> 00:02:11,550
olduqca müxtəlif
Biz bu günə qədər gördüm bir şey.

45
00:02:11,550 --> 00:02:16,750
İndi biz bir yol xəritəsi kimi data istifadə
Bu data strukturu naviqasiya.

46
00:02:16,750 --> 00:02:18,710
Və biz təqib edə bilər, əgər
yol xəritəsi, biz əgər

47
00:02:18,710 --> 00:02:22,390
məlumat edin
başından sonuna qədər alacağıq

48
00:02:22,390 --> 00:02:24,945
ki, data olub-olmadığını bilmək
trie mövcuddur.

49
00:02:24,945 --> 00:02:28,310
>> Və biz xəritəsi edin bilməz, əgər
bütün son, yəni ki,

50
00:02:28,310 --> 00:02:30,600
məlumat mövcud deyil.

51
00:02:30,600 --> 00:02:32,890
Yenə düymələri burada
Unikal olması təmin.

52
00:02:32,890 --> 00:02:36,020
Belə bir hash masa fərqli olaraq, biz heç vaxt lazımdır
Burada toqquşma ilə məşğul olmalıdır.

53
00:02:36,020 --> 00:02:39,090
Və məlumatların heç bir iki ədəd
eyni yol xəritəsi var

54
00:02:39,090 --> 00:02:40,530
halda ki, data eynidir.

55
00:02:40,530 --> 00:02:44,580
>> Biz John, sonra daxil olarsa
biz John üçün axtarış.

56
00:02:44,580 --> 00:02:47,430
Ki, iki eyni ədəd var
data, sağ, biz vasitəsilə baxırıq.

57
00:02:47,430 --> 00:02:49,880
Lakin başqa, hər hansı bir
məlumatların iki ədəd var

58
00:02:49,880 --> 00:02:52,750
unikal yol xəritələri üçün zəmanət
Bu data strukturu vasitəsilə.

59
00:02:52,750 --> 00:02:56,210
Və biz nəzər olacaq
yalnız bir anda bu vizual.

60
00:02:56,210 --> 00:02:58,810
>> Biz çalışırıq bu edəcəyik
yeni data strukturu yaratmaq,

61
00:02:58,810 --> 00:03:00,564
aşağıdakı əsas dəyər cüt Xəritəçəkmə.

62
00:03:00,564 --> 00:03:03,480
Bu halda, biz istifadə etmək fikrində deyilik
boolean kimi sadə bir şey.

63
00:03:03,480 --> 00:03:06,200
Biz, həqiqətən, simli saxlamaq olacaq.

64
00:03:06,200 --> 00:03:08,690
Və string gedir
bir universitetin adı.

65
00:03:08,690 --> 00:03:12,140
>> Və əsas il olacaq
universitet təsis edildiyi.

66
00:03:12,140 --> 00:03:15,380
Ali Bütün il
dörd rəqəm olacaq.

67
00:03:15,380 --> 00:03:19,840
Və belə ki, biz bu dörd rəqəm istifadə edəcəyik
Bu data strukturu vasitəsilə gedin.

68
00:03:19,840 --> 00:03:22,270
Və biz yenə görəcəksiniz, necə
biz yalnız ikinci bunu.

69
00:03:22,270 --> 00:03:25,110
>> Yolun sonunda,
biz adını görəcəksiniz

70
00:03:25,110 --> 00:03:30,250
uyğundur universitetin
ki əsas, bu dörd rəqəm.

71
00:03:30,250 --> 00:03:34,390
bir trie əsas ideyası
biz mərkəzi marşrut var.

72
00:03:34,390 --> 00:03:35,640
Belə ki, bir ağac kimi bu barədə düşünürəm.

73
00:03:35,640 --> 00:03:39,211
Bu yazım oxşar
və ağaca anlayışı.

74
00:03:39,211 --> 00:03:41,460
Ümumiyyətlə, biz haqqında düşünmək zaman
real dünyada ağaclar,

75
00:03:41,460 --> 00:03:44,090
onlar bir kök
torpaq və onlar yuxarı inkişaf

76
00:03:44,090 --> 00:03:46,830
və onlar filial
və onlar yarpaqları var.

77
00:03:46,830 --> 00:03:49,450
Və əsasən fikir
bir trie, tam eyni deyil

78
00:03:49,450 --> 00:03:51,755
ki, kök anchored edir istisna olmaqla,
Göy yerdə.

79
00:03:51,755 --> 00:03:53,130
Və yarpaqları altındakı var.

80
00:03:53,130 --> 00:03:55,750
>> Belə ki, bir ağac alaraq kimi növ var
və yalnız altüst Flipping.

81
00:03:55,750 --> 00:03:56,880
Amma yenə də filialları var.

82
00:03:56,880 --> 00:03:59,463
Və bu bizim yollar olacaq,
o bizim əlaqələri olacaq

83
00:03:59,463 --> 00:04:02,220
yarpaqları kök.

84
00:04:02,220 --> 00:04:04,200
Bu halda, o
yolları, o filialları

85
00:04:04,200 --> 00:04:08,490
bizə rəqəm ilə etiketli olunur
hansı yolla biz burada getmək.

86
00:04:08,490 --> 00:04:11,800
>> Biz bir 0 görürsünüzsə, biz bu sahədə enmək,
Biz bir 1 görürsünüzsə, biz bu sahədə enmək,

87
00:04:11,800 --> 00:04:12,900
və s və s.

88
00:04:12,900 --> 00:04:14,060
Bəli, bu nə deməkdir?

89
00:04:14,060 --> 00:04:16,519
Yaxşı ki, o deməkdir ki,
hər qovşağında nöqtədə

90
00:04:16,519 --> 00:04:19,260
və hər node
orta və hər filialı,

91
00:04:19,260 --> 00:04:23,020
Mümkün 10 var
biz getmək bilər yerlərdə.

92
00:04:23,020 --> 00:04:27,690
Belə ki, 10 göstəricilərinə var
hər yerdən.

93
00:04:27,690 --> 00:04:30,610
>> Çalışır bir əldə edə bilərsiniz və bu
kimsə üçün qorxuducu az

94
00:04:30,610 --> 00:04:34,460
kim bir çox yoxdur
əvvəl kompüter təcrübəsi.

95
00:04:34,460 --> 00:04:35,960
Amma çalışır həqiqətən olduqca zəhmli edir.

96
00:04:35,960 --> 00:04:37,793
Və varsa
onlarla işləmək imkanı

97
00:04:37,793 --> 00:04:40,420
və qazmaq-in istediğiniz
və onlarla təcrübə,

98
00:04:40,420 --> 00:04:44,234
Onlar, həqiqətən, olduqca maraqlı deyilik
data strukturları ilə işləmək üçün.

99
00:04:44,234 --> 00:04:46,900
Biz bir element əlavə etmək istəyirsinizsə,
trie daxil bütün biz nə etmək lazımdır

100
00:04:46,900 --> 00:04:51,360
doğru yol qurmaq
yarpaq kök.

101
00:04:51,360 --> 00:04:55,390
Burada nə hər bir addım birlikdə var
yol kimi görünə bilər.

102
00:04:55,390 --> 00:04:59,660
Biz yeni məlumatlar müəyyən olacaq
yeni node üçün struktur bir trie çağırıb.

103
00:04:59,660 --> 00:05:02,560
>> Və məlumatların daxili
quruluşu iki ədəd var.

104
00:05:02,560 --> 00:05:05,460
Biz saxlamaq olacaq
bir universitetin adı.

105
00:05:05,460 --> 00:05:09,410
Və biz saxlamaq olacaq
göstəricilər bir sıra

106
00:05:09,410 --> 00:05:12,190
eyni tipli digər qovşaqlarının.

107
00:05:12,190 --> 00:05:14,780
Belə ki, daha, bu ki, sort deyil
Hər yerdə anlayışının

108
00:05:14,780 --> 00:05:18,567
biz 10 mümkün var
biz getmək bilər yerlərdə.

109
00:05:18,567 --> 00:05:20,150
Biz bir 0 görürsünüzsə, bu filialı enmək.

110
00:05:20,150 --> 00:05:22,690
Biz 1 görürsünüzsə, bu sahədə,
və s və s və s.

111
00:05:22,690 --> 00:05:25,160
Biz 9 demək olarsa, bu filialı enmək.

112
00:05:25,160 --> 00:05:28,220
Hər qovşağında nöqtədə So
10 mümkün yerlərdə bilərsiniz.

113
00:05:28,220 --> 00:05:35,740
Belə ki, hər node 10 göstəricilərinə ehtiva edir
10 qovşaqlarının digər qovşaqlarının, üçün.

114
00:05:35,740 --> 00:05:39,810
>> Və biz saxlanılması edirik məlumatdır
universitetin yalnız adı.

115
00:05:39,810 --> 00:05:41,060
Belə ki, bir trie inşa edək.

116
00:05:41,060 --> 00:05:44,860
Bir neçə daxil edək
Bizim trie daxil maddələr.

117
00:05:44,860 --> 00:05:46,740
, Çox üst So
bu, bizim kök node edir.

118
00:05:46,740 --> 00:05:49,740
Bu yəqin ki, bir şey olacaq
Siz elan Qlobal olacaq.

119
00:05:49,740 --> 00:05:53,450
Və saxlamaq Qlobal olacaq
həmişə bu node bir göstərici.

120
00:05:53,450 --> 00:05:55,360
>> Siz demək olacaq
kök bərabərdir, və istəyirik

121
00:05:55,360 --> 00:05:57,580
Özünüz trie node malloc gedir.

122
00:05:57,580 --> 00:05:59,850
Və heç vaxt olacaq
daha kök toxunmaq.

123
00:05:59,850 --> 00:06:02,300
Siz istədiyiniz hər dəfə
gezinmek başlamaq,

124
00:06:02,300 --> 00:06:05,802
Başqa bir göstərici müəyyən
Belə trav kimi, kök bərabər,

125
00:06:05,802 --> 00:06:07,760
olan nümunə var
Mənim Videonun çox istifadə

126
00:06:07,760 --> 00:06:11,090
burada çıxarıcı borular və kuyrukları
və link siyahıları və s.

127
00:06:11,090 --> 00:06:13,320
>> Başqa bir göstərici müəyyən
traversal üçün Trav çağırıb.

128
00:06:13,320 --> 00:06:15,890
Və naviqasiya Trav istifadə
data strukturu vasitəsilə.

129
00:06:15,890 --> 00:06:17,500
Belə ki, bu ola bilər necə edək.

130
00:06:17,500 --> 00:06:19,880
Belə ki, indi, nə
bir node kimi görünür?

131
00:06:19,880 --> 00:06:22,920
Bəli, yalnız bizim data kimi
strukturu bəyannamə, göstərilən

132
00:06:22,920 --> 00:06:26,906
biz bir simli var olan
bu halda boş.

133
00:06:26,906 --> 00:06:27,780
Burada bir şey yoxdur.

134
00:06:27,780 --> 00:06:29,550
>> 10 göstəricilər bir sıra.

135
00:06:29,550 --> 00:06:31,790
Və indi, biz yalnız
bu trie 1 node var.

136
00:06:31,790 --> 00:06:33,110
Bu başqa bir şey yoxdur.

137
00:06:33,110 --> 00:06:36,020
Belə ki, o bütün 10
point göstəricilərinə null.

138
00:06:36,020 --> 00:06:38,090
Ki, qırmızı göstərir budur.

139
00:06:38,090 --> 00:06:39,500
>> Nin simli Harvard daxil edək.

140
00:06:39,500 --> 00:06:41,999
Nin University daxil edək
Bu trie daxil Harvard olan

141
00:06:41,999 --> 00:06:43,940
il 1636-ci ildə yaradılmışdır.

142
00:06:43,940 --> 00:06:48,220
Biz düyməsindən istifadə etmək istəyirsinizsə,
1636, biz olduğunuz bizə

143
00:06:48,220 --> 00:06:50,140
trie Harvard saxlamaq üçün gedir.

144
00:06:50,140 --> 00:06:51,470
İndi ki, necə ola bilər?

145
00:06:51,470 --> 00:06:52,886
>> Bu kimi bir şey ola bilər.

146
00:06:52,886 --> 00:06:54,160
Biz kök başlamaq.

147
00:06:54,160 --> 00:06:56,920
Və biz getmək bilər ki, bu 10 yerləri var.

148
00:06:56,920 --> 00:06:59,900
kök yalnız hər hansı bir kimi
trie digər node.

149
00:06:59,900 --> 00:07:02,850
Biz burada getmək bilər 10 yerlər var.

150
00:07:02,850 --> 00:07:07,215
>> Harada biz yəqin ki, istəyirəm
əsas 1636 əgər getmək?

151
00:07:07,215 --> 00:07:08,340
Həqiqətən iki variantları var.

152
00:07:08,340 --> 00:07:08,450
Right.

153
00:07:08,450 --> 00:07:10,825
Biz əsas inşa edə bilərsiniz
sol və sağ 6 ilə başlamaq üçün.

154
00:07:10,825 --> 00:07:14,000
Yoxsa biz açarı qurmaq bilər
soldan sağa və 1 ilə başlayın.

155
00:07:14,000 --> 00:07:16,140
>> Bu yəqin ki, daha çox
bir insan kimi intuitiv

156
00:07:16,140 --> 00:07:18,110
alacağıq anlamaq
yalnız soldan sağa gedin.

157
00:07:18,110 --> 00:07:21,140
Və mən əlavə etmək istəyirsinizsə,
Bu trie daxil Harvard,

158
00:07:21,140 --> 00:07:23,560
Mən yəqin ki, başlamaq istəyirəm
kök başlayaraq,

159
00:07:23,560 --> 00:07:25,720
mənim 10 variantları axtarır
mənə qarşısında və söyləyərək

160
00:07:25,720 --> 00:07:28,700
I 1 yol aşağı getmək istəyirəm.

161
00:07:28,700 --> 00:07:29,700
OLDU.

162
00:07:29,700 --> 00:07:31,810
>> İndi 1 yol hazırda null edir.

163
00:07:31,810 --> 00:07:35,920
Belə ki, yol aşağı davam etmək istəyirsinizsə,
trie bu element əlavə etmək üçün,

164
00:07:35,920 --> 00:07:42,040
Mən 1 var, yeni node malloc var
orada qeyd və sonra getmək üçün yaxşı deyiləm.

165
00:07:42,040 --> 00:07:46,460
>> Belə ki, əsasən am
point mən duran alıram

166
00:07:46,460 --> 00:07:50,270
ağac və ya kök
trie və 10 filialı var.

167
00:07:50,270 --> 00:07:52,260
Lakin hər bir filial bir
qarşısında qapısı.

168
00:07:52,260 --> 00:07:53,060
Right.

169
00:07:53,060 --> 00:07:54,850
Heç bir şey yoxdur, çünki başqa var.

170
00:07:54,850 --> 00:07:56,522
No təhlükəsiz keçid.

171
00:07:56,522 --> 00:07:58,980
Ki, heç bir şey yoxdur o deməkdir ki,
o istənilən filialına aşağı.

172
00:07:58,980 --> 00:08:02,532
Mən bina başlamaq istəyirsinizsə
bir şey, mən qapısı çıxarmaq istəyirik.

173
00:08:02,532 --> 00:08:04,490
Mən qapısı aradan qaldırılması üçün istədiyiniz
1 nömrəli qarşısında.

174
00:08:04,490 --> 00:08:05,698
Mən ki, aşağı gəzmək istəyirəm.

175
00:08:05,698 --> 00:08:08,060
Mən qurmaq istəyirik
Mənim üçün başqa bir yer getmək üçün.

176
00:08:08,060 --> 00:08:09,470
>> Və mən burada etdik nə var.

177
00:08:09,470 --> 00:08:11,430
Belə ki, 1 artıq bal null üçün.

178
00:08:11,430 --> 00:08:13,830
Mən indi burada enmək təhlükəsiz bildirib etdik.

179
00:08:13,830 --> 00:08:15,789
Başqa bir node inşa edilmişdir.

180
00:08:15,789 --> 00:08:18,330
Mən ki, node almaq zaman, mən
etmək üçün başqa bir qərar var.

181
00:08:18,330 --> 00:08:20,890
Harada buradan getmək üçün gedirəm?

182
00:08:20,890 --> 00:08:22,700
>> Bəli, mən artıq 1 aşağı getdi etdik.

183
00:08:22,700 --> 00:08:24,470
Belə ki, indi mən yəqin ki, 6 aşağı getmək istəyirəm.

184
00:08:24,470 --> 00:08:24,970
Right.

185
00:08:24,970 --> 00:08:27,100
Yenə mən seçə bilərsiniz 10 yerlərdə var.

186
00:08:27,100 --> 00:08:30,060
Belə ki, indi sayı 6 gedək.

187
00:08:30,060 --> 00:08:32,280
Belə ki, qapısı sil
6 nömrəli qarşısında.

188
00:08:32,280 --> 00:08:33,250
Mən orada gəzmək.

189
00:08:33,250 --> 00:08:34,580
Mən başqa bir node qurmaq.

190
00:08:34,580 --> 00:08:37,630
Mən bir qovşaq nöqtəsi əldə etdik.

191
00:08:37,630 --> 00:08:40,289
>> Yenə 10 seçim var
Mən getmək bilər harada.

192
00:08:40,289 --> 00:08:42,799
Mən 1-dən 6-hərəkət etdik.

193
00:08:42,799 --> 00:08:44,215
Belə ki, indi mən yəqin ki, 3 getmək istəyirəm.

194
00:08:44,215 --> 00:08:45,381
3, heç bir yerdə mən getmək bilər var.

195
00:08:45,381 --> 00:08:48,980
Belə ki, yol açmaq lazımdır
və özümü yeni bir yer yaratmaq.

196
00:08:48,980 --> 00:08:50,870
Və sonra mən getmək istəyirəm 3 olan?

197
00:08:50,870 --> 00:08:52,450
Mən aşağı 6 getmək istəyirəm.

198
00:08:52,450 --> 00:08:54,770
>> Və yenə, mən idi
bunu yol açmaq.

199
00:08:54,770 --> 00:08:59,179
Belə ki, indi yaratmaq daxil mənim düyməsini istifadə etdiyiniz
qovşaqlarının bu trie qurmaq başlamaq və.

200
00:08:59,179 --> 00:09:00,220
Mən kök açılmış etdik.

201
00:09:00,220 --> 00:09:03,666
Mən 1636-cı aşağı getdi etdik.

202
00:09:03,666 --> 00:09:05,540
İndi altındakı deyiləm
orada node.

203
00:09:05,540 --> 00:09:06,610
Və edə bilər
ekranda görürük.

204
00:09:06,610 --> 00:09:07,735
>> Bu sarı qeyd edir.

205
00:09:07,735 --> 00:09:10,020
Hal-hazırda am harada.

206
00:09:10,020 --> 00:09:11,300
Mənim əsas edilir.

207
00:09:11,300 --> 00:09:13,030
Mən əsas hər mövqe canı etdik.

208
00:09:13,030 --> 00:09:15,040
Belə ki, hər hansı bir daha getmək bilməz.

209
00:09:15,040 --> 00:09:17,720
Bu nöqtədə, bütün Mən
həqiqətən OK, demək nə etmək lazımdır.

210
00:09:17,720 --> 00:09:18,990
Bu cür axtarır kimi
torpaq aşağı,

211
00:09:18,990 --> 00:09:21,115
Siz nəzərdə tutan edirsinizsə
Özünüz yolun bu növ kimi

212
00:09:21,115 --> 00:09:22,350
müxtəlif əlaqələri ilə.

213
00:09:22,350 --> 00:09:25,800
Sort aşağı və sort axtarır
yerdə Harvard rəsm sprey.

214
00:09:25,800 --> 00:09:26,800
Yəni bu adı var.

215
00:09:26,800 --> 00:09:28,300
Bu yerdə nə bilirik.

216
00:09:28,300 --> 00:09:31,870
Biz kök başlamaq və biz aşağı getmək əgər
1 və sonra 6 və sonra 3 və sonra 6

217
00:09:31,870 --> 00:09:32,780
Biz harada var?

218
00:09:32,780 --> 00:09:35,640
Yaxşı aşağı baxmaq əgər
və biz sonra, Harvard görmək

219
00:09:35,640 --> 00:09:38,960
biz Harvard olduğunu bilirik
yolu əsasında 1636-ci ildə yaradılmışdır

220
00:09:38,960 --> 00:09:41,400
bu data strukturu həyata edirik.

221
00:09:41,400 --> 00:09:43,177
Belə ki, inşallah sadə idi.

222
00:09:43,177 --> 00:09:44,760
Biz daha iki insertions nə olacaq.

223
00:09:44,760 --> 00:09:50,060
Və ümid edirəm ki, kömək lazımdır
çox bu iki dəfə daha çox işlər.

224
00:09:50,060 --> 00:09:52,210
>> İndi bir universitet daxil edək.

225
00:09:52,210 --> 00:09:54,630
Bu trie daxil Yale daxil edək.

226
00:09:54,630 --> 00:09:57,037
Yale 1701-ci ildə yaradılmışdır.

227
00:09:57,037 --> 00:09:58,870
Belə ki, biz başlamaq lazımdır
kök, biz həmişə nə kimi.

228
00:09:58,870 --> 00:09:59,890
Və biz bir traversal göstərici seçin.

229
00:09:59,890 --> 00:10:01,624
Biz vasitəsilə hərəkət etmək üçün istifadə olacaq.

230
00:10:01,624 --> 00:10:03,790
biz istədiyiniz ilk şey
Bunu 1 yoluna getmək edir.

231
00:10:03,790 --> 00:10:05,830
Yəni bizim əsas ilk rəqəmli var.

232
00:10:05,830 --> 00:10:08,420
Xoşbəxtlikdən, baxmayaraq ki, biz deyil
hər hansı bir iş bu dəfə var.

233
00:10:08,420 --> 00:10:09,919
1 yol artıq təmizləndi.

234
00:10:09,919 --> 00:10:13,520
Mən əvvəllər mən bunu ili
1636-da Harvard daxil edilib.

235
00:10:13,520 --> 00:10:18,090
Belə ki, təhlükəsiz hərəkət edə bilər
1 aşağı və yalnız orada getmək.

236
00:10:18,090 --> 00:10:20,150
1 aşağı hərəkət edə bilər.

237
00:10:20,150 --> 00:10:22,930
>> İndi baxmayaraq ki, mən 7 getmək istəyirəm.

238
00:10:22,930 --> 00:10:24,280
Mən 6 yol təmizlənib.

239
00:10:24,280 --> 00:10:27,050
Mən təhlükəsiz bilirik
6 yol aşağı davam etdirilir.

240
00:10:27,050 --> 00:10:29,220
Amma 7 yoluna davam etmək lazımdır.

241
00:10:29,220 --> 00:10:30,580
Belə ki, nə mən nə etmək lazımdır?

242
00:10:30,580 --> 00:10:35,070
Bəli, yalnız əvvəl kimi, yalnız lazımdır
qapısı təmizləmək üçün yol həyata almaq,

243
00:10:35,070 --> 00:10:38,740
7 yolundan yeni node qurmaq.

244
00:10:38,740 --> 00:10:40,250
Məhz bu kimi.

245
00:10:40,250 --> 00:10:42,930
>> Belə ki, indi 1 və sonra 7 hərəkət etdik.

246
00:10:42,930 --> 00:10:45,550
İndi qeyd mən sort edirəm
bu yeni şöbəsi var.

247
00:10:45,550 --> 00:10:46,050
Right.

248
00:10:46,050 --> 00:10:49,260
16 başqa hər şey
, Mən qayğı yoxdur.

249
00:10:49,260 --> 00:10:50,720
Mən 16 bir şey bunu deyiləm.

250
00:10:50,720 --> 00:10:51,750
Mən 17 stuff edirəm.

251
00:10:51,750 --> 00:10:58,380
>> Belə ki, indi 17-dən, mən var
sort burada yeni yolları etmek.

252
00:10:58,380 --> 00:11:00,462
növbəti rəqəmli mənim əsas 0.

253
00:11:00,462 --> 00:11:01,670
Mən aydın yerdə əldə edə bilməz.

254
00:11:01,670 --> 00:11:02,628
Mən yalnız bu node inşa edilmişdir.

255
00:11:02,628 --> 00:11:04,550
Belə ki, mən heç bir var bilirəm
irəli buradan yolları.

256
00:11:04,550 --> 00:11:06,370
Mən bir özüm etmək lazımdır.

257
00:11:06,370 --> 00:11:09,360
>> Belə ki, yeni node malloc
və orada 0 nöqtə var.

258
00:11:09,360 --> 00:11:12,770
Və sonra bir dəfə daha, mən malloc bir
yeni node və orada bir nöqtə var.

259
00:11:12,770 --> 00:11:15,870
Yenə Mən düyməsi, 1701 canı etdik.

260
00:11:15,870 --> 00:11:18,472
Beləliklə, mən aşağı baxmaq və mən Yale boya sprey.

261
00:11:18,472 --> 00:11:19,680
Yəni, bu node adı var.

262
00:11:19,680 --> 00:11:24,660
>> Və indi mən heç Yale görmek lazımdır
bu trie, mən kök başlamaq,

263
00:11:24,660 --> 00:11:27,060
Mən 1701-aşağı getmək və aşağı baxmaq.

264
00:11:27,060 --> 00:11:30,030
Mən Yale sprey görürsünüzsə
sonra ortalığa boyalı

265
00:11:30,030 --> 00:11:32,200
Mən Yale bu trie mövcuddur bilirik.

266
00:11:32,200 --> 00:11:32,950
Daha bir nə edək.

267
00:11:32,950 --> 00:11:36,430
Bu daxil Dartmouth daxil edək
1769-ci ildə təsis edilib trie.

268
00:11:36,430 --> 00:11:37,750
>> Daha kök başlamaq.

269
00:11:37,750 --> 00:11:39,445
Mənim əsas mənim ilk rəqəmli 1.

270
00:11:39,445 --> 00:11:40,820
Mən təhlükəsiz ki, yolunu aşağı hərəkət edə bilər.

271
00:11:40,820 --> 00:11:42,400
Artıq mövcuddur.

272
00:11:42,400 --> 00:11:44,040
Mənim əsas növbəti rəqəmli 7.

273
00:11:44,040 --> 00:11:45,890
Mən təhlükəsiz ki, yolunu aşağı hərəkət edə bilər.

274
00:11:45,890 --> 00:11:47,540
Bu həmçinin mövcuddur.

275
00:11:47,540 --> 00:11:49,000
>> Növbəti 6.

276
00:11:49,000 --> 00:11:52,860
Burada, Hal-hazırda am yerdən
ki, orta node var sarı,

277
00:11:52,860 --> 00:11:56,060
6 Hal-hazırda off kilidlənib.

278
00:11:56,060 --> 00:11:58,830
Hesab edirəm ki, yol aşağı getmək istəyirsinizsə,
Mən özüm qurmaq lazımdır.

279
00:11:58,830 --> 00:12:02,250
Belə ki, yeni node malloc lazımdır
və orada 6 nöqtə var.

280
00:12:02,250 --> 00:12:04,250
Və sonra, yenə, mən deyiləm
Burada yeni yolları alovlu.

281
00:12:04,250 --> 00:12:10,750
>> Belə ki, yeni node malloc ki, belə
İndi o node yol sayı 9 olan və

282
00:12:10,750 --> 00:12:13,584
Mən 1769 səyahət və mən aşağı baxmaq əgər.

283
00:12:13,584 --> 00:12:15,500
Heç bir şey Hal-hazırda yoxdur
orada boyalı sprey.

284
00:12:15,500 --> 00:12:16,930
Mən Dartmouth yaza bilərsiniz.

285
00:12:16,930 --> 00:12:20,710
Mən daxil etdik
Trie daxil DARTMOUTH.

286
00:12:20,710 --> 00:12:23,450
>> Belə ki, daxil deyil
trie daxil şeylər.

287
00:12:23,450 --> 00:12:25,384
İndi biz şey üçün axtarış etmək istəyirəm.

288
00:12:25,384 --> 00:12:27,050
Necə ki, biz trie şey üçün axtarış edirsiniz?

289
00:12:27,050 --> 00:12:29,170
Bəli, bu, olduqca çox eyni fikirdir.

290
00:12:29,170 --> 00:12:33,620
İndi biz yalnız əsas rəqəm istifadə
biz kök getmək bilər görmek üçün

291
00:12:33,620 --> 00:12:37,170
biz trie getmək istədiyiniz üçün.

292
00:12:37,170 --> 00:12:41,620
>> Biz sonra, hər hansı bir anda bir ölü son edib
ki, element mövcud deyil bilər ki, bilirik

293
00:12:41,620 --> 00:12:44,500
və ya başqa yol olardı
artıq təmizlənib.

294
00:12:44,500 --> 00:12:45,930
Biz bütün yol etmək əgər
sonunda, bütün biz nə etmək lazımdır

295
00:12:45,930 --> 00:12:48,471
aşağı baxmaq və əgər görmək
biz aradığınız element.

296
00:12:48,471 --> 00:12:49,335
Bu, uğur deyil.

297
00:12:49,335 --> 00:12:52,610
Bu deyil, uğursuz.

298
00:12:52,610 --> 00:12:54,940
>> Belə ki, üçün axtarış imkan
Bu trie Harvard.

299
00:12:54,940 --> 00:12:56,020
Biz kök başlamaq.

300
00:12:56,020 --> 00:12:58,228
Və yenə biz olacaq
bir traversal pointer yaratmaq

301
00:12:58,228 --> 00:12:59,390
bizim üçün hərəkət etmək üçün.

302
00:12:59,390 --> 00:13:02,080
Kök biz bilirik ki,
biz getmək lazımdır ilk yer, 1

303
00:13:02,080 --> 00:13:03,390
biz bunu edə bilər?

304
00:13:03,390 --> 00:13:03,982
Bəli, biz bilərsiniz.

305
00:13:03,982 --> 00:13:04,690
Əgər təhlükəsiz mövcuddur.

306
00:13:04,690 --> 00:13:06,660
Biz orada getmək bilər.

307
00:13:06,660 --> 00:13:08,440
>> İndi biz getmək lazımdır növbəti yer 6.

308
00:13:08,440 --> 00:13:10,557
6 yolu buradan varmı?

309
00:13:10,557 --> 00:13:11,140
Bəli, bu yoxdur.

310
00:13:11,140 --> 00:13:12,690
Biz 6 yol aşağı bilərsiniz.

311
00:13:12,690 --> 00:13:13,905
Və biz burada son.

312
00:13:13,905 --> 00:13:16,130
>> Biz burada 3 yol aşağı getmək olar?

313
00:13:16,130 --> 00:13:18,450
Bəli, bu çıxır kimi,
Bəli, çox var.

314
00:13:18,450 --> 00:13:20,790
Və biz burada 6 yolda əldə edə bilərsiniz?

315
00:13:20,790 --> 00:13:21,982
Bəli, biz bilərsiniz.

316
00:13:21,982 --> 00:13:24,002
>> Biz kifayət qədər cavab yoxdur
hələ sual.

317
00:13:24,002 --> 00:13:25,710
Bir daha hələ var
İndi addım,

318
00:13:25,710 --> 00:13:28,520
Biz aşağı baxmaq lazımdır və
ki, həqiqətən görmek

319
00:13:28,520 --> 00:13:32,660
biz Harvard arıyorsanız, ki,
biz əsas girinc sonra biz nə tapmaq?

320
00:13:32,660 --> 00:13:35,430
Məsələn, biz burada istifadə etdiyiniz,
il həmişə dörd rəqəm var.

321
00:13:35,430 --> 00:13:40,280
Amma nümunə harada istifadə edilə bilər
Siz sözləri lüğət saxlanılması olunur.

322
00:13:40,280 --> 00:13:44,060
>> Və belə əvəzinə 10 göstəricilərinə malik olan
Mənim yeri üçün, 26 ola bilər.

323
00:13:44,060 --> 00:13:46,040
Əlifba hər bir hərf üçün bir.

324
00:13:46,040 --> 00:13:50,350
Və yarasa kimi bəzi sözlər var,
olan məsələn partiyasının alt edir.

325
00:13:50,350 --> 00:13:53,511
Və almaq belə olsa
əsas sonu və aşağı baxmaq,

326
00:13:53,511 --> 00:13:55,260
Siz nə görmək bilər
Aradığınız.

327
00:13:55,260 --> 00:13:58,500
>> Belə ki, həmişə axır var
Bütün yol və sonra

328
00:13:58,500 --> 00:14:01,540
Uğurla edə olsaydı
bütün yol axır,

329
00:14:01,540 --> 00:14:03,440
aşağı baxmaq və bir final təsdiq yoxdur.

330
00:14:03,440 --> 00:14:05,120
Mən arıyorum nədir?

331
00:14:05,120 --> 00:14:07,740
Bəli, mən başlayaraq sonra aşağı baxmaq
üst və 1636 gedir.

332
00:14:07,740 --> 00:14:08,240
Mən aşağı baxmaq.

333
00:14:08,240 --> 00:14:09,400
Mən Harvard görürük.

334
00:14:09,400 --> 00:14:11,689
Belə ki, bəli, mən oldu.

335
00:14:11,689 --> 00:14:13,980
Nə nə mən arıyorum
baxmayaraq ki, trie deyil.

336
00:14:13,980 --> 00:14:17,200
Mən Princeton arıyorum nə varsa,
olan 1746-ci ildə yaradılmışdır.

337
00:14:17,200 --> 00:14:20,875
Və belə 1746 mənim əsas olur
trie gezinmek üçün.

338
00:14:20,875 --> 00:14:22,040
Yaxşı, mən kök başlamaq.

339
00:14:22,040 --> 00:14:24,760
Mən istəyirəm ilk yer
1 yol aşağı gedir.

340
00:14:24,760 --> 00:14:25,590
Mən bunu edə bilər?

341
00:14:25,590 --> 00:14:26,490
Bəli, edə bilərsiniz.

342
00:14:26,490 --> 00:14:28,730
>> Mən 7 yol aşağı getmək olar?

343
00:14:28,730 --> 00:14:29,230
Bəli, mən.

344
00:14:29,230 --> 00:14:30,750
Bu çox mövcuddur.

345
00:14:30,750 --> 00:14:32,460
Amma buradan 4 yol aşağı getmək olar?

346
00:14:32,460 --> 00:14:35,550
Bu bilərsiniz, sual kimi
Mən kiçik kvadrat ki, aşağı davam

347
00:14:35,550 --> 00:14:37,114
Mən sarı qeyd etdik?

348
00:14:37,114 --> 00:14:38,030
Heç bir şey yoxdur.

349
00:14:38,030 --> 00:14:38,610
Right.

350
00:14:38,610 --> 00:14:41,310
>> Heç bir yol irəli 4 yol aşağı var.

351
00:14:41,310 --> 00:14:46,480
Princeton, bu trie idi 4 ki, əgər
artıq bizim üçün tip olardı.

352
00:14:46,480 --> 00:14:49,130
Və bu nöqtədə
biz bir ölü sonunda əldə etdiyiniz.

353
00:14:49,130 --> 00:14:50,250
Biz bundan sonra da hər hansı bir getmək bilməz.

354
00:14:50,250 --> 00:14:53,440
Və belə ki, biz heç bir qəti demək olar.

355
00:14:53,440 --> 00:14:56,760
Princeton bu trie yoxdur.

356
00:14:56,760 --> 00:14:58,860
>> Belə ki, bu bütün nə deməkdir?

357
00:14:58,860 --> 00:14:59,360
Right.

358
00:14:59,360 --> 00:15:01,000
Burada gedən bir çox var.

359
00:15:01,000 --> 00:15:02,500
Bütün yer üzərində göstəricilər var.

360
00:15:02,500 --> 00:15:04,249
Və kimi görə bilərsiniz
yalnız diagram

361
00:15:04,249 --> 00:15:07,010
qovşaqlarının bir çox var ki,
növ ətrafında uçan olunur.

362
00:15:07,010 --> 00:15:13,480
Amma biz istəyirdi hər zaman hiss
bir şey trie olub-olmadığını yoxlamaq,

363
00:15:13,480 --> 00:15:15,000
biz yalnız 4 hərəkət etmək idi.

364
00:15:15,000 --> 00:15:17,208
>> Biz istəyirdi hər dəfə
trie bir şey daxil,

365
00:15:17,208 --> 00:15:20,440
biz bəlkə, 4 hərəkət etmək lazımdır
yol boyunca bəzi məhsulları mallocing.

366
00:15:20,440 --> 00:15:23,482
Biz daxil zaman gördük kimi
Trie daxil Dartmouth,

367
00:15:23,482 --> 00:15:25,940
bəzən yolun bəzi
artıq bizim üçün rəsmiləşdirilməyib bilər.

368
00:15:25,940 --> 00:15:30,520
Və belə ki, bizim trie olur kimi böyük və
böyük, daha az iş hər zaman var

369
00:15:30,520 --> 00:15:32,270
yeni şeylər əlavə etmək
biz artıq var, çünki

370
00:15:32,270 --> 00:15:35,746
aralıq bir çox inşa
yol boyunca filialları.

371
00:15:35,746 --> 00:15:38,370
Biz yalnız heç baxmaq varsa,
4 şeyi, 4 yalnız daimi deyil.

372
00:15:38,370 --> 00:15:41,750
Biz, həqiqətən, cür yaxınlaşan
daimi vaxt durub

373
00:15:41,750 --> 00:15:44,501
və daimi vaxt Sistemi.

374
00:15:44,501 --> 00:15:47,500
tradeoff, əlbəttə, ki, olan
bu trie kimi yəqin ki, deyə bilərsiniz

375
00:15:47,500 --> 00:15:49,030
böyükdür.

376
00:15:49,030 --> 00:15:51,040
Bu qovşaqlarının hər biri
kosmik bir çox çəkir.

377
00:15:51,040 --> 00:15:52,090
>> Amma ki, tradeoff var.

378
00:15:52,090 --> 00:15:55,260
Biz, həqiqətən, sürətli istəyirsinizsə
durub, həqiqətən sürətli silinməsi,

379
00:15:55,260 --> 00:15:59,630
və həqiqətən sürətli axtarış, biz var
bir çox veri ətrafında uçan var.

380
00:15:59,630 --> 00:16:03,590
Biz kosmik bir çox kənara var
ki, data strukturu üçün yaddaş

381
00:16:03,590 --> 00:16:04,290
mövcud.

382
00:16:04,290 --> 00:16:05,415
>> Və belə ki, tradeoff var.

383
00:16:05,415 --> 00:16:07,310
Lakin biz kimi görünür
aşkar ola bilər.

384
00:16:07,310 --> 00:16:09,560
Biz gördük bilər
data strukturları müqəddəs grail

385
00:16:09,560 --> 00:16:12,264
tez durub ilə,
silinməsi, və axtarış.

386
00:16:12,264 --> 00:16:14,430
Və bəlkə bu olacaq
müvafiq data structure

387
00:16:14,430 --> 00:16:18,890
nə məlumat üçün istifadə
biz mağaza çalışırıq.

388
00:16:18,890 --> 00:16:21,860
Mən Doug Lloyd deyiləm, bu CS50 edir.

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