1
00:00:00,000 --> 00:00:02,994
>> [MUZYKI]

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

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Więc byliśmy inching bliżej
i bliżej, że Święty Graal danych

4
00:00:08,550 --> 00:00:13,050
struktury, który można włożyć
się, usunąć z, i spójrz w górę

5
00:00:13,050 --> 00:00:15,440
w stałym czasie.

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

7
00:00:16,270 --> 00:00:17,280
To swego rodzaju siatkę.

8
00:00:17,280 --> 00:00:19,720
Chcemy być w stanie zrobić
rzeczy bardzo, bardzo szybko.

9
00:00:19,720 --> 00:00:22,580
>> Mają znaleźliśmy go tutaj, kiedy
mówimy o próbach?

10
00:00:22,580 --> 00:00:23,670
Cóż, rzućmy okiem.

11
00:00:23,670 --> 00:00:25,628
Tak więc widzieliśmy kilka
różne struktury danych

12
00:00:25,628 --> 00:00:28,680
które obsługuje mapowanie
tzw pary klucz-wartość,

13
00:00:28,680 --> 00:00:32,080
mapowanie jakiś kawałek danych
do innej części danych

14
00:00:32,080 --> 00:00:36,020
więc wiemy, gdzie znaleźć
Informacje zawarte w strukturze.

15
00:00:36,020 --> 00:00:40,060
>> Tak na tablicy, na przykład,
Kluczowym elementem jest wskaźnik lub tablica

16
00:00:40,060 --> 00:00:42,600
Położenie 0 lub tablica 1 i tak dalej.

17
00:00:42,600 --> 00:00:46,140
A wartość jest dane
że istnieje w tym miejscu.

18
00:00:46,140 --> 00:00:48,550
Więc co jest przechowywane w tablicy 0?

19
00:00:48,550 --> 00:00:54,290
Jakie są przechowywane w tablicy 1, w porównaniu z zaledwie
0 i 1, co byłoby klucze.

20
00:00:54,290 --> 00:00:56,360
>> Z tabeli mieszania to
rodzaj tej samej idei.

21
00:00:56,360 --> 00:01:00,690
Z tabeli mieszania, mamy ten hash
funkcja, która generuje kody hash.

22
00:01:00,690 --> 00:01:03,670
Tak więc kluczem jest kod skrótu danych.

23
00:01:03,670 --> 00:01:06,530
I wartość, w szczególności
rozmawialiśmy o łańcuchowym

24
00:01:06,530 --> 00:01:10,590
w wideo na stołach z cebulą,
jest to, że wiąże lista danych

25
00:01:10,590 --> 00:01:12,550
że skróty do tej hashcode.

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

27
00:01:14,050 --> 00:01:16,050
Co innego podejścia
Ten sposób, chociaż?

28
00:01:16,050 --> 00:01:21,000
Co do sposobu, w którym
Kluczem jest gwarantowane jest unikatowy,

29
00:01:21,000 --> 00:01:25,410
w przeciwieństwie do tabeli mieszania, gdzie moglibyśmy
kończy się z dwóch części danych

30
00:01:25,410 --> 00:01:27,200
o tej samej hashcode.

31
00:01:27,200 --> 00:01:30,020
I wtedy mamy do czynienia z
że albo sondowania lub więcej

32
00:01:30,020 --> 00:01:33,340
najlepiej łączenia naprawić ten problem.

33
00:01:33,340 --> 00:01:37,520
>> Więc teraz możemy zagwarantować
że nasz klucz będzie wyjątkowy.

34
00:01:37,520 --> 00:01:39,690
A co, jeśli nasza wartość była
tylko coś tak proste

35
00:01:39,690 --> 00:01:44,080
jak prawda i fałsz, który mówi nam, czy
czy nie, że informacja

36
00:01:44,080 --> 00:01:45,610
występuje w strukturze?

37
00:01:45,610 --> 00:01:48,180
Boolean może być tak proste, jak się trochę.

38
00:01:48,180 --> 00:01:52,660
Realistycznie to chyba
bajt bardziej prawdopodobne niż trochę.

39
00:01:52,660 --> 00:01:55,410
Ale to o wiele mniejsze niż
przechowywania może ciąg 50 znaków,

40
00:01:55,410 --> 00:01:57,360
na przykład.

41
00:01:57,360 --> 00:02:02,210
>> Tak stara, podobna do mieszania tabele,
które łączą tablice i związane lista,

42
00:02:02,210 --> 00:02:05,790
próbuje połączyć tablice,
struktury, i wskaźniki

43
00:02:05,790 --> 00:02:08,509
razem przechowuje dane
ciekawy sposób to

44
00:02:08,509 --> 00:02:11,550
całkiem inny od
coś widzieliśmy do tej pory.

45
00:02:11,550 --> 00:02:16,750
Teraz możemy korzystać z danych w mapie drogowej
aby poruszać tę strukturę danych.

46
00:02:16,750 --> 00:02:18,710
A jeśli możemy śledzić
plan działania, jeśli to możliwe

47
00:02:18,710 --> 00:02:22,390
postępuj według danych z
początku do końca, będziemy

48
00:02:22,390 --> 00:02:24,945
wiedzieć, czy te dane
istnieć w trie.

49
00:02:24,945 --> 00:02:28,310
>> A jeśli nie możemy śledzić mapę
od co oznacza do końca w ogóle,

