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
че хешове на тази хеш-код.

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
имаща същата хеш-код.

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
A Булева може да бъде толкова просто като малко.

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
>> Ако въведете John, тогава
ние търсим Джон.

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

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
Ако видим едно, този клон,
и така нататък, и така нататък, и така нататък.

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
Ще си изчистване 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 за прекосява.

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
И точно сега, ние само
има един възел в тази синтактично дърво.

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
Нека да въведете университет
Harvard в тази синтактично дърво, което

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
ще се съхранява в Harvard 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
И така, ако искам да вмъкнете
Harvard в тази синтактично дърво,

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
>> Сега, един път в момента е нищожна.

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
в основата на дървото или
синтактично дърво и има 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
Така че една вече не сочи към нула.

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
И когато стигнем до този възел, I
имаме още едно решение да се направи.

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 места I могат да избират.

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
Ключова My е направено.

207
00:09:11,300 --> 00:09:13,030
Аз бях изчерпал всяка позиция в моя ключ.

208
00:09:13,030 --> 00:09:15,040
Така че аз не мога да отида по-нататък.

209
00:09:15,040 --> 00:09:17,720
Така че в този момент, всичко, което мога
Наистина трябва да направите е да се каже, OK.

210
00:09:17,720 --> 00:09:18,990
Това е нещо като начало
надолу към земята,

211
00:09:18,990 --> 00:09:21,115
ако сте предвиждащ
себе си като този вид на пътя

212
00:09:21,115 --> 00:09:22,350
с различни връзки.

213
00:09:22,350 --> 00:09:25,800
Нещо гледа надолу и да сортирате на
спрей боядисване Harvard на земята.

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
Нека да вмъкнете Yale в тази синтактично дърво.

226
00:09:54,630 --> 00:09:57,037
Yale е основана през 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
В един път вече е изчистена.

234
00:10:09,919 --> 00:10:13,520
Аз го изчисти преди това, когато аз
се поставяте в Harvard 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
I разчисти пътя към 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
Така че аз гледам надолу и аз спрей боя Yale.

261
00:11:18,472 --> 00:11:19,680
Това е името на този възел.

262
00:11:19,680 --> 00:11:24,660
>> И така, сега, ако някога се наложи да се види дали Yale
е в това синтактично дърво, започна в корена,

263
00:11:24,660 --> 00:11:27,060
Сляза 1701, и погледнете надолу.

264
00:11:27,060 --> 00:11:30,030
И ако видя Yale спрей
рисувани върху земята, а след това

265
00:11:30,030 --> 00:11:32,200
Знам, Yale съществува в този синтактично дърво.

266
00:11:32,200 --> 00:11:32,950
Нека да направим още една.

267
00:11:32,950 --> 00:11:36,430
Нека да вмъкнете Dartmouth в тази
синтактично дърво, която е основана през 1769.

268
00:11:36,430 --> 00:11:37,750
>> Започнете в основата отново.

269
00:11:37,750 --> 00:11:39,445
Моята първа цифра на ключовата ми е едно.

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
>> My следващата е 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
ако пътувам 1,769, а аз гледам надолу.

283
00:12:13,584 --> 00:12:15,500
Няма нищо в момента
спрей боядисани там.

284
00:12:15,500 --> 00:12:16,930
Мога да напиша Dartmouth.

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
>> Така че нека да търси за
Harvard в тази синтактично дърво.

299
00:12:54,940 --> 00:12:56,020
Започваме в корена.

300
00:12:56,020 --> 00:12:58,228
И, отново, ние ще
създадете прекосява показалка

301
00:12:58,228 --> 00:12:59,390
да направи нашите ходове за нас.

302
00:12:59,390 --> 00:13:02,080
От корена ние знаем, че
първо място ние трябва да отида е 1,

303
00:13:02,080 --> 00:13:03,390
можем да направим това?

304
00:13:03,390 --> 00:13:03,982
Да ние можем.

305
00:13:03,982 --> 00:13:04,690
Ако съществува безопасно.

306
00:13:04,690 --> 00:13:06,660
Ние можем да отидем там.

307
00:13:06,660 --> 00:13:08,440
>> Сега, следващото място, което трябва да отида е 6.

308
00:13:08,440 --> 00:13:10,557
Пътят 6 Съществува ли от тук?

309
00:13:10,557 --> 00:13:11,140
Да, това е така.

310
00:13:11,140 --> 00:13:12,690
Ние можем да слезем на пътя 6.

