1
00:00:00,000 --> 00:00:07,700

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Понякога, когато изграждането на
програма, може да искате да използвате по-

3
00:00:10,890 --> 00:00:13,190
структура на данните, известен като речник.

4
00:00:13,190 --> 00:00:17,960
Речник карти ключове, които са
обикновено струни, до стойности, цели числа,

5
00:00:17,960 --> 00:00:21,900
символа, указател към някакъв обект,
каквото си искаме.

6
00:00:21,900 --> 00:00:26,510
Това е точно като обикновените речници
че картата думи чрез определения.

7
00:00:26,510 --> 00:00:29,440
>> Речници ни предоставите
Възможност за съхраняване на информация

8
00:00:29,440 --> 00:00:32,750
свързани с нещо
и го гледам по-късно.

9
00:00:32,750 --> 00:00:36,620
И така, как ние всъщност приложи
речник в, да речем, C код, който ние можем да

10
00:00:36,620 --> 00:00:38,460
използвате в една от нашите програми?

11
00:00:38,460 --> 00:00:41,790
Е, има много начини, по които
бихме могли да приложат речник.

12
00:00:41,790 --> 00:00:45,930
>> От една страна, бихме могли да използваме масив, който ние
динамично повторно размер или бихме могли да използвате

13
00:00:45,930 --> 00:00:49,150
свързан списък, хеш таблица
или двоичен дърво.

14
00:00:49,150 --> 00:00:52,250
Но каквото и да изберете, ние трябва да
бъдат съпричастни на ефективността и

15
00:00:52,250 --> 00:00:54,300
представяне на изпълнението.

16
00:00:54,300 --> 00:00:57,930
Ние трябва да мислим за използвания алгоритъм
да вмъкнете и погледнете нагоре елементи в

17
00:00:57,930 --> 00:00:59,120
нашата структура данни.

18
00:00:59,120 --> 00:01:03,060
>> За сега, нека да приемем, че ние
искате да използвате низове като ключове.

19
00:01:03,060 --> 00:01:07,290
Нека поговорим за една възможност,
структурата на данните нарича Trie.

20
00:01:07,290 --> 00:01:11,210
Така че тук е визуално представяне
на Trie.

21
00:01:11,210 --> 00:01:14,590
>> Тъй като на снимката подсказва, а Trie
е с дървовидна структура на данните с

22
00:01:14,590 --> 00:01:16,050
възли, свързани заедно.

23
00:01:16,050 --> 00:01:19,420
Виждаме, че има ясно корен
възел с някои връзки, простиращи се

24
00:01:19,420 --> 00:01:20,500
други възли.

25
00:01:20,500 --> 00:01:23,040
Но какво означава всеки възел се състои от?

26
00:01:23,040 --> 00:01:26,700
Ако приемем, че ние сме съхранение на ключове
само с буквени знаци, и

27
00:01:26,700 --> 00:01:30,150
ние не се грижи за капитализация,
тук е определение на възел, който

28
00:01:30,150 --> 00:01:31,100
ще са достатъчни.

29
00:01:31,100 --> 00:01:34,130
>> Един обект, чийто тип е структурата
възел има две части

30
00:01:34,130 --> 00:01:35,740
нарича данни и деца.

31
00:01:35,740 --> 00:01:39,200
Ние сме лявата част на данни като коментар
да бъдат заменени от компонент

32
00:01:39,200 --> 00:01:43,190
декларация, когато структурата на възел е
включено в програма C.

33
00:01:43,190 --> 00:01:47,040
Част на данни възел може да бъде
Булева стойност да се посочи дали или

34
00:01:47,040 --> 00:01:51,160
не възел представлява завършване
на речник ключ или тя може да бъде

35
00:01:51,160 --> 00:01:54,240
низ представлява определението
на дума в речника.

36
00:01:54,240 --> 00:01:58,870
>> Ние ще използваме усмивка на лицето да посочи
когато данните се намира в един възел.

37
00:01:58,870 --> 00:02:02,310
Има 26 елементи в този
деца масив, един форум

38
00:02:02,310 --> 00:02:03,690
на буква от азбуката.

39
00:02:03,690 --> 00:02:06,570
Ще видим значението
на това скоро.