50
00:02:28,310 --> 00:02:30,600
dane nie mogą istnieć.

51
00:02:30,600 --> 00:02:32,890
Ponownie, klucze tutaj
muszą być unikalne.

52
00:02:32,890 --> 00:02:36,020
I tak, w przeciwieństwie do tabeli mieszania, że ​​nigdy nie będziesz
mamy do czynienia z kolizji tutaj.

53
00:02:36,020 --> 00:02:39,090
I nie ma dwóch fragmentów danych
mają dokładnie tę samą mapę drogową

54
00:02:39,090 --> 00:02:40,530
chyba, że ​​dane są identyczne.

55
00:02:40,530 --> 00:02:44,580
>> Jeśli wstawiamy Jana, a następnie
szukamy Jana.

56
00:02:44,580 --> 00:02:47,430
To dwa identyczne kawałki
Dane, w prawo, my patrząc przez.

57
00:02:47,430 --> 00:02:49,880
Ale w inny sposób,
dwa kawałki danych są

58
00:02:49,880 --> 00:02:52,750
na pewno mają unikalne mapy drogowe
przez tę strukturę danych.

59
00:02:52,750 --> 00:02:56,210
I mamy zamiar przyjrzeć się
wizualny tego za chwilę.

60
00:02:56,210 --> 00:02:58,810
>> Zrobimy to, starając się
utworzenie nowej struktury,

61
00:02:58,810 --> 00:03:00,564
mapowanie następujące pary wartość klucza.

62
00:03:00,564 --> 00:03:03,480
W tym przypadku nie będziemy korzystać
coś tak prostego jak Boolean.

63
00:03:03,480 --> 00:03:06,200
My rzeczywiście będzie przechowywać ciąg.

64
00:03:06,200 --> 00:03:08,690
I że ciąg będzie
być nazwa uczelni.

65
00:03:08,690 --> 00:03:12,140
>> Oraz kluczowy będzie rok
gdy uniwersytet został założony.

66
00:03:12,140 --> 00:03:15,380
Wszystkie lata na uczelni
będą cztery cyfry.

67
00:03:15,380 --> 00:03:19,840
I tak będziemy korzystać z tych czterech cyfr do
poruszać się w tej strukturze danych.

68
00:03:19,840 --> 00:03:22,270
I zobaczymy, znowu, jak
my, że w ciągu sekundy.

69
00:03:22,270 --> 00:03:25,110
>> Na koniec drogi,
zobaczymy nazwę

70
00:03:25,110 --> 00:03:30,250
uczelni, który odpowiada
do tego klawisza, te cztery cyfry.

71
00:03:30,250 --> 00:03:34,390
Podstawową ideą jest trie
to mamy główną trasą.

72
00:03:34,390 --> 00:03:35,640
Więc pomyśl o tym jak drzewo.

73
00:03:35,640 --> 00:03:39,211
I to jest podobne w pisowni
i koncepcji do drzewa.

74
00:03:39,211 --> 00:03:41,460
Generalnie, kiedy myślimy o
drzewa w świecie rzeczywistym,

75
00:03:41,460 --> 00:03:44,090
mają korzeń, który jest w
ziemi i rosną w górę

76
00:03:44,090 --> 00:03:46,830
i mają oddziały
i mają liści.

77
00:03:46,830 --> 00:03:49,450
I w zasadzie idea
trie jest dokładnie taka sama,

78
00:03:49,450 --> 00:03:51,755
oprócz tego, że korzeń jest zakotwiczony
gdzieś w niebie.

79
00:03:51,755 --> 00:03:53,130
I pozostawia się na dole.

80
00:03:53,130 --> 00:03:55,750
>> Więc to jest trochę jak przy drzewo
i po prostu przerzucanie go do góry nogami.

81
00:03:55,750 --> 00:03:56,880
Ale nadal istnieją oddziały.

82
00:03:56,880 --> 00:03:59,463
A ci, byłoby nasze drogi,
będą to nasze połączenia

83
00:03:59,463 --> 00:04:02,220
od korzenia do liści.

84
00:04:02,220 --> 00:04:04,200
W tym przypadku te
ścieżki, te gałęzie

85
00:04:04,200 --> 00:04:08,490
oznaczone są cyframi, które mówią nam
w którą stronę iść, skąd jesteśmy.

86
00:04:08,490 --> 00:04:11,800
>> Jeśli widzimy 0, idziemy w dół tej branży,
jeśli widzimy 1, idziemy w dół tej branży,

87
00:04:11,800 --> 00:04:12,900
i tak i tak dalej.

88
00:04:12,900 --> 00:04:14,060
Cóż, co to oznacza?

89
00:04:14,060 --> 00:04:16,519
Cóż, to oznacza, że
w każdym punkcie połączenia

90
00:04:16,519 --> 00:04:19,260
i każdy węzeł w
średniej i każdy oddział,

91
00:04:19,260 --> 00:04:23,020
istnieją 10 możliwe
miejsca, że ​​możemy iść.

92
00:04:23,020 --> 00:04:27,690
Więc istnieje 10 wskazówek
z każdego miejsca.

93
00:04:27,690 --> 00:04:30,610
>> I to jest, gdy próbuje mogą uzyskać
trochę skomplikowane dla kogoś

94
00:04:30,610 --> 00:04:34,460
kto nie ma dużo
doświadczenie w dziedzinie informatyki wcześniej.

