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