40
00:02:06,570 --> 00:02:10,759
>> Нека да погледнем по-отблизо на корен възел
в нашата схема, която няма данни

41
00:02:10,759 --> 00:02:14,740
свързани с нея, както е посочено от
отсъствие на усмихнато се изправи в

42
00:02:14,740 --> 00:02:16,110
порция данни.

43
00:02:16,110 --> 00:02:19,910
Стрелките, простиращи се от части на
децата масиви представляват не-възел

44
00:02:19,910 --> 00:02:21,640
указатели към други възли.

45
00:02:21,640 --> 00:02:25,500
Например, стрелката, простираща се от
вторият елемент на деца

46
00:02:25,500 --> 00:02:28,400
представлява буквата B
в основен речник.

47
00:02:28,400 --> 00:02:31,920
И в по-голямата схема
ние го надпишете с B.

48
00:02:31,920 --> 00:02:35,810
>> Имайте предвид, че в по-голямата схема, когато
изготвя указател към друг възел, тя

49
00:02:35,810 --> 00:02:39,100
Няма значение, когато стрелката
отговаря, че друг възел.

50
00:02:39,100 --> 00:02:43,850
Нашата проба Trie речник съдържа
две думи, че и мащабиране.

51
00:02:43,850 --> 00:02:47,040
Да минеш през един пример за
погледна данни за ключ.

52
00:02:47,040 --> 00:02:50,800
>> Да предположим, че ние искахме да се запознаете с
съответстваща стойност за ключов баня.

53
00:02:50,800 --> 00:02:53,610
Ще започнем нашия поглед нагоре
В основата възел.

54
00:02:53,610 --> 00:02:57,870
След това ние ще направим първата буква от нашата
ключ, B, и намерите съответния

55
00:02:57,870 --> 00:03:00,020
място в нашия деца масив.

56
00:03:00,020 --> 00:03:04,490
Забележете, че има точно 26 точки
в масива, една за всяка буква от

57
00:03:04,490 --> 00:03:05,330
азбуката.

58
00:03:05,330 --> 00:03:08,800
И ние ще имаме петната представляват
букви от азбуката в ред.

59
00:03:08,800 --> 00:03:13,960
>> Ние ще разгледаме втория индекса тогава,
един индекс, за Б. Като цяло, ако

60
00:03:13,960 --> 00:03:17,990
има някои азбуката C ние
може да се определи съответното място

61
00:03:17,990 --> 00:03:21,520
в деца масив, използвайки
изчисление по този начин.

62
00:03:21,520 --> 00:03:25,140
Ние би могъл да използва по-голям деца
масив, ако искахме да предложим поглед нагоре на

63
00:03:25,140 --> 00:03:28,380
ключове с по-широк диапазон от символи,
като цялата

64
00:03:28,380 --> 00:03:29,880
Настроите ASCII характер.

65
00:03:29,880 --> 00:03:32,630
>> В този случай, на показалеца
в нашата детска масив в

66
00:03:32,630 --> 00:03:34,320
Индекс на един не е нищожна.

67
00:03:34,320 --> 00:03:36,600
Така че ние ще продължим да търсим
до ключ баня.

68
00:03:36,600 --> 00:03:40,130
Ако някога сме се сблъска с нулев указател
на правилното място при децата

69
00:03:40,130 --> 00:03:43,230
масив, докато ние се премества възлите,
тогава ние ще трябва да се каже, че ние

70
00:03:43,230 --> 00:03:45,630
Не можах да намеря нищо за този ключ.

71
00:03:45,630 --> 00:03:49,370
>> Сега, ние ще вземем второто писмо на
Основният ни, A, и да продължи след

72
00:03:49,370 --> 00:03:52,400
указатели по този начин, докато ние
стигнете до края на нашия ключ.

73
00:03:52,400 --> 00:03:56,530
Ако стигнете до края на ключа, без да
удря всички задънени улици, нулеви указатели,

74
00:03:56,530 --> 00:03:59,730
какъвто е случаят тук, тогава можем само
Трябва да проверя още едно нещо.

75
00:03:59,730 --> 00:04:02,110
Дали това действително ключ
в речника?

