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
Ми хочемо використовувати ключ,
Тисячу шістсот тридцять шість, щоб сказати нам, де ми

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
>> Куди ми, ймовірно, хочете
щоб піти, якщо ключ тисячу шістсот тридцять шість?

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
Я пішов вниз один тисяча шістсот тридцять шість.

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
Знову ж таки, я вичерпав свій ключ, 1 701.

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
Я спускаюся 1 701, і дивитися вниз.

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
Ну, я дивлюся вниз після запуску
у верхній і збирається тисячу шістсот тридцять шість.

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