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

2
00:00:07,700 --> 00:00:10,890
>> Кевін ШМІД: Іноді, при будівництві
Програма, ви можете використовувати

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
Так як же ми насправді реалізувати
словник, скажімо, С-коду, ми можемо

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
Давайте поговоримо про однієї можливості,
структура даних називається синтаксичного дерева.

20
00:01:07,290 --> 00:01:11,210
Отже, ось візуальне уявлення
з вигляді дерева.

21
00:01:11,210 --> 00:01:14,590
>> Як картина припускає, вигляді дерева
це структура даних дерева з

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
І в ширшому діаграмі
ми називаємо його з В.

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
Наш словник зразок синтаксичного дерева містить
два слова, що і зум.

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
Тоді ми будемо приймати першу літеру нашої
Ключ, В і знайти відповідний

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
є алфавітний символ з ми
може визначити точку

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
>> Тепер, ми будемо приймати другу букву
наш ключ, і продовжуйте слідувати

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
перебору синтаксичного дерева.

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

83
00:04:25,436 --> 00:04:28,750
відповідний буквою H, буде
провели нульовий покажчик.

84
00:04:28,750 --> 00:04:31,120
Так ванна не в словнику.

85
00:04:31,120 --> 00:04:34,800
І так синтаксичного дерева унікальний тим, що ключів
ніколи не явно зберігається в

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

87
00:04:36,650 --> 00:04:38,810
Так як же нам вставити щось
у вигляді дерева?

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

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
У певному сенсі, процес вставити
щось у вигляді дерева подібна

94
00:05:00,350 --> 00:05:02,060
дивлячись щось у вигляді дерева.

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
Тепер, давайте спробуємо вставки
Ключ БАНЯ в синтаксичного дерева.

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
Якщо ви хочете шукати слово в
синтаксичного дерева потрібно просто перебирати

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

120
00:06:17,100 --> 00:06:19,060
зайшли в глухий кут у синтаксичного дерева.

121
00:06:19,060 --> 00:06:22,470
>> І коли ви хочете вставити ключ
значення пари у вигляді дерева за допомогою

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
вставка і подивитися постійні
Час операції для вигляді дерева.

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

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
Ми також повинні враховувати, що для зберігання
слово у вигляді дерева, ми повинні, в гіршому

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
І вузли вигляді дерева може перебувати
в будь-якому місці в цій купі.

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
>> Синтаксичного дерева однозначно корисно
Для виконання цієї операції.

164
00:08:27,050 --> 00:08:29,890
Це просто для перебору
синтаксичного дерева для кожного символу

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
Я Кевін Шмід, і це 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
>> Виступаючий 1: Молодці.

192
00:09:16,280 --> 00:09:17,530
Це було дійсно добре зроблено.

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