[Играет музыка] ДАГ Lloyd: Так мы были вскоре может стать и ближе, что Святой Грааль данных структуры, который мы можем вставить в, исключить и посмотреть в постоянное время. Правильно. Это своего рода цели. Мы хотим, чтобы быть в состоянии сделать вещи очень, очень быстро. 

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

Таким образом, для массива, например, Ключ индекс элемента массива или Местонахождение на карте 0 или 1 массив и так далее. И значение данных что существует в этом месте. Так что хранится в массиве 0? Что хранится в массиве 1 по сравнению с просто 0 и 1, которые будут ключи. 

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

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

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

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

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

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

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

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

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

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

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

А внутри этих данных Структура есть две части. Мы собираемся хранить наименование университета. И мы собираемся хранить массив указателей на другие узлы того же типа. Так, опять же, это такого рода понятия везде мы, мы на 10 можно места, которые мы можем пойти. Если мы видим 0, мы идем по этой отрасли. Если мы видим, что 1, эта отрасль, и так далее, и так далее, и так далее. Если мы говорим, 9, спускаемся эту ветку. Таким образом, в каждой точке перехода, мы можем пойти 10 возможных мест. Таким образом, каждый узел должен содержать 10 указателей на другие узлы, до 10 других узлов. 

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

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

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

И массив из 10 указателей. И сейчас, мы только есть 1 узел в этом синтаксического дерева. Там нет ничего в нем. Таким образом, все 10 из тех, указатели указывают на нуль. Это то, что красный означает. 

Давайте вставить строку в Гарвардский. Давайте вставить университет Гарвардский в этом синтаксического дерева, которые была основана в 1636 в год. Мы хотим использовать ключ, 1636, чтобы сказать нам, где мы собираетесь хранить в Гарвард в синтаксического дерева. Теперь, как мы могли бы это сделать? 

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

Куда мы, вероятно, хотите чтобы пойти, если ключ 1636? Там действительно два варианта. Правильно. Мы можем построить ключ из справа налево и начать с 6. Или мы могли бы построить ключ из слева направо и начать с 1. 

Это, вероятно, более интуитивное, как человеческого существа чтобы понять, мы только налево направо. И поэтому, если я хочу, чтобы вставить Гарвардский в этом синтаксического дерева, Я, вероятно, хотите, чтобы начать от начиная с корневого, глядя на мои 10 вариантов передо мной, и сказал Я хочу, чтобы идти по пути 1. ХОРОШО. 

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

Так что я в основном нахожусь в точка, где я стою в корне дерева или Trie и есть 10 филиалов. Но каждая ветвь имеет Ворота перед ним. Правильно. Потому что нет ничего другого, есть. Нет безопасный проход. Это означает, что нет ничего вниз любой из этих ветвей. Если я хочу, чтобы начать строительство то, я хочу, чтобы удалить ворота. Я хочу, чтобы удалить ворота перед номером 1. И я хочу, чтобы спуститься, что. И я хочу, чтобы построить другое место для меня, чтобы пойти. 

И вот что я сделал здесь. Так что 1 больше не указывает на нуль. Я сказал, что это безопасно спуститься здесь и сейчас. Я построил другой узел. И когда я добираюсь до этого узла, я есть другое решение, чтобы сделать. Где я буду идти дальше? 

Ну, я уже ушел вниз 1. Так что теперь я, вероятно, хотите, чтобы спуститься 6. Правильно. Опять же, у меня есть 10 мест я могу выбрать. Так пусть теперь спустимся номер 6. Так что я очистить ворота перед номером 6. И я иду туда. И я построить еще один узел. И я достиг другую точку перехода. 

Опять же, у меня есть 10 вариантов для того, где я могу пойти. Я переехал от 1 до 6. Так что теперь я, наверное, хотите, чтобы перейти к 3. 3, нет нигде я могу пойти. Так что я, чтобы расчистить путь и построить себе новое пространство. А потом от 3, где я хочу пойти? Я хочу, чтобы спуститься 6. 

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

Это выделены желтым цветом. Вот где я в настоящее время нахожусь. Мой ключ делается. Я исчерпал каждую позицию в моей ключа. Так что я не могу идти дальше. Так в этой точке, все, что я действительно нужно сделать, это сказать, хорошо. Это вроде как смотрит в землю, если вы предусматривающие сами, как такого рода пути с различными соединениями. Сортировать глядя и вроде окраска распылением Гарвард на земле. Это имя этого. Знайте, что это то, что в этом месте. Если мы стартуем из корня и идем вниз 1, а затем 6, а затем 3, а затем 6, где мы? Ну, если мы посмотрим вниз и мы видим, Гарвард, затем мы знаем, что Гарвард был основана в 1636 году на основе, как мы реализации этой структуры данных. Так что, надеюсь, был прост. Мы собираемся сделать еще два вставки. И, надеюсь, это поможет в чтобы это было сделано в два раза больше. 