76
00:04:02,110 --> 00:04:07,660
>> Ако е така, ние трябва да се намери стойност, както е
усмивка икона лице в нашата диаграма, където

77
00:04:07,660 --> 00:04:08,750
думата завършва.

78
00:04:08,750 --> 00:04:12,270
Ако има нещо друго, съхранява с
данните, а след това можем да го върнат.

79
00:04:12,270 --> 00:04:16,500
Например, ключовата зоологическата градина не е в
речник, въпреки че бихме могли да имаме

80
00:04:16,500 --> 00:04:19,810
достигнала края на този ключов, без изобщо да
удря нулев указател, докато ние

81
00:04:19,810 --> 00:04:21,089
превъртите през TRIE.

82
00:04:21,089 --> 00:04:25,436
>> Ако се опитаме да погледнем нагоре ключовата баня,
второ да индексира масив миналата възлова точка,

83
00:04:25,436 --> 00:04:28,750
съответстваща на буквата Н, би
са заемали нулев указател.

84
00:04:28,750 --> 00:04:31,120
Така баня не е в речника.

85
00:04:31,120 --> 00:04:34,800
И така Trie е уникален с това, ключовете
никога не са изрично съхранява в

86
00:04:34,800 --> 00:04:36,650
структурата на данните.

87
00:04:36,650 --> 00:04:38,810
Така че как можем да вмъкнете нещо
в Trie?

88
00:04:38,810 --> 00:04:41,780
>> Нека поставете ключа
зоологическа градина в нашата Trie.

89
00:04:41,780 --> 00:04:46,120
Не забравяйте, че една усмивка на лицето на възел
може да съответства на код за проста

90
00:04:46,120 --> 00:04:50,170
Булева стойност да се посочи, че зоологическа градина
е в речника или може

91
00:04:50,170 --> 00:04:53,710
съответства на допълнителна информация, която ние
Иска да се сдружават с ключовата зоологическата градина,

92
00:04:53,710 --> 00:04:56,860
както и определянето на
дума или нещо друго.

93
00:04:56,860 --> 00:05:00,350
В някои отношения, процесът да вмъкнете
нещо в Trie е подобен

94
00:05:00,350 --> 00:05:02,060
търсите нещо в Trie.

95
00:05:02,060 --> 00:05:05,720
>> Ще започнем с корен възел отново,
следните насоки, съответстващи

96
00:05:05,720 --> 00:05:07,990
буквите от нашите ключови.

97
00:05:07,990 --> 00:05:11,310
За щастие, ние бяхме в състояние да следват показалки
по целия път, докато стигнахме

98
00:05:11,310 --> 00:05:12,770
на края на ключа.

99
00:05:12,770 --> 00:05:16,480
Тъй като зоологическата градина е префикс на думата
увеличение, което е член на

100
00:05:16,480 --> 00:05:19,440
речник, ние не трябва да
разпредели нови възли.

101
00:05:19,440 --> 00:05:23,140
>> Можем да променя възлова точка показва, че
пътя на знаци, водещи до

102
00:05:23,140 --> 00:05:25,360
тя представлява ключова в нашия речник.

103
00:05:25,360 --> 00:05:28,630
Сега, нека се опитаме да поставите
ключов БАНЯ в TRIE.

104
00:05:28,630 --> 00:05:32,260
Ще започнем от корен възел
и следвайте отново указатели.

105
00:05:32,260 --> 00:05:35,620
Но в тази ситуация, ние удари мъртъв
края, преди да можем да стигнем до

106
00:05:35,620 --> 00:05:36,940
край на ключа.

107
00:05:36,940 --> 00:05:40,980
Сега, ние ще трябва да се разпределят някои нови
възли ще трябва да отделят един нов

108
00:05:40,980 --> 00:05:43,660
възел за всички останали
писмо на нашия ключ.

109
00:05:43,660 --> 00:05:46,740
>> В този случай, ние просто трябва
да се разпредели един нов възел.

110
00:05:46,740 --> 00:05:50,590
Тогава ще трябва да се направи индекс H
упоменете нов възел.

111
00:05:50,590 --> 00:05:54,070
Отново, ние може да промени възел към
посочва, че пътят на символи

112
00:05:54,070 --> 00:05:57,120
което води до това представлява
ключ в нашия речник.

