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
Jel tako.

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
да хасхес том хасхЦоде.

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

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
има исти хасхЦоде.

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
да себи маллоц трие чвор.

122
00:05:57,580 --> 00:05:59,850
И ти никад нећеш
на додир корен поново.

123
00:05:59,850 --> 00:06:02,300
Сваки пут када желите да
почнете са навигацијом кроз,

124
00:06:02,300 --> 00:06:05,802
не поставите други показивач
једнако корену, као што су Трав,

125
00:06:05,802 --> 00:06:07,760
што је пример ја
користе у многим од мојих видеа

126
00:06:07,760 --> 00:06:11,090
овде на гомиле и редовима
и линк листе и тако даље.

127
00:06:11,090 --> 00:06:13,320
>> Ви сет други показивач
позвао трав за Траверсал.

128
00:06:13,320 --> 00:06:15,890
И користите Трав за навигацију
кроз структуру података.

129
00:06:15,890 --> 00:06:17,500
Дакле, хајде да видимо како то може да изгледа.

130
00:06:17,500 --> 00:06:19,880
Тако сада, шта
не чвор изгледа?

131
00:06:19,880 --> 00:06:22,920
Па, баш као нашим подацима
Структура декларација наведено,

132
00:06:22,920 --> 00:06:26,906
имамо стринг, који
у овом случају је празна.

133
00:06:26,906 --> 00:06:27,780
Овде нема ничега.

134
00:06:27,780 --> 00:06:29,550
>> И низ од 10 показивача.

135
00:06:29,550 --> 00:06:31,790
И управо сада, само ми
Имам 1 чвор у овом Трие.

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
Jel tako.

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
Морам да маллоц нови чвор, имају 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
Jel tako.

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
Jel tako.

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
Дакле, у овом тренутку, ја
Стварно треба да урадите је да кажем, у реду.

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
И сада приметио, некако сам
од на овом новом суббранцх.

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

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
>> И сада ако икада треба да видимо да ли Иале
је у овом Трие, почнем у корену,

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
Зато ћу маллоц нови чвор
и има 6 праву.

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

281
00:12:04,250 --> 00:12:10,750
>> Тако сам Маллоц нови чвор, тако да од
да ноде-- број пут 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
морамо да погледа доле и
видим да ли је то стварно--

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
Jel tako.

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
Jel tako.

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 потезе, евентуално
маллоцинг неке ствари успут.

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
da postoji.

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
Ја сам Доуг Ллоид, ово је ЦС50.

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