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
Даг LLOYD: Значи ние сме во чекор поблизу
и поблиску дека светиот грал на податоци

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
знае дали тие податоци
постојат во 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
случува да се Примерок 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
ќе се постави уште еден покажувач
еднаква на корен, како што се 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 за traversal.

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 јазол во оваа 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
Морам да Примерок нов јазол, 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
Па во овој момент, се што можам
навистина треба да направите е да се каже, во ред.

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
И ние се постави traversal покажувачот.

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
>> Па јас Примерок нов јазол
и 0 точка таму.

258
00:11:09,360 --> 00:11:12,770
А потоа уште еднаш, јас Примерок на
нов јазол и да имаат една точка таму.

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
Одам долу 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
Па јас ќе Примерок нов јазол
и имаат 6 точка таму.

280
00:12:02,250 --> 00:12:04,250
А потоа, повторно, јас сум
пламнал нови патеки тука.

281
00:12:04,250 --> 00:12:10,750
>> Па јас Примерок нов јазол, така што од
дека 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
И, повторно, ние ќе треба да
создаде traversal покажувачот

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
Па, јас се погледне надолу по започнувањето
на врвот и ќе 1.636.

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