113
00:05:57,120 --> 00:06:00,730
Нека да разсъждаваме за асимптотичната
сложност на процедурите ни за тях

114
00:06:00,730 --> 00:06:02,110
две операции.

115
00:06:02,110 --> 00:06:06,420
>> Забелязваме, че и в двата случая броят
на стъпки от нашия алгоритъм отне беше

116
00:06:06,420 --> 00:06:09,470
пропорционално на броя на
буквите в думата.

117
00:06:09,470 --> 00:06:10,220
Точно така.

118
00:06:10,220 --> 00:06:13,470
Когато искате да търсите дума в
Trie просто трябва да превъртите през

119
00:06:13,470 --> 00:06:17,100
буквите една по една, докато вие или
стигнат до края на думата или

120
00:06:17,100 --> 00:06:19,060
удари задънена улица в TRIE.

121
00:06:19,060 --> 00:06:22,470
>> А когато искате да вмъкнете ключов
стойност чифт в Trie помощта на

122
00:06:22,470 --> 00:06:26,250
процедура ние обсъдихме, в най-лошия случай
ще ви разпределяне на нов възел

123
00:06:26,250 --> 00:06:27,550
за всяка буква.

124
00:06:27,550 --> 00:06:31,290
И ние ще приемем, че разпределянето
е постоянна работа време.

125
00:06:31,290 --> 00:06:35,850
Така че, ако приемем, че дължината на ключа е
ограничена от фиксирана постоянно, както

126
00:06:35,850 --> 00:06:39,400
вмъкване и погледнете нагоре са постоянни
операции за това срок Trie.

127
00:06:39,400 --> 00:06:42,930
>> Ако ние не правим това предположение, че
дължината на ключа е ограничено с фиксиран

128
00:06:42,930 --> 00:06:46,650
константа, след това вкарване и погледнете нагоре,
в най-лошия случай, са линейни в

129
00:06:46,650 --> 00:06:48,240
дължина на ключа.

130
00:06:48,240 --> 00:06:51,800
Обърнете внимание, че броят на елементи, съхранени
в TRIE не се отразява на външния вид на

131
00:06:51,800 --> 00:06:52,820
или време вмъкване.

132
00:06:52,820 --> 00:06:55,360
Това е повлияно само от
дължина на ключа.

133
00:06:55,360 --> 00:06:59,300
>> За разлика от това, добавяне на записи, да речем,
хеш таблицата са склонни да направят

134
00:06:59,300 --> 00:07:01,250
бъдещата потърсим по-бавно.

135
00:07:01,250 --> 00:07:04,520
Макар че това може да звучи привлекателно на пръв поглед,
ние трябва да имаме предвид, че

136
00:07:04,520 --> 00:07:08,740
благоприятно асимптотичната сложност не
означава, че на практика данните

137
00:07:08,740 --> 00:07:11,410
структура е задължително
безупречна.

138
00:07:11,410 --> 00:07:15,860
Ние също трябва да се счита, че за да съхраните
дума в Trie ние трябва в най-лошия

139
00:07:15,860 --> 00:07:19,700
случай, редица възли пропорционална
на дължината на самата дума.

140
00:07:19,700 --> 00:07:21,880
>> Опитва склонни да използват много пространство.

141
00:07:21,880 --> 00:07:25,620
Това е в контраст с хеш таблица,
където ние само трябва един нов възел към

142
00:07:25,620 --> 00:07:27,940
съхранявате някои двойка ключове стойност.

143
00:07:27,940 --> 00:07:31,370
Сега, отново на теория, голямо пространство
консумация не изглежда като една голяма

144
00:07:31,370 --> 00:07:34,620
се справят, особено предвид факта, че съвременната
компютри имат гигабайта и

145
00:07:34,620 --> 00:07:36,180
гигабайта памет.

146
00:07:36,180 --> 00:07:39,200
Но се оказва, че ние все още имаме
да се притеснявате за използването на паметта и

147
00:07:39,200 --> 00:07:42,540
организация заради
производителност, тъй като съвременните компютри

148
00:07:42,540 --> 00:07:46,960
разполагат с механизми, съществуващи в рамките на
качулка, за да се ускори достъп до паметта.