Теперь, давайте вставить другой университет. Давайте вставить Йель в этом синтаксического дерева. Йельский была основана в 1701 году. Таким образом, мы начнем на корень, как мы всегда делаем. И мы должны установить указатель обхода. Мы собираемся использовать это, чтобы двигаться через. Первое, что мы хотим, чтобы сделать, это пойти по пути 1. Это первая цифра нашего ключа. К счастью, однако, мы не должны делать любую работу на этот раз. 1-путь уже был очищен. Я очистил его ранее, когда я вставлял в Гарвард в 1636 году. Так что я могу смело двигаться вниз 1 и только туда. Если может двигаться вниз 1. 

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

Так что теперь я переехал 1, а затем 7. А теперь обратите внимание, я вроде из этой новой подотрасли. Правильно. Все остальное от 16 , я не волнует. Я не делаю ничего 16. Я делаю 17 вещей. 

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

Так что я таНос новый узел и имеют точку 0 там. А потом еще раз, я таНос Новый узел и имеют одну точку там. Опять же, я исчерпал свой ключ, 1701. Так я смотрю вниз, и я распылить краску Йель. Это имя этого узла. 

И вот теперь, если я когда-нибудь понадобится, чтобы увидеть, если Йельском университете в этом синтаксического дерева, я начинаю в корне, Я спускаюсь 1701, и смотреть вниз. И если я вижу Yale спрей окрашены на землю, то Я знаю, Йельский существует в этом синтаксического дерева. Давайте сделаем еще один. Давайте вставить Дартмут в это Trie, которая была основана в 1769 году. 

Начало в корне снова. Моя первая цифра моего ключа 1. Я могу с уверенностью двигаться по этому пути. Это уже существует. Следующая цифра моего ключа 7. Я могу с уверенностью двигаться по этому пути. Она существует, как хорошо. 

Мой следующий 6. Отсюда, откуда настоящее время я в желтый есть в этой средней узла, 6 В настоящее время выключено. Если я хочу, чтобы идти по этому пути, Я должен построить сам. Так что я буду таНос новый узел и имеют 6 пункт там. А потом, опять же, я пылающий новые тропы здесь. 

Так что я таНос новый узел, так что из что node-- путь Количество 9-- и то сейчас если я путешествую 1769, и я с нетерпением вниз. Там нет ничего о себе спрей окрашены там. Я могу написать Дартмут. И я вставил Дартмут в синтаксического дерева. 

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

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

Так что давайте искать Гарвардский в этом синтаксического дерева. Мы начинаем в корне. И, опять же, мы собираемся создать указатель обхода сделать наши шаги для нас. Из корня мы знаем, что Первое место мы должны пойти 1, мы можем сделать? Да мы можем. Если безопасно существует. Мы можем пойти туда. 

Теперь, следующее место мы должны пойти 6. Существует ли путь 6 отсюда? Да, это так. Мы можем спуститься 6 путь. И мы в конечном итоге здесь. 

Можем ли мы пойти вниз 3 пути отсюда? Ну, как выясняется, да, тоже существует. И мы можем получить на пути от 6 здесь? Да мы можем. 

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

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

Таким образом, вы всегда должны пройти весь путь, а затем если бы вы были в состоянии успешно пройти весь путь, смотреть вниз и сделать одну окончательное подтверждение. Это то, что я ищу? Ну, я смотрю вниз после запуска в верхней и собирается 1636. Я смотрю вниз. Я вижу в Гарвард. Так что, да, мне это удалось. Что делать, если то, что я ищу не в синтаксического дерева, хотя. Что делать, если я ищу Принстоне, которая была основана в 1746 году. И так становится 1746 мой ключ для навигации по синтаксического дерева. Ну, я начинаю в корне. И в первую очередь я хочу чтобы спускается путь 1. Могу ли я это сделать? Да, я могу. 

Могу ли я перейти вниз по 7 пути оттуда? Да, я могу. Это тоже существует. Но я могу пойти по пути 4 из здесь? Это как задать вопрос, может Я исхожу вниз, что скверик что я выделил желтым? Там ничего нет. Правильно. 

Там нет способа вперед по пути 4. Если Принстон был в этом синтаксического дерева, что 4 был бы очищен для нас уже. И поэтому на данном этапе мы зашли в тупик. Мы не можем идти дальше. И таким образом, мы можем сказать окончательно, нет. Принстон не существует в этом синтаксического дерева. 

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

Каждый раз, когда мы хотели вставить что-то в синтаксического дерева, мы должны сделать 4 перемещается, возможно, mallocing некоторые вещи по пути. Но, как мы видели, когда мы вставили Дартмут в синтаксического дерева, Иногда некоторые из пути уже может быть очищена для нас. И так как наш Trie становится все больше и больше, у нас есть меньше работы каждый раз, вставить новые вещи потому что мы уже построено много промежуточный филиалы по пути. Если мы только когда-либо должны смотреть на 4 вещи, 4 это просто константа. Мы действительно вид приближается постоянная вставки раз и постоянное поиск время. Компромисс, конечно, в том, что это Trie, как вы, вероятно, может сказать, огромный. Каждый из этих узлов занимает много места. 

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

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