Кевін ШМІД: Іноді, при будівництві Програма, ви можете використовувати Структура даних відомий як словник. Словник Карти ключі, які зазвичай рядки, до значень, Інтс, символи, покажчик на якийсь предмет, все, що хочемо. Це просто, як звичайні словники що карта слова через визначень. 

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

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

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

Як картина припускає, вигляді дерева це структура даних дерева з вузли пов'язані між собою. Ми бачимо, що є чітко корінь вузол з кілька посилань поширюється на інших вузлів. Але те, що кожен вузол складається? Якщо припустити, що ми зберігання ключів тільки з букви алфавіту, і ми не дбаємо про капіталізацію, от визначення вузла, вистачить. 

Об'єкт, тип якого є структура вузол складається з двох частин називаються даними і дітей. Ми залишили частину даних як коментар повинні бути замінені складової Декларація, коли структура вузол включені в програму C. Частина даних вузла може бути Логічне значення, щоб вказати, чи є чи НЕ вузол, який представляє собою завершення зі словника ключа або це може бути Рядок, що представляє визначення слова в словнику. 

Ми будемо використовувати смайлик для позначення коли дані присутні в вузлі. Є 26 елементів у нашій діти масив, один індекс за літери. Ми побачимо значення це найближчим часом. 

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

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

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

Ми розглянемо другий індекс, то, Індекс один, для В. Загалом, якщо ми є алфавітний символ з ми може визначити точку в масиві дітей з використанням Розрахунок, як це. Ми могли б використовувати більший дітей Масив, якщо ми хотіли запропонувати Дивись вище клавіші з більш широким діапазоном символів, таких як всієї Набір символів ASCII. 

У цьому випадку покажчик в наших дітях масиву в Індекс один не є нульовим. Тому ми будемо продовжувати шукати до ключового ванною. Якщо ми коли-небудь стикалися нульовий покажчик на належному місці в дітей Масив в той час як ми перетнули вузли, то ми повинні будемо сказати, що ми не міг знайти нічого для цього ключа. 

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

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

Якби ми спробували подивитися ключову ванну, другий індексу масиву в минулому вузла, відповідний буквою H, буде провели нульовий покажчик. Так ванна не в словнику. І так синтаксичного дерева унікальний тим, що ключів ніколи не явно зберігається в Структура даних. Так як же нам вставити щось у вигляді дерева? 

Давайте вставте ключ зоопарк в наш синтаксичного дерева. Пам'ятайте, що смайлик у вузлі може відповідати в коді для простої Логічне значення, щоб вказати, що зоопарк є в словнику, або це міг відповідають отримання додаткової інформації, що ми хочете пов'язати з ключовим зоопарку, як визначення слово або щось ще. У певному сенсі, процес вставити щось у вигляді дерева подібна дивлячись щось у вигляді дерева. 

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

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

У цьому випадку, ми просто повинні виділити один новий вузол. Тоді ми повинні будемо зробити індекс H посилайтеся на цей новий вузол. Ще раз, ми можемо змінити вузол свідчать про те, що шлях символів веде до нього являє собою Ключовим у нашому словнику. Давайте міркувати про асимптотическое Складність наших процедур для цих дві операції. 

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

І коли ви хочете вставити ключ значення пари у вигляді дерева за допомогою Процедура ми обговорювали, в гіршому випадку буде у вас виділення нового вузла для кожної літери. І ми будемо вважати, що розподіл постійна робота час. Так що, якщо ми припускаємо, що довжина ключа обмежений фіксованою константою, як вставка і подивитися постійні Час операції для вигляді дерева. 

Якщо ми не будемо робити це припущення, що довжина ключа обмежена фіксованим постійна, то вставка і подивіться вгору, в гіршому випадку, лінійних по Довжина ключа. Зверніть увагу, що кількість елементів зберігаються в синтаксичного дерева не впливає на зовнішній вигляд до або час вставки. Це тільки вплив Довжина ключа. 

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

Намагається як правило, використовують багато місця. Це на відміну від хеш-таблиці, де нам потрібен тільки один новий вузол до зберігати деякі ключові цінності пару. Тепер знову в теорії, великий простір Витрата не здається, що більша справа, особливо враховуючи, що сучасні комп'ютери мають гігабайт і гігабайт пам'яті. Але виявляється, що у нас ще є турбуватися про використання пам'яті і організація заради продуктивність, так як сучасні комп'ютери впровадити механізми під капот, щоб прискорити доступ до пам'яті. 

Але ці механізми працюють краще, коли доступ до пам'яті виконані в компактній регіони чи райони. І вузли вигляді дерева може перебувати в будь-якому місці в цій купі. Але це компроміси що ми повинні розглянути. 

Пам'ятайте, що при виборі даних Структура для певної задачі, ми повинні думати про те, які з операції структура даних повинна підтримка і скільки продуктивність кожного з тих, операції має значення для нас. Ці операції можуть навіть виходять за рамки просто основний вид і вставки. Припустимо, ми хочемо реалізувати свого роду з автозаповнення функціональність, набагато як пошукова система Google робить. Тобто, повернути всі ключі і потенційно цінності, які є заданого префікса. 

Синтаксичного дерева однозначно корисно Для виконання цієї операції. Це просто для перебору синтаксичного дерева для кожного символу префікс. Так само, як дивитися вгору операції, ми могли слідувати покажчики посимвольний. Потім, коли ми приходимо в кінці префікс, ми могли перебору Інша частина структури даних так як будь-який з ключів за ця точка мають префікс. 

Це також легко отримати цей лістинг в алфавітному порядку, так як Елементи масиву дітей розташовуються в алфавітному порядку. Так, сподіваюся, ви розглянути надання намагається спробувати. Я Кевін Шмід, і це CS50. 

Ах, це початок занепаду. Мені дуже шкода. Вибачте. Вибачте. Вибачте. 

Удар чотири. Я йду. Вибачте. Вибачте. Вибачте. Вибачте за людину, яка повинен змінити цю збожеволіти. 

Вибачте. Вибачте. Вибачте. Вибачте. 

Виступаючий 1: Молодці. Це було дійсно добре зроблено.