95
00:04:34,460 --> 00:04:35,960
Ale próbuje są naprawdę dość niesamowite.

96
00:04:35,960 --> 00:04:37,793
A jeśli masz
możliwość pracy z nimi

97
00:04:37,793 --> 00:04:40,420
i jesteś w stanie kopać w
i eksperymentować z nimi,

98
00:04:40,420 --> 00:04:44,234
są naprawdę bardzo interesujące
struktury danych do pracy.

99
00:04:44,234 --> 00:04:46,900
Jeśli chcemy, aby wstawić element
do trie, wszystko musimy zrobić

100
00:04:46,900 --> 00:04:51,360
jest zbudować poprawną ścieżkę
od korzenia do liścia.

101
00:04:51,360 --> 00:04:55,390
Oto, co na każdym kroku wraz
sposób może wyglądać.

102
00:04:55,390 --> 00:04:59,660
Jedziemy do zdefiniowania nowego dane
Struktura nowego węzła nazywany TRIE.

103
00:04:59,660 --> 00:05:02,560
>> I wewnątrz tych danych
Struktura są dwa kawałki.

104
00:05:02,560 --> 00:05:05,460
Mamy zamiar przechowywać
nazwa uczelni.

105
00:05:05,460 --> 00:05:09,410
I mamy zamiar przechowywać
tablica wskaźników

106
00:05:09,410 --> 00:05:12,190
do innych węzłów o tym samym rodzaju.

107
00:05:12,190 --> 00:05:14,780
Tak, znowu, jest to ten rodzaj
od koncepcji wszędzie

108
00:05:14,780 --> 00:05:18,567
jesteśmy, na 10 możliwe
miejsca możemy iść.

109
00:05:18,567 --> 00:05:20,150
Jeśli widzimy 0, idziemy w dół tę gałąź.

110
00:05:20,150 --> 00:05:22,690
Jeśli widzimy 1, ta gałąź,
i tak dalej, i tak dalej, i tak dalej.

111
00:05:22,690 --> 00:05:25,160
Jeśli mówimy, 9, idziemy w dół tę gałąź.

112
00:05:25,160 --> 00:05:28,220
Tak więc w każdym punkcie skrzyżowania,
możemy iść 10 możliwych miejsc.

113
00:05:28,220 --> 00:05:35,740
Więc każdy węzeł musi zawierać 10 wskazówek
do innych węzłów, do 10 innych węzłów.

114
00:05:35,740 --> 00:05:39,810
>> I przechowywania danych mamy jest
tylko nazwa uczelni.

115
00:05:39,810 --> 00:05:41,060
Więc zbudować TRIE.

116
00:05:41,060 --> 00:05:44,860
Miejmy wstawić kilka
przedmiotów do naszego trie.

117
00:05:44,860 --> 00:05:46,740
Tak więc na samym szczycie,
to jest nasz węzeł główny.

118
00:05:46,740 --> 00:05:49,740
Jest to prawdopodobnie będzie coś
idziesz do globalnej deklaracji.

119
00:05:49,740 --> 00:05:53,450
I masz zamiar globalnie utrzymanie
wskaźnik do tego węzła zawsze.

120
00:05:53,450 --> 00:05:55,360
>> Masz zamiar powiedzieć,
Korzeń jest równa, a ty jesteś

121
00:05:55,360 --> 00:05:57,580
będzie malloc sobie węzeł TRIE.

122
00:05:57,580 --> 00:05:59,850
I nigdy nie będziemy
ponownie dotknąć korzeni.

123
00:05:59,850 --> 00:06:02,300
Za każdym razem kiedy chcesz
rozpocząć nawigację za pośrednictwem,

124
00:06:02,300 --> 00:06:05,802
ustawić inny wskaźnik
równa korzenia, takich jak trav,

125
00:06:05,802 --> 00:06:07,760
która jest przykładem I
używać w wielu moich filmów

126
00:06:07,760 --> 00:06:11,090
tu na stosy i kolejki
i listy linków i tak dalej.

127
00:06:11,090 --> 00:06:13,320
>> Ustawić inny wskaźnik
nazywa trav do przechodzenia.

128
00:06:13,320 --> 00:06:15,890
I używasz TRAV do nawigacji
przez strukturę danych.

129
00:06:15,890 --> 00:06:17,500
Zobaczmy więc, jak to może wyglądać.

130
00:06:17,500 --> 00:06:19,880
Więc teraz, co
ma węzeł wygląda?

131
00:06:19,880 --> 00:06:22,920
Cóż, tak jak naszych danych
Deklaracja struktury wskazane,

132
00:06:22,920 --> 00:06:26,906
mamy ciąg, który
w tym przypadku jest pusta.

133
00:06:26,906 --> 00:06:27,780
Nic tu nie ma.

134
00:06:27,780 --> 00:06:29,550
>> A tablica z 10 wskaźników.

135
00:06:29,550 --> 00:06:31,790
A teraz, tylko
mają 1 węzeł w tym trie.

136
00:06:31,790 --> 00:06:33,110
Nie ma nic innego w nim.

137
00:06:33,110 --> 00:06:36,020
Więc wszystkie 10 osób
wskaźniki punktowe na null.

138
00:06:36,020 --> 00:06:38,090
To właśnie czerwony wskazuje.

139
00:06:38,090 --> 00:06:39,500
>> Miejmy wstawić ciąg Harvarda.