149
00:07:46,960 --> 00:07:51,180
>> Но тези механизми работят най-добре, когато
памет достъпи са направени в компактен

150
00:07:51,180 --> 00:07:52,810
региони или зони.

151
00:07:52,810 --> 00:07:55,910
И възли на Trie може да пребивават
навсякъде в тази купчина.

152
00:07:55,910 --> 00:07:58,390
Но това са компромиси
че трябва да се помисли.

153
00:07:58,390 --> 00:08:01,440
>> Не забравяйте, че при избора на данни
структура за определена задача, ние

154
00:08:01,440 --> 00:08:04,420
трябва да мислим за това, което видове
операции структурата на данните трябва да

155
00:08:04,420 --> 00:08:07,140
подкрепа и колко изпълнение
на всеки от тези

156
00:08:07,140 --> 00:08:09,080
оперативни въпроси към нас.

157
00:08:09,080 --> 00:08:11,300
Тези операции могат дори
простира отвъд просто

158
00:08:11,300 --> 00:08:13,430
Основният поглед нагоре и вмъкване.

159
00:08:13,430 --> 00:08:17,010
Да предположим, че ние искахме да се приложи един вид
на авто-пълна функционалност, много

160
00:08:17,010 --> 00:08:18,890
като търсачката Google прави.

161
00:08:18,890 --> 00:08:22,210
Това е, върнете всички ключове и
потенциално ценности, които

162
00:08:22,210 --> 00:08:24,130
има даден префикс.

163
00:08:24,130 --> 00:08:27,050
>> A Trie е уникално полезно
за тази операция.

164
00:08:27,050 --> 00:08:29,890
Това е ясно, за да превъртате през
на TRIE за всеки един от героите на

165
00:08:29,890 --> 00:08:30,950
префикса.

166
00:08:30,950 --> 00:08:33,559
Само като погледнете нагоре операция,
бихме могли да следват показалки

167
00:08:33,559 --> 00:08:35,400
знак по знак.

168
00:08:35,400 --> 00:08:38,659
След това, когато пристигнем в края на
префикс, бихме могли да превъртите чрез на

169
00:08:38,659 --> 00:08:42,049
останалата част от структурата на данните
тъй като всеки от бутоните отвъд

170
00:08:42,049 --> 00:08:43,980
тази точка има префикс.

171
00:08:43,980 --> 00:08:47,670
>> Това е също така лесно да се получи тази обява
по азбучен ред, тъй като

172
00:08:47,670 --> 00:08:50,970
елементи на деца масива
са подредени по азбучен ред.

173
00:08:50,970 --> 00:08:54,420
Така че, да се надяваме, че ще обмисли
даване опитва да опитате.

174
00:08:54,420 --> 00:08:56,085
Аз съм Кевин Schmid, и това е CS50.

175
00:08:56,085 --> 00:08:58,745

176
00:08:58,745 --> 00:09:00,790
>> Ах, това е началото
от спада.

177
00:09:00,790 --> 00:09:01,350
Съжалявам.

178
00:09:01,350 --> 00:09:01,870
Извинете.

179
00:09:01,870 --> 00:09:02,480
Извинете.

180
00:09:02,480 --> 00:09:03,130
Извинете.

181
00:09:03,130 --> 00:09:03,950
>> Ненужното четири.

182
00:09:03,950 --> 00:09:04,360
Аз съм вън.

183
00:09:04,360 --> 00:09:05,280
Извинете.

184
00:09:05,280 --> 00:09:06,500
Извинете.

185
00:09:06,500 --> 00:09:07,490
Извинете.

186
00:09:07,490 --> 00:09:12,352
Съжалявам за вземане на лицето, което
трябва да редактирате тази побърка.

187
00:09:12,352 --> 00:09:13,280
>> Извинете.

188
00:09:13,280 --> 00:09:13,880
Извинете.

189
00:09:13,880 --> 00:09:15,080
Извинете.

190
00:09:15,080 --> 00:09:15,680
Извинете.

191
00:09:15,680 --> 00:09:16,280
>> SPEAKER 1: Браво.

192
00:09:16,280 --> 00:09:17,530
Това е наистина добре направено.

193
00:09:17,530 --> 00:09:18,430