311
00:13:12,690 --> 00:13:13,905
И ние в крайна сметка тук.

312
00:13:13,905 --> 00:13:16,130
>> Можем ли да върви надолу по пътеката 3 от тук?

313
00:13:16,130 --> 00:13:18,450
Е, както се оказва,
Да, съществува също.

314
00:13:18,450 --> 00:13:20,790
И можем да получим по пътя 6 от тук?

315
00:13:20,790 --> 00:13:21,982
Да ние можем.

316
00:13:21,982 --> 00:13:24,002
>> Не сме съвсем отговори
Все още на въпроса.

317
00:13:24,002 --> 00:13:25,710
Все още има още една
стъпка, която в момента е

318
00:13:25,710 --> 00:13:28,520
ние трябва да се погледне надолу и
да видим дали това е actually--

319
00:13:28,520 --> 00:13:32,660
ако ние не търсим Харвард, е, че
това, което откриваме, след като изчерпи ключът?

320
00:13:32,660 --> 00:13:35,430
В примера ние използваме тук,
годините винаги са четири цифри.

321
00:13:35,430 --> 00:13:40,280
Но вие може да се използва за пример, където
съхранявате речник на думи.

322
00:13:40,280 --> 00:13:44,060
>> И така, вместо да се налага 10 показалки
за моето място, може да се наложи 26.

323
00:13:44,060 --> 00:13:46,040
Един за всяка буква от азбуката.

324
00:13:46,040 --> 00:13:50,350
И има някои думи като прилеп,
който е подмножество на партида, например.

325
00:13:50,350 --> 00:13:53,511
И така, дори и да стигнем до
край на ключа и погледнете надолу,

326
00:13:53,511 --> 00:13:55,260
може да не видите това, което
, което търсите.

327
00:13:55,260 --> 00:13:58,500
>> Така че винаги трябва да прекосяват
целия път и след това

328
00:13:58,500 --> 00:14:01,540
ако сте били в състояние успешно
да прекосяват целия път,

329
00:14:01,540 --> 00:14:03,440
погледнете надолу и направете едно окончателно потвърждение.

330
00:14:03,440 --> 00:14:05,120
Е, че това, което аз търся?

331
00:14:05,120 --> 00:14:07,740
Е, аз гледам надолу след започване
на върха и ще 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
Това е като да си зададе въпроса, може
I продължите надолу, че малък площад

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
Принстън не съществува в този синтактично дърво.

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

369
00:15:30,520 --> 00:15:32,270
да въведете нови неща
защото вече сме

370
00:15:32,270 --> 00:15:35,746
построена много на междинния
клонове по протежение на пътя.

371
00:15:35,746 --> 00:15:38,370
Ако ние само някога трябва да разгледаме
4 неща, 4 е просто константа.

372
00:15:38,370 --> 00:15:41,750
Ние наистина са вид наближава
константно време вмъкване

373
00:15:41,750 --> 00:15:44,501
и константно време за справка.

374
00:15:44,501 --> 00:15:47,500
Компромис, разбира се, е, че
това синтактично дърво, както вероятно можете да кажа,

375
00:15:47,500 --> 00:15:49,030
е огромна.

376
00:15:49,030 --> 00:15:51,040
Всеки от тези възли
заема много място.

377
00:15:51,040 --> 00:15:52,090
>> Но това е компромис.

378
00:15:52,090 --> 00:15:55,260
Ако искаме наистина бързо
вмъкване, наистина бързо изтриване,

379
00:15:55,260 --> 00:15:59,630
и наистина бързо търсене, ние трябва да
има много данни, които летят наоколо.

380
00:15:59,630 --> 00:16:03,590
Ние трябва да се заделят много място
и памет за които структурата на данните

381
00:16:03,590 --> 00:16:04,290
да съществува.

382
00:16:04,290 --> 00:16:05,415
>> И така, това е компромис.

383
00:16:05,415 --> 00:16:07,310
Но изглежда, че ние
може да са го намерили.

384
00:16:07,310 --> 00:16:09,560
Ние може да сме установили, че
Светия Граал на структури от данни

385
00:16:09,560 --> 00:16:12,264
с бърз вмъкване,
заличаване и справка.

386
00:16:12,264 --> 00:16:14,430
И може би това ще бъде
подходяща структура от данни

387
00:16:14,430 --> 00:16:18,890
да се използва за всякаква информация
ние се опитваме да я запазите.

388
00:16:18,890 --> 00:16:21,860
Аз съм Дъг Лойд, това е cs50.

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