140
00:06:39,500 --> 00:06:41,999
Miejmy włożyć Uniwersytet
Harvard do tego trie, które

141
00:06:41,999 --> 00:06:43,940
została założona w roku 1636.

142
00:06:43,940 --> 00:06:48,220
Chcemy użyć klawisza,
1636 roku, aby powiedzieć nam, gdzie jesteśmy

143
00:06:48,220 --> 00:06:50,140
będzie przechowywać Harvard w trie.

144
00:06:50,140 --> 00:06:51,470
Teraz, w jaki sposób możemy to zrobić?

145
00:06:51,470 --> 00:06:52,886
>> To może wyglądać tak.

146
00:06:52,886 --> 00:06:54,160
Zaczynamy u nasady.

147
00:06:54,160 --> 00:06:56,920
I mamy te 10 miejsc możemy iść.

148
00:06:56,920 --> 00:06:59,900
Korzeń jest tak jak każdy
drugi węzeł trie.

149
00:06:59,900 --> 00:07:02,850
Jest 10 miejsc, gdzie idziemy stąd.

150
00:07:02,850 --> 00:07:07,215
>> Gdzie my prawdopodobnie chcesz
iść, jeśli klucz jest 1636?

151
00:07:07,215 --> 00:07:08,340
Jest naprawdę dwie opcje.

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

153
00:07:08,450 --> 00:07:10,825
Możemy zbudować klucz z
od prawej do lewej i zacząć z 6.

154
00:07:10,825 --> 00:07:14,000
Albo możemy budować klucz z
od lewej do prawej i zacząć 1.

155
00:07:14,000 --> 00:07:16,140
>> To prawdopodobnie więcej
Intuicyjny jako człowieka

156
00:07:16,140 --> 00:07:18,110
rozumieć będziemy
Wystarczy przejść od lewej do prawej.

157
00:07:18,110 --> 00:07:21,140
I tak, jeśli chcę wstawić
Harvard do tego trie,

158
00:07:21,140 --> 00:07:23,560
Pewnie chcą rozpocząć
zaczynając od korzenia

159
00:07:23,560 --> 00:07:25,720
patrząc na moje 10 opcji
przede mną, mówiąc:

160
00:07:25,720 --> 00:07:28,700
Chcę iść ścieżką 1.

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

162
00:07:29,700 --> 00:07:31,810
>> Teraz, 1 ścieżka jest aktualnie pusty.

163
00:07:31,810 --> 00:07:35,920
Więc jeśli chcę przejść tą drogą
wstawić ten element w trie,

164
00:07:35,920 --> 00:07:42,040
Muszę malloc nowy węzeł, mają 1
wskazują tam, i to ja jestem dobry, aby przejść.

165
00:07:42,040 --> 00:07:46,460
>> Więc ja w zasadzie jestem ze
Punkt, w którym stoję

166
00:07:46,460 --> 00:07:50,270
u korzeni drzewa i tym
trie i istnieje 10 oddziałów.

167
00:07:50,270 --> 00:07:52,260
Ale każdy oddział ma
bramy przed nim.

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

169
00:07:53,060 --> 00:07:54,850
Bo nie ma nic innego nie ma.

170
00:07:54,850 --> 00:07:56,522
Nie bezpieczne przejście.

171
00:07:56,522 --> 00:07:58,980
Oznacza to, że nie ma nic
dół żadnej z tych oddziałów.

172
00:07:58,980 --> 00:08:02,532
Jeśli chcę, aby rozpocząć budowę
coś, chcę usunąć bramę.

173
00:08:02,532 --> 00:08:04,490
Chcę usunąć bramę
przed numerem 1.

174
00:08:04,490 --> 00:08:05,698
I chcę iść w dół, że.

175
00:08:05,698 --> 00:08:08,060
I chcę zbudować
kolejne miejsce dla mnie, aby przejść.

176
00:08:08,060 --> 00:08:09,470
>> I to jest to, co zrobiłem tutaj.

177
00:08:09,470 --> 00:08:11,430
Tak więc 1 nie wskazuje już na null.

178
00:08:11,430 --> 00:08:13,830
Powiedziałem, że to bezpieczne, aby zejść tutaj.

179
00:08:13,830 --> 00:08:15,789
I zbudował inny węzeł.

180
00:08:15,789 --> 00:08:18,330
A kiedy się do tego węzła, ja
mają inną decyzję.

181
00:08:18,330 --> 00:08:20,890
Gdzie ja mam dalej?

182
00:08:20,890 --> 00:08:22,700
>> Cóż, ja już poszła w dół 1.

183
00:08:22,700 --> 00:08:24,470
Więc teraz pewnie chce iść w dół 6.

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

185
00:08:24,970 --> 00:08:27,100
Znów mam 10 lokalizacje mogę wybrać.

186
00:08:27,100 --> 00:08:30,060
Więc teraz zejść numer 6.

187
00:08:30,060 --> 00:08:32,280
Więc jasne bramę
przed numerem 6.

188
00:08:32,280 --> 00:08:33,250
I idę tam.

189
00:08:33,250 --> 00:08:34,580
I budowa kolejnego węzła.

190
00:08:34,580 --> 00:08:37,630
I już dotarł do kolejnego punktu połączenia.

191
00:08:37,630 --> 00:08:40,289
>> Znów mam 10 wyborów
dla których mogę iść.

