Кевин ШМИД: Иногда, при строительстве Программа, вы можете использовать Структура данных известен как словарь. Словарь Карты ключи, которые обычно строки, до значений, Интс, символы, указатель на какой-то предмет, все, что хотим. Это просто, как обычные словари что карта слова через определений. 

Словари дают нам Способность хранить информацию ассоциируется с чем-то и посмотреть его позже. Так как же мы на самом деле реализовать словарь, скажем, С-кода, мы можем использовать в одной из наших программ? Ну, есть много способов, которыми мы могли бы реализовать словарь. 

С одной стороны, мы могли бы использовать массив, что мы динамически изменять размеры или мы могли бы использовать связанный список, хэш-таблицы или бинарное дерево. Но что бы мы ни выбрали, мы должны помнить о эффективности и Производительность подсистемы. Мы должны думать о алгоритма, используемого вставить и посмотреть элементы в наша структура данных. 

А сейчас давайте предположим, что мы хотите использовать строки в качестве ключей. Давайте поговорим о одной возможности, структура данных называется синтаксического дерева. Итак, вот визуальное представление из виде дерева. 

Как картина предполагает, виде дерева это структура данных дерева с узлы связаны между собой. Мы видим, что есть четко корень узел с несколько ссылок распространяется на других узлов. Но то, что каждый узел состоит? Если предположить, что мы хранения ключей только с буквы алфавита, и мы не заботимся о капитализации, вот определение узла, хватит. 

Объект, тип которого является структура узел состоит из двух частей называются данными и детей. Мы оставили часть данных как комментарий должны быть заменены составляющей Декларация, когда структура узел включены в программу C. Часть данных узла может быть Логическое значение, чтобы указать, является ли или не узел, представляющий собой завершение из словаря ключа или это может быть Строка, представляющая определение слова в словаре. 

Мы будем использовать смайлик для обозначения когда данные присутствуют в узле. Есть 26 элементов в нашей дети массив, один индекс за буквы. Мы увидим значение это в ближайшее время. 

Давайте внимательнее посмотрим корневого узла в нашей схеме, которая не имеет данных связанные с ним, как указано отсутствие смайлик в часть данных. Стрелки, идущие от частей дети массива представляют не-узел указатели на другие узлы. Например, стрелка проходит от второй элемент детей представляет букву B в ключе словаря. И в более широком диаграмме мы называем его с В. 

Отметим, что в большей схеме, когда мы нарисовать указатель на другой узел, это Не имеет значения, где стрелка отвечает, что другой узел. Наш словарь образец синтаксического дерева содержит два слова, что и зум. Давайте рассмотрим пример глядя данные для ключа. 

Предположим, мы хотим посмотреть соответствующее значение для ключевого ванной. Мы начнем наш взгляд вверх в корневом узле. Тогда мы будем принимать первую букву нашей Ключ, В и найти соответствующий пятно в нашей детской массива. Обратите внимание, что существует ровно 26 мест в массиве, по одному для каждой буквы алфавит. И мы будем иметь пятна представляют буквы алфавита по порядку. 

Мы рассмотрим второй индекс, то, Индекс один, для В. В общем, если мы есть алфавитный символ с мы может определить соответствующую точку в массиве детей с использованием Расчет, как это. Мы могли бы использовать больший детей Массив, если мы хотели предложить Смотри выше клавиши с более широким диапазоном символов, таких как всей Набор символов ASCII. 

В этом случае указатель в наших детях массива в Индекс один не является нулевым. Поэтому мы будем продолжать искать до ключевого ванной. Если мы когда-либо сталкивались нулевой указатель на должном месте в детей Массив в то время как мы пересекли узлы, то мы должны будем сказать, что мы не мог найти ничего для этого ключа. 

Теперь, мы будем принимать вторую букву наш ключ, и продолжайте следовать указатели на этом пути пока мы дойдете до конца наш ключ. Если мы достигаем конца ключа без поражая любые тупиков, нулевых указателей, как это имеет место здесь, то мы только должны проверить еще одну вещь. Это ключ на самом деле в словаре? 

Если это так, мы должны найти значение, а смайлик значок лицо в нашей диаграмме, где слово заканчивается. Если есть что-то еще сохраняются с данные, то мы можем вернуть его. Например, ключ зоопарка не находится в словарь, хотя мы могли бы иметь подошел к концу этого ключа, даже не попав в пустой указатель, в то время как мы перебора синтаксического дерева. 

Если бы мы попытались посмотреть ключевую ванну, второй индекса массива в прошлом узла, соответствующий буквой H, будет провели нулевой указатель. Так ванна не в словаре. И так синтаксического дерева уникален тем, что ключей никогда не явно хранится в Структура данных. Так как же нам вставить что-то в виде дерева? 

