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
с той же хэш-код.

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
В этом случае, мы не собираемся использовать
что-то же просто, как Boolean.

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
И в основном идея
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
Если мы хотим, чтобы вставить элемент
в синтаксического дерева, все, что мы должны сделать,

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
собирается таНос себе 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
>> Вы можете установить другой указатель
называется Трав для обхода.

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

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
Правильно.

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
в корне дерева или
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
Так что теперь я использовал свой ключ, чтобы вставить создать
узлы и начать строить эту синтаксического дерева.

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
Правильно.

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
И если я вижу Yale спрей
окрашены на землю, то

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
Давайте вставить Дартмут в это
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
И я вставил
Дартмут в синтаксического дерева.

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
мы должны смотреть вниз и
увидеть, если это 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
Ну, я смотрю вниз после запуска
в верхней и собирается 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
Правильно.

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
Правильно.

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 перемещается, возможно,
mallocing некоторые вещи по пути.

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
И так как наш 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