192
00:08:40,289 --> 00:08:42,799
Mam przeniesiony od 1 do 6.

193
00:08:42,799 --> 00:08:44,215
Więc teraz pewnie chce iść do 3.

194
00:08:44,215 --> 00:08:45,381
3, nie ma gdzie mogę iść.

195
00:08:45,381 --> 00:08:48,980
Więc muszę oczyścić drogę
i zbudować sobie nową przestrzeń.

196
00:08:48,980 --> 00:08:50,870
A następnie od 3, gdzie chcę iść?

197
00:08:50,870 --> 00:08:52,450
Chcę zejść 6.

198
00:08:52,450 --> 00:08:54,770
>> I znowu, musiałem
oczyścić drogę, aby to zrobić.

199
00:08:54,770 --> 00:08:59,179
Więc teraz użyłem mój klucz do wstawienia stworzyć
węzły i zacząć budować ten TRIE.

200
00:08:59,179 --> 00:09:00,220
Zacząłem się w katalogu głównym.

201
00:09:00,220 --> 00:09:03,666
Poszedłem na dół 1636.

202
00:09:03,666 --> 00:09:05,540
A teraz jestem na dnie
nie w tym węźle.

203
00:09:05,540 --> 00:09:06,610
I może być w stanie
zobaczyć go na ekranie.

204
00:09:06,610 --> 00:09:07,735
>> Jest podświetlone na żółto.

205
00:09:07,735 --> 00:09:10,020
To gdzie ja obecnie jestem.

206
00:09:10,020 --> 00:09:11,300
Mój klucz jest wykonywana.

207
00:09:11,300 --> 00:09:13,030
Byłem wyczerpany każdą pozycję w moim kluczem.

208
00:09:13,030 --> 00:09:15,040
Więc nie mogę iść dalej.

209
00:09:15,040 --> 00:09:17,720
Więc w tym momencie, wszystko co
naprawdę musisz zrobić, to powiedzieć: OK.

210
00:09:17,720 --> 00:09:18,990
To tak jakby patrząc
w ziemię,

211
00:09:18,990 --> 00:09:21,115
jeśli przewidując
siebie jako tego rodzaju ścieżki

212
00:09:21,115 --> 00:09:22,350
z różnych połączeń.

213
00:09:22,350 --> 00:09:25,800
Rodzaj patrząc w dół i rodzaj
Spray malowanie Harvard na ziemi.

214
00:09:25,800 --> 00:09:26,800
To jest nazwa tego.

215
00:09:26,800 --> 00:09:28,300
Wiesz, że to co jest w tym miejscu.

216
00:09:28,300 --> 00:09:31,870
Jeśli zaczynają się od korzenia i idziemy w dół
1 i 6, a następnie 3 i 6,

217
00:09:31,870 --> 00:09:32,780
gdzie jesteśmy?

218
00:09:32,780 --> 00:09:35,640
Cóż, jeśli spojrzymy w dół
i widzimy, Harvard, a następnie

219
00:09:35,640 --> 00:09:38,960
wiemy, że Harvard było
założona w 1636 roku w oparciu o sposób

220
00:09:38,960 --> 00:09:41,400
mamy do realizacji tej struktury danych.

221
00:09:41,400 --> 00:09:43,177
Więc mam nadzieję, że to było proste.

222
00:09:43,177 --> 00:09:44,760
Mamy zamiar zrobić jeszcze dwie wstawki.

223
00:09:44,760 --> 00:09:50,060
I miejmy nadzieję, że to pomoże
zobacz to zrobić dwa razy więcej.

224
00:09:50,060 --> 00:09:52,210
>> A teraz włóż inną uczelnię.

225
00:09:52,210 --> 00:09:54,630
Załóżmy, włóż w to Yale trie.

226
00:09:54,630 --> 00:09:57,037
Yale został założony w 1701 roku.

227
00:09:57,037 --> 00:09:58,870
Będziemy więc rozpocząć się
korzeń, jak zawsze.

228
00:09:58,870 --> 00:09:59,890
I ustawiamy wskaźnik przejścia.

229
00:09:59,890 --> 00:10:01,624
Mamy zamiar używać, aby poruszać się.

230
00:10:01,624 --> 00:10:03,790
Pierwszą rzeczą, którą chcesz
zrobić, to przejść ścieżką 1.

231
00:10:03,790 --> 00:10:05,830
To pierwsza cyfra nasz klucz.

232
00:10:05,830 --> 00:10:08,420
Na szczęście jednak, nie robimy
trzeba wykonywać żadnej pracy tym razem.

233
00:10:08,420 --> 00:10:09,919
Ścieżka 1 zostały już usunięte.

234
00:10:09,919 --> 00:10:13,520
I straciła gola wcześniej, kiedy
było wstawienie Harvard w 1636 roku.

235
00:10:13,520 --> 00:10:18,090
Więc mogę spokojnie przejść
dół 1 i właśnie tam.

236
00:10:18,090 --> 00:10:20,150
Jeśli można przesunąć w dół 1.

237
00:10:20,150 --> 00:10:22,930
>> Teraz jednak chcę iść do 7.

238
00:10:22,930 --> 00:10:24,280
I otworzyło drogę na 6.

239
00:10:24,280 --> 00:10:27,050
Wiem, że mogę bezpiecznie
postępować ścieżką 6.

240
00:10:27,050 --> 00:10:29,220
Ale muszę przejść na ścieżce 7.