Давайте вставьте ключ зоопарк в наш синтаксического дерева. Помните, что смайлик в узле может соответствовать в коде для простой Логическое значение, чтобы указать, что зоопарк есть в словаре, или это мог соответствуют получения дополнительной информации, что мы хотите связать с ключевым зоопарке, как определение слово или что-то еще. В некотором смысле, процесс вставить что-то в виде дерева подобна глядя что-то в виде дерева. 

Мы начнем с корневого узла снова, Следующие указатели, соответствующие буквы наш ключ. К счастью, мы были в состоянии следовать указатели на всем пути, пока мы не достигли конец ключа. Поскольку зоопарк является префиксом слова зум, который является членом словарь, мы не должны выделить каких-либо новых узлов. 

Мы можем изменить узел, чтобы указать, что путь персонажей, ведущих к она представляет собой ключ в нашем словаре. Теперь, давайте попробуем вставки Ключ БАНЯ в синтаксического дерева. Мы начнем в корневом узле и следуйте указатели снова. Но в этой ситуации, мы попали в мертвых конец до мы в состоянии добраться до конец ключа. Теперь мы должны выделить некоторые новые узлы потребуется выделить один новый узел для каждого оставшегося Письмо нашим ключом. 

В этом случае, мы просто должны выделить один новый узел. Тогда мы должны будем сделать индекс H ссылайтесь на этот новый узел. Еще раз, мы можем изменить узел свидетельствуют о том, что путь символов ведущая к нему представляет собой Ключевым в нашем словаре. Давайте рассуждать о асимптотическое Сложность наших процедур для этих две операции. 

Заметим, что в обоих случаях число из шаги наш алгоритм взял было пропорциональна количеству буквы в ключевое слово. Это верно. Если вы хотите искать слово в синтаксического дерева нужно просто перебирать буквы по одному, пока вы либо дойдете до конца слова или зашли в тупик в синтаксического дерева. 

И когда вы хотите вставить ключ значение пары в виде дерева с помощью Процедура мы обсуждали, в худшем случае будет у вас выделения нового узла для каждой буквы. И мы будем считать, что распределение постоянная работа время. Так что, если мы предполагаем, что длина ключа ограничен фиксированной константой, как вставка и посмотреть постоянны Время операции для виде дерева. 

Если мы не будем делать это предположение, что длина ключа ограничена фиксированным постоянная, то вставка и посмотрите вверх, в худшем случае, линейных по Длина ключа. Обратите внимание, что количество элементов хранятся в синтаксического дерева не влияет на внешний вид до или время вставки. Это только влияние Длина ключа. 

С другой стороны, добавление элементов, скажем, хэш-таблицу приводит к тому, Будущее посмотреть медленнее. Хотя это может показаться привлекательным в первую очередь, мы должны иметь в виду, что благоприятная асимптотической сложности не означает, что на практике данные Структура обязательно безупречным. Мы также должны учитывать, что для хранения слово в виде дерева, мы должны, в худшем так, число узлов пропорциональна длине самого слова. 

Пытается как правило, используют много места. Это в отличие от хэш-таблице, где нам нужен только один новый узел к хранить некоторые ключевые ценности пару. Теперь снова в теории, большое пространство Расход не кажется, что большая дело, особенно учитывая, что современные компьютеры имеют гигабайт и гигабайт памяти. Но оказывается, что у нас еще есть беспокоиться об использовании памяти и организация ради производительность, так как современные компьютеры внедрить механизмы под капот, чтобы ускорить доступ к памяти. 

Но эти механизмы работают лучше, когда доступ к памяти выполнены в компактной регионы или районы. И узлы виде дерева может находиться в любом месте в этой куче. Но это компромиссы что мы должны рассмотреть. 

Помните, что при выборе данных Структура для определенной задачи, мы должны думать о том, какие из операции структура данных должна поддержка и сколько производительность каждого из тех, операции имеет значение для нас. Эти операции могут даже выходят за рамки просто основной вид и вставки. Предположим, мы хотим реализовать своего рода из автозаполнения функциональность, намного как поисковая система Google делает. То есть, вернуть все ключи и потенциально ценности, которые есть заданного префикса. 

Синтаксического дерева однозначно полезно Для выполнения этой операции. Это просто для перебора синтаксического дерева для каждого символа префикс. Так же, как смотреть вверх операции, мы могли следовать указатели посимвольно. Потом, когда мы приходим в конце префикс, мы могли перебора Остальная часть структуры данных так как любой из ключей за эта точка имеют префикс. 

Это также легко получить этот листинг в алфавитном порядке, так как Элементы массива детей располагаются в алфавитном порядке. Так, надеюсь, вы рассмотреть предоставление пытается попробовать. Я Кевин Шмид, и это CS50. 

Ах, это начало упадка. Мне очень жаль. Извините. Извините. Извините. 

Удар четыре. Я ухожу. Извините. Извините. Извините. Извините за человека, который должен изменить эту сойти с ума. 

Извините. Извините. Извините. Извините. 

Выступающий 1: Молодцы. Это было действительно хорошо сделано.