[Грає музика] ДАГ 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 на рік. Ми хочемо використовувати ключ, Тисячу шістсот тридцять шість, щоб сказати нам, де ми збираєтеся зберігати в Гарвард в синтаксичного дерева. Тепер, як ми могли б це зробити? 

Це може виглядати приблизно так. Ми починаємо в корені. І у нас є ці 10 місць, ми можемо йти. Корінь, як і будь інший вузол синтаксичного дерева. Є 10 місць ми можемо перейти від тут. 

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

Це, ймовірно, більш інтуїтивне, як людської істоти щоб зрозуміти, ми тільки наліво направо. І тому, якщо я хочу, щоб вставити Гарвардський в цьому синтаксичного дерева, Я, ймовірно, хочете, щоб почати від починаючи з кореневого, дивлячись на мої 10 варіантів переді мною, і сказав Я хочу, щоб йти шляхом 1. ДОБРЕ. 

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

Так що я в основному перебуваю в точка, де я стою в корені дерева або Trie і є 10 філій. Але кожна гілка має Ворота перед ним. Право. Тому що немає нічого іншого, є. Немає безпечний прохід. Це означає, що немає нічого вниз будь-який з цих гілок. Якщо я хочу, щоб почати будівництво то, я хочу, щоб видалити ворота. Я хочу, щоб видалити ворота перед номером 1. І я хочу, щоб спуститися, що. І я хочу, щоб побудувати інше місце для мене, щоб піти. 

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

Ну, я вже пішов вниз 1. Так що тепер я, ймовірно, хочете, щоб спуститися 6. Право. Знову ж, у мене є 10 місць я можу вибрати. Так нехай тепер спустимося номер 6. Так що я очистити ворота перед номером 6. І я йду туди. І я побудувати ще один вузол. І я досяг іншу точку переходу. 

Знову ж, у мене є 10 варіантів для того, де я можу піти. Я переїхав від 1 до 6. Так що тепер я, напевно, хочете, щоб перейти до 3. 3, немає ніде я можу піти. Так що я, щоб розчистити шлях і побудувати собі новий простір. А потім від 3, де я хочу піти? Я хочу, щоб спуститися 6. 

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

Це виділені жовтим кольором. Ось де я в даний час перебуваю. Мій ключ робиться. Я вичерпав кожну позицію в моїй ключа. Так що я не можу йти далі. Так в цій точці, все, що я дійсно потрібно зробити, це сказати, добре. Це ніби як дивиться в землю, якщо ви передбачають самі, як такого роду шляху з різними сполуками. Сортувати дивлячись і начебто забарвлення розпиленням Гарвард на землі. Це ім'я цього. Знайте, що це те, що в цьому місці. Якщо ми стартуємо з кореня і йдемо вниз 1, а потім 6, а потім 3, а потім 6, де ми? Ну, якщо ми подивимося вниз і ми бачимо, Гарвард, потім ми знаємо, що Гарвард був заснована в 1636 році на основі, як ми реалізації цієї структури даних. Так що, сподіваюся, був простий. Ми збираємося зробити ще два вставки. І, сподіваюся, це допоможе в щоб це було зроблено в два рази більше. 

Тепер, давайте вставити інший університет. Давайте вставити Йель в цьому синтаксичного дерева. Єльський була заснована в 1701 році. Таким чином, ми почнемо на корінь, як ми завжди робимо. І ми повинні встановити покажчик обходу. Ми збираємося використовувати це, щоб рухатися через. Перше, що ми хочемо, щоб зробити, це піти по шляху 1. Це перша цифра нашого ключа. На щастя, однак, ми не повинні робити будь-яку роботу на цей раз. 1-шлях вже був очищений. Я очистив його раніше, коли я вставляв у Гарвард в 1636 році. Так що я можу сміливо рухатися вниз 1 і тільки туди. Якщо може рухатися вниз 1. 

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

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

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

Так що я Танос новий вузол і мають точку 0 там. А потім ще раз, я Танос Новий вузол і мають одну точку там. Знову ж таки, я вичерпав свій ключ, 1 701. Так я дивлюся вниз, і я розпорошити фарбу Єль. Це ім'я цього вузла. 

І ось тепер, якщо я коли-небудь знадобиться, щоб побачити, якщо Єльському університеті в цьому синтаксичного дерева, я починаю в корені, Я спускаюся 1 701, і дивитися вниз. І якщо я бачу Yale спрей пофарбовані на землю, то Я знаю, Єльський існує в цьому синтаксичного дерева. Давайте зробимо ще один. Давайте вставити Дартмут в це Trie, яка була заснована в 1769 році. 

Початок в корені знову. Моя перша цифра мого ключа 1. Я можу з упевненістю рухатися цим шляхом. Це вже існує. Наступна цифра мого ключа 7. Я можу з упевненістю рухатися цим шляхом. Вона існує, як добре. 

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

Так що я Танос новий вузол, так що з що node-- шлях Кількість 9-- і то зараз якщо я подорожую +1769, і я з нетерпінням вниз. Там немає нічого про себе спрей пофарбовані там. Я можу написати Дартмут. І я вставив Дартмут в синтаксичного дерева. 

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

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

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

Тепер, наступне місце ми повинні піти 6. Чи існує шлях 6 звідси? Так, це так. Ми можемо спуститися 6 шлях. І ми в кінцевому підсумку тут. 

Чи можемо ми піти вниз 3 шляху звідси? Ну, як з'ясовується, так, теж існує. І ми можемо отримати на шляху від 6 тут? Так, ми можемо. 

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

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

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

Чи можу я перейти вниз по 7 шляху звідти? Так, я можу. Це теж існує. Але я можу піти по шляху 4 з тут? Це як поставити запитання, може Я виходжу вниз, що скверик що я виділив жовтим? Там нічого немає. Право. 

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

Отже, що ж все це означає? Право. Там дуже багато тут відбувається. Там це покажчики всюди. І, як ви можете бачити просто з діаграми, є багато вузлів, які є свого роду політ навколо. Але зверніть увагу, кожен раз, коли ми хотіли перевірити щось було в синтаксичного дерева, у нас був тільки зробити 4 ходів. 

Кожен раз, коли ми хотіли вставити щось у синтаксичного дерева, ми повинні зробити 4 переміщається, можливо, mallocing деякі речі по дорозі. Але, як ми бачили, коли ми вставили Дартмут в синтаксичного дерева, Іноді деякі з шляху вже може бути очищена для нас. І так як наш Trie стає все більше і більше, у нас є менше роботи кожного разу, вставити нові речі тому що ми вже побудовано багато проміжний філії по шляху. Якщо ми тільки коли-небудь повинні дивитися на 4 речі, 4 це просто константа. Ми дійсно вид наближається постійна вставки раз і постійне пошук час. Компроміс, звичайно, в тому, що це Trie, як ви, ймовірно, може сказати, величезний. Кожен з цих вузлів займає багато місця. 

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

І так це компроміс. Але, схоже, ми можливо, знайшли його. Ми могли б знайти, що Святий Грааль структур даних з швидкою вставки, видалення і пошук. І, може бути, це буде відповідна структура даних використовувати для будь-якої інформації ми намагаємося зберегти. Я Дуг Ллойд, це CS50.