241
00:10:29,220 --> 00:10:30,580
Więc co mam zrobić?

242
00:10:30,580 --> 00:10:35,070
Cóż, tak jak wcześniej, tylko trzeba
aby usunąć bramę, dostać się z drogi,

243
00:10:35,070 --> 00:10:38,740
i zbudować nowy węzeł z drogą 7.

244
00:10:38,740 --> 00:10:40,250
Po prostu tak.

245
00:10:40,250 --> 00:10:42,930
>> Więc teraz mam przeniósł 1, a następnie 7.

246
00:10:42,930 --> 00:10:45,550
A teraz zauważyć, że jestem jakby
w sprawie tego nowego subbranch.

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

248
00:10:46,050 --> 00:10:49,260
Wszystko inne od 16
na, nie dbam o.

249
00:10:49,260 --> 00:10:50,720
Nie robię nic 16.

250
00:10:50,720 --> 00:10:51,750
Robię 17 rzeczy.

251
00:10:51,750 --> 00:10:58,380
>> Więc teraz, z 17 na, muszę
rodzaj płoną tu nowe szlaki.

252
00:10:58,380 --> 00:11:00,462
Kolejny mój klucz jest cyfra 0.

253
00:11:00,462 --> 00:11:01,670
I oczywiście nie można dostać wszędzie.

254
00:11:01,670 --> 00:11:02,628
Właśnie zbudował ten węzeł.

255
00:11:02,628 --> 00:11:04,550
Tak wiem, że nie ma
Ścieżki forward tutaj.

256
00:11:04,550 --> 00:11:06,370
Muszę więc zrobić jeden siebie.

257
00:11:06,370 --> 00:11:09,360
>> Więc malloc nowy węzeł
i mają 0 pkt tam.

258
00:11:09,360 --> 00:11:12,770
A potem jeszcze raz, ja malloc
Nowy węzeł ma jeden punkt i tam.

259
00:11:12,770 --> 00:11:15,870
Ponownie, już wyczerpane mój klucz, 1701.

260
00:11:15,870 --> 00:11:18,472
Więc patrzę w dół, a ja lakierniczych Yale.

261
00:11:18,472 --> 00:11:19,680
To jest nazwa tego węzła.

262
00:11:19,680 --> 00:11:24,660
>> A więc teraz, jeśli kiedykolwiek trzeba sprawdzić, czy Yale
trie jest w tym, że zaczynają się od korzenia,

263
00:11:24,660 --> 00:11:27,060
Idę w dół 1701, i spojrzeć w dół.

264
00:11:27,060 --> 00:11:30,030
A jeśli widzę sprayu Yale
malowane na ziemi, po czym

265
00:11:30,030 --> 00:11:32,200
Wiem, że istnieje w tej Yale trie.

266
00:11:32,200 --> 00:11:32,950
Zróbmy jeszcze jeden.

267
00:11:32,950 --> 00:11:36,430
Miejmy włożyć Dartmouth w to
trie, która została założona w 1769 roku.

268
00:11:36,430 --> 00:11:37,750
>> Zacznij od korzenia ponownie.

269
00:11:37,750 --> 00:11:39,445
Moja pierwsza cyfra mojego klucza to 1.

270
00:11:39,445 --> 00:11:40,820
Mogę spokojnie przejść tą drogą.

271
00:11:40,820 --> 00:11:42,400
To już istnieje.

272
00:11:42,400 --> 00:11:44,040
Następna cyfra mojego klucza jest 7.

273
00:11:44,040 --> 00:11:45,890
Mogę spokojnie przejść tą drogą.

274
00:11:45,890 --> 00:11:47,540
Istnieje również.

275
00:11:47,540 --> 00:11:49,000
>> Mój następny jest 6.

276
00:11:49,000 --> 00:11:52,860
Stąd, skąd ja aktualnie jestem
tam żółty w tym węzeł pośredni,

277
00:11:52,860 --> 00:11:56,060
6 jest zablokowany off.

278
00:11:56,060 --> 00:11:58,830
Jeśli chcę iść tą drogą,
Mam zbudować go samodzielnie.

279
00:11:58,830 --> 00:12:02,250
Więc będę malloc nowy węzeł
i mają 6 punkt tam.

280
00:12:02,250 --> 00:12:04,250
A potem znowu, jestem
płonącego nowe szlaki tutaj.

281
00:12:04,250 --> 00:12:10,750
>> Więc malloc nowy węzeł tak, że od
że node-- numer trasy 9-- i teraz

282
00:12:10,750 --> 00:12:13,584
jeśli podróżujesz 1769, i spojrzeć w dół.

283
00:12:13,584 --> 00:12:15,500
Nie ma to obecnie
Spray malowane tam.

284
00:12:15,500 --> 00:12:16,930
Mogę napisać Dartmouth.

285
00:12:16,930 --> 00:12:20,710
A ja włożona
Dartmouth w trie.

286
00:12:20,710 --> 00:12:23,450
>> Więc to jest wstawianie
rzeczy do trie.

287
00:12:23,450 --> 00:12:25,384
Teraz chcemy, aby szukać rzeczy.

288
00:12:25,384 --> 00:12:27,050
Jak mamy szukać rzeczy w trie?

289
00:12:27,050 --> 00:12:29,170
Cóż, to prawie ten sam pomysł.

290
00:12:29,170 --> 00:12:33,620
Teraz wystarczy użyć cyfr klucza
aby sprawdzić, czy możemy poruszać się od korzenia

291
00:12:33,620 --> 00:12:37,170
tam, gdzie chcemy iść w trie.

292
00:12:37,170 --> 00:12:41,620
>> Jeśli uderzymy w ślepy zaułek w każdym punkcie, a następnie
wiemy, że ten element nie istnieje

293
00:12:41,620 --> 00:12:44,500
albo, że ścieżka będzie
zostały już usunięte.

294
00:12:44,500 --> 00:12:45,930
Jeśli robimy to przez całą drogę do
koniec, wszystko co musisz zrobić,

295
00:12:45,930 --> 00:12:48,471
jest spojrzeć w dół i zobaczyć, czy to
element szukamy.

296
00:12:48,471 --> 00:12:49,335
Jeśli tak, to sukces.

297
00:12:49,335 --> 00:12:52,610
Jeśli nie, nie.

298
00:12:52,610 --> 00:12:54,940
>> Warto więc szukać
Harvard w tym trie.

299
00:12:54,940 --> 00:12:56,020
Zaczynamy u nasady.

300
00:12:56,020 --> 00:12:58,228
I znowu, będziemy
utworzyć wskaźnik przejścia

301
00:12:58,228 --> 00:12:59,390
zrobić dla nas nasze ruchy.

302
00:12:59,390 --> 00:13:02,080
Z katalogu wiemy, że
Pierwszym miejscem, musimy udać się 1,

303
00:13:02,080 --> 00:13:03,390
możemy to zrobić?

304
00:13:03,390 --> 00:13:03,982
Tak możemy.

305
00:13:03,982 --> 00:13:04,690
Jeśli bezpiecznie istnieje.

306
00:13:04,690 --> 00:13:06,660
Możemy tam iść.

307
00:13:06,660 --> 00:13:08,440
>> Teraz, następne miejsce musimy iść to 6.

308
00:13:08,440 --> 00:13:10,557
Czy ścieżka 6 istnieje tutaj?

309
00:13:10,557 --> 00:13:11,140
Tak, tak.

310
00:13:11,140 --> 00:13:12,690
Możemy iść ścieżką 6.

311
00:13:12,690 --> 00:13:13,905
A to w końcu tutaj.

312
00:13:13,905 --> 00:13:16,130
>> Możemy iść ścieżką stąd 3?

313
00:13:16,130 --> 00:13:18,450
Cóż, jak się okazuje,
tak, że istnieje też.

314
00:13:18,450 --> 00:13:20,790
I możemy się na ścieżce 6 stąd?

315
00:13:20,790 --> 00:13:21,982
Tak możemy.

316
00:13:21,982 --> 00:13:24,002
>> Nie dość odpowiedział
jeszcze pytanie.

317
00:13:24,002 --> 00:13:25,710
Jest jeszcze jeden
krok, który jest obecnie

318
00:13:25,710 --> 00:13:28,520
musimy spojrzeć w dół i
zobaczyć, czy to actually--

319
00:13:28,520 --> 00:13:32,660
jeśli szukamy Harvardu, jest to, że
co znajdziemy po tym wyczerpuje klucz?

320
00:13:32,660 --> 00:13:35,430
W przykładzie używamy tutaj,
lata są zawsze cztery cyfry.

321
00:13:35,430 --> 00:13:40,280
Ale być może używasz na przykład, w którym
warunki przechowywania słownika wyrazów.

322
00:13:40,280 --> 00:13:44,060
>> I tak zamiast 10 wskazówek
dla mojej lokalizacji, może być 26.

323
00:13:44,060 --> 00:13:46,040
Po jednym dla każdej litery alfabetu.

324
00:13:46,040 --> 00:13:50,350
I są pewne słowa takie jak bat,
który jest podzbiorem partii, na przykład.

325
00:13:50,350 --> 00:13:53,511
A więc nawet jeśli się do
koniec klucza i spojrzeć w dół,

326
00:13:53,511 --> 00:13:55,260
nie może zobaczyć, co
szukasz.

327
00:13:55,260 --> 00:13:58,500
>> Więc zawsze masz do przejścia
cała ścieżka, a następnie

328
00:13:58,500 --> 00:14:01,540
jeśli były z powodzeniem w stanie
przemierzać całą ścieżkę,

329
00:14:01,540 --> 00:14:03,440
spojrzeć w dół i zrobić jedną ostatecznego potwierdzenia.

330
00:14:03,440 --> 00:14:05,120
Czy to, co szukam?

331
00:14:05,120 --> 00:14:07,740
Cóż, patrzę w dół po uruchomieniu
na górze i będzie 1636.

332
00:14:07,740 --> 00:14:08,240
Patrzę w dół.

333
00:14:08,240 --> 00:14:09,400
Widzę Harvard.

334
00:14:09,400 --> 00:14:11,689
Tak, tak, to mi się udało.

335
00:14:11,689 --> 00:14:13,980
Co, jeśli to, co szukam
nie ma w trie, choć.

336
00:14:13,980 --> 00:14:17,200
Co zrobić, jeśli szukam Princeton,
która została założona w 1746 roku.

337
00:14:17,200 --> 00:14:20,875
I tak 1746 będzie mój klucz
poruszać się po trie.

338
00:14:20,875 --> 00:14:22,040
Cóż, zaczynają się od korzenia.

339
00:14:22,040 --> 00:14:24,760
I pierwsze miejsce chcę
by idzie ścieżką 1.

340
00:14:24,760 --> 00:14:25,590
Czy mogę to zrobić?

341
00:14:25,590 --> 00:14:26,490
Tak, mogę.

342
00:14:26,490 --> 00:14:28,730
>> Mogę iść ścieżką stamtąd 7?

343
00:14:28,730 --> 00:14:29,230
Tak, mogę.

344
00:14:29,230 --> 00:14:30,750
Że istnieje też.

345
00:14:30,750 --> 00:14:32,460
Ale mogę iść ścieżką stąd 4?

346
00:14:32,460 --> 00:14:35,550
To jak zadać pytanie, może
I przejść się, że mały kwadrat

347
00:14:35,550 --> 00:14:37,114
że mam podświetlone na żółto?

348
00:14:37,114 --> 00:14:38,030
Tam nic nie ma.

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

350
00:14:38,610 --> 00:14:41,310
>> Nie ma mowy, naprzód ścieżką 4.

351
00:14:41,310 --> 00:14:46,480
Jeśli Marcin był w tym trie, że 4
zostałby dopuszczony do nas już.

352
00:14:46,480 --> 00:14:49,130
A więc w tym momencie
dotarliśmy w ślepy zaułek.

353
00:14:49,130 --> 00:14:50,250
Nie możemy iść dalej.

354
00:14:50,250 --> 00:14:53,440
I tak można powiedzieć, ostatecznie, nie.

355
00:14:53,440 --> 00:14:56,760
Marcin nie ma w tym trie.

356
00:14:56,760 --> 00:14:58,860
>> Więc co to wszystko znaczy?

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

358
00:14:59,360 --> 00:15:01,000
Jest dużo się tu dzieje.

359
00:15:01,000 --> 00:15:02,500
Nie ma wskazówek, w każdym miejscu.

360
00:15:02,500 --> 00:15:04,249
I, jak widać
tylko z wykresu,

361
00:15:04,249 --> 00:15:07,010
jest wiele węzłów, które
są rodzajem latają.

362
00:15:07,010 --> 00:15:13,480
Zauważmy jednak, za każdym razem chcieliśmy
sprawdzić, czy coś jest nie w trie,

363
00:15:13,480 --> 00:15:15,000
mieliśmy tylko do 4 ruchy.

364
00:15:15,000 --> 00:15:17,208
>> Za każdym razem chcieliśmy
wstawić coś w trie,

365
00:15:17,208 --> 00:15:20,440
mamy do 4 ruchów, ewentualnie
mallocing pewne rzeczy po drodze.

366
00:15:20,440 --> 00:15:23,482
Ale jak widzieliśmy, gdy włożona
Dartmouth w trie,

367
00:15:23,482 --> 00:15:25,940
Czasami pewne ścieżki
może już być wyczyszczone dla nas.

368
00:15:25,940 --> 00:15:30,520
I tak, jak nasza trie robi się coraz większy i
większe, musimy zrobić mniej pracy za każdym razem,

369
00:15:30,520 --> 00:15:32,270
aby wstawić nowe rzeczy
już, bo mamy

370
00:15:32,270 --> 00:15:35,746
zbudowany dużo pośredniego
gałęzie po drodze.

371
00:15:35,746 --> 00:15:38,370
Jeśli tylko kiedykolwiek spojrzeć na
4 rzeczy, 4 jest po prostu stałą.

372
00:15:38,370 --> 00:15:41,750
Naprawdę są rodzajem zbliża
stała wstawiania czas

373
00:15:41,750 --> 00:15:44,501
Czas i stały wyszukiwania.

374
00:15:44,501 --> 00:15:47,500
Wadą oczywiście jest, że
tego trie, jak można prawdopodobnie powiedzieć,

375
00:15:47,500 --> 00:15:49,030
jest ogromna.

376
00:15:49,030 --> 00:15:51,040
Każdy z tych węzłów
zajmuje dużo miejsca.

377
00:15:51,040 --> 00:15:52,090
>> Ale to jest kompromis.

378
00:15:52,090 --> 00:15:55,260
Jeśli chcemy naprawdę szybkie
wstawiania, bardzo szybkie usunięcie,

379
00:15:55,260 --> 00:15:59,630
i bardzo szybkie wyszukiwanie, musimy
mają wiele danych latają.

380
00:15:59,630 --> 00:16:03,590
Musimy odłożyć dużo miejsca
i pamięć dla tej struktury danych

381
00:16:03,590 --> 00:16:04,290
istnieć.

382
00:16:04,290 --> 00:16:05,415
>> I tak to jest kompromis.

383
00:16:05,415 --> 00:16:07,310
Ale wygląda na to,
może ją znaleźli.

384
00:16:07,310 --> 00:16:09,560
Możemy odkryli, że
Święty Graal struktur danych

385
00:16:09,560 --> 00:16:12,264
z szybkim wprowadzeniem,
usuwanie i wyszukiwanie.

386
00:16:12,264 --> 00:16:14,430
A może będzie to
odpowiednie struktury danych

387
00:16:14,430 --> 00:16:18,890
do korzystania z jakichkolwiek informacji
próbujemy sklepie.

388
00:16:18,890 --> 00:16:21,860
Jestem Doug Lloyd, to CS50.

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