[За възпроизвеждане на музика] Дъг LLOYD: Така че ние сме били по-близо приближава и по-близо, че Светия Граал на данни структури, такава, която можем да вмъкнете в, изтриете от, и погледнете нагоре в постоянен време. Право. Това е нещо от вратата. Ние искаме да бъдем в състояние да направи нещата много, много бързо. 

Има го намери тук, когато ние не говорим за опит? Е, нека да разгледаме. Така че сме виждали няколко различни структури от данни които се справят с картографирането на така наречените двойки ключ-стойност, картографиране някаква част от данните, към някоя друга част от данните, така че ние знаем къде да намеря информация в структурата. 

Така за матрица, например, ключ е индексът на елемент или масив населено място 0 или масив 1 и така нататък. А стойността е данните който съществува на това място. Така че това, което се съхранява в масив 0? Това, което се съхранява в масив 1 срещу само 0 и 1, което би било ключовете. 

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

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

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

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

Ако въведете John, тогава ние търсим Джон. Ето две еднакви парчета данни, нали, ние не търсим сам. Но друго, всяка две парчета данните гарантирано, че има уникални пътни карти през тази структура данни. И ние ще да разгледаме най- визуално за това в един момент. 

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

И ключът ще бъде годината когато този университет е основан. Всички години за университетите ще бъдат четири цифри. И така, ние ще използваме тези четири цифри за придвижвате в тази структура на данните. И ние ще видим, отново, как ние правим това само с втората. 

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

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

Ако видим 0, слизаме този бранш, ако ние виждаме едно, слизаме този бранш, и така и така нататък. Е, какво означава това? Е, това означава, че при всяко кръстовище точка и всеки възел в среден и всеки клон, има 10 възможни места, които можем да вървим. Така че има 10 показалки от всяко населено място. 

И това е мястото, където се опитва да получите малко смущаваща за някого кой не разполагате с много опит в компютърните науки и преди. Но си опит са наистина доста страхотно. И ако имате шанс да работя с тях и сте готови да копаят-в и експериментирате с тях, те са наистина доста интересно структури от данни, за да работим. Ако искаме да вмъкнете елемент в TRIE, всичко, което трябва да направите, се изгради правилния път от корените към листата. Ето какво всяка стъпка по Между другото може да изглежда така. Отиваме да определи нова информация структура за нов възел нарича Trie. 

А вътре на тези данни структура има две части. Отиваме, за да съхраните Име на университет. И ние ще се съхранява масив от указатели към други възли от същия тип. Така че, отново, това е, че сортиране на концепция за навсякъде ние сме, ние от 10 възможни места можем да вървим. Ако видим 0, слизаме този бранш. Ако видим едно, този клон, и така нататък, и така нататък, и така нататък. Ако кажем, 9, слизаме този бранш. Така че при всяко кръстовище точка, можем да отидем 10 възможни места. Така че всеки възел трябва да съдържа 10 показалки към други възли, до 10 други възли. 

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

Ще кажа, корен е равен, а ти си Ще си изчистване Trie възел. И никога няма да се докоснат до корените отново. Всеки път, когато искате да започнете да навигирате чрез, зададете друга показалка равен на корен, като Trav, която е пример използвате в много от моите клипове тук на стекове и опашки и линк списъци и така нататък. 

Можете да зададете друга показалка наречено Trav за прекосява. И вие използвате Trav да навигирате чрез структурата на данните. Така че нека да видим как това може да изглежда. Така че точно сега, това, което е една възлова точка изглежда? Е, точно както нашите данни декларация структура е посочено, имаме поредица, която в този случай е празна. Тук няма нищо. 

И масив от 10 указатели. И точно сега, ние само има един възел в тази синтактично дърво. Няма нищо друго в него. Така че всички 10 от тях указатели точка за нищожна. Това е, което червеният показва. 

Нека да въведете низ Харвард. Нека да въведете университет Harvard в тази синтактично дърво, което е основана през 1636 година. Искаме да използвате клавиша, 1636, за да ни каже къде сме ще се съхранява в Harvard TRIE. Сега, как може да стане това? 

Тя може да изглежда нещо като това. Започваме в корена. И ние имаме тези 10 места, на които могат да отидат. Коренът е като всеки друг възел на Trie. Има 10 места можем да преминат от тук. 

Къде бихме вероятно ще пожелаете да отида, ако ключът е 1636? Има наистина две възможности. Право. Ние можем да изградим ключа от дясно на ляво и се започне с 6. Или можем да изградим ключа от ляво на дясно и се започне с 1. 

Това е може би по- интуитивен като човешко същество да разбираме, ще Просто отидете ляво на дясно. И така, ако искам да вмъкнете Harvard в тази синтактично дърво, Аз може би искате да започнете като се започне в основата, погледнете в моите 10 възможности пред мен, и каза: Искам да отида надолу по пътеката 1. ДОБРЕ. 

Сега, един път в момента е нищожна. Така че, ако искам да се процедира по този път да вмъкнете този елемент в TRIE, Аз трябва да изчистване на нов възел, има 1 точка там, и тогава аз съм добре да тръгвам. 

Така че аз съм в основата на по- точка, където стоя в основата на дървото или синтактично дърво и има 10 клона. Но всеки клон има порта пред него. Право. Защото няма какво друго има. Не безопасно преминаване. Това означава, че няма нищо определяне на всеки от тези клонове. Ако искам да започне изграждането нещо, което искам да премахнете портата. Искам да премахна портата Пред номер 1. И аз искам да върви надолу, че. И аз искам да се изгради друго място за мен да отида. 

И това е, което съм направил тук. Така че една вече не сочи към нула. Аз бях казал, че е безопасно да сляза тук, сега. Аз построих друг възел. И когато стигнем до този възел, I имаме още едно решение да се направи. Къде отивам да отида от тук? 

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

Отново имам 10 възможности за избор за къде мога да отида. Аз бях преместен 1-6. Така че сега аз вероятно искате да отидете до 3. 3, има къде мога да отида. Така че аз трябва да разчисти пътя и себе си построи ново пространство. И тогава от 3, където искам да отида? Искам да сляза 6. 

И, отново, аз трябваше да разчисти пътя да го направя. Така че сега аз съм използвал ключа си, за да вмъкнете създадете възли и започват да се изгради тази синтактично дърво. Аз започнах в корена. Аз бях слязъл 1636. И сега съм на дъното там на този възел. И вие може да бъде в състояние да я видите на вашия екран. 

Тя е оцветена в жълто. Това е, когато аз в момента съм. Ключова My е направено. Аз бях изчерпал всяка позиция в моя ключ. Така че аз не мога да отида по-нататък. Така че в този момент, всичко, което мога Наистина трябва да направите е да се каже, OK. Това е нещо като начало надолу към земята, ако сте предвиждащ себе си като този вид на пътя с различни връзки. Нещо гледа надолу и да сортирате на спрей боядисване Harvard на земята. Това е името на този. Знайте, че това, което е на това място. Ако започнем в корена и слизаме 1 и след 6 и след 3 и 6, след това, къде се намираме? Ами ако погледнем надолу и ние виждаме Харвард, а след това ние знаем, че Харвард е основана през 1636 въз основа на начина, по който ние сме за прилагане на настоящата структура на данните. Така че това беше надяваме ясна. Ние ще направим още две вмъквания. И да се надяваме, че ще ви помогне да виж това да стане още два пъти. 

Сега, нека да поставите друг университет. Нека да вмъкнете Yale в тази синтактично дърво. Yale е основана през 1701. Така че ние ще започне в корен, както ние винаги правим. И ние зададете прекосява показалка. Отиваме да използват това, за да се движи сам. Първото нещо, което искаме да направите е да отидете надолу по пътеката 1. Това е първата цифра от нашия ключ. За щастие, обаче, не го правим трябва да се направи някаква работа този път. В един път вече е изчистена. Аз го изчисти преди това, когато аз се поставяте в Harvard 1636. Така че мога спокойно да се движи надолу 1 и просто отидете там. Ако може да се движи надолу по 1. 

Сега, обаче, искам да отида до 7. I разчисти пътя към 6. Знам, че мога спокойно продължете надолу по пътеката 6. Но аз трябва да се процедира по пътя 7. И така, какво трябва да направя? Е, точно както и преди, аз просто трябва да изчисти портата, да се измъкнем от пътя, и изграждане на нов възел от пътя 7. Точно като този. 

Така че сега съм се премества 1 и след 7. И сега забележи, че съм нещо като на тази нова subbranch. Право. Всичко останало от 16 нататък, аз не се грижи за. Не го правя 16 нищо. Правя 17 неща. 

Така че сега, от 17 нататък, аз трябва да сортиране на пожар нови трасета тук. Следващата цифра моят ключ е 0. Аз очевидно не може да се навсякъде. Току-що построен този възел. Така че аз знам, че няма пътеки напред от тук. Така че трябва да се направи една себе си. 

Така че аз изчистване на нов възел и има 0 точки там. И след това още един път, аз изчистване на нов възел и имат една точка там. Отново съм изчерпал ми ключ, 1701. Така че аз гледам надолу и аз спрей боя Yale. Това е името на този възел. 

И така, сега, ако някога се наложи да се види дали Yale е в това синтактично дърво, започна в корена, Сляза 1701, и погледнете надолу. И ако видя Yale спрей рисувани върху земята, а след това Знам, Yale съществува в този синтактично дърво. Нека да направим още една. Нека да вмъкнете Dartmouth в тази синтактично дърво, която е основана през 1769. 

Започнете в основата отново. Моята първа цифра на ключовата ми е едно. Мога спокойно да се движи по този път. Това вече съществува. Следващата цифра на ключовата ми е 7. Мога спокойно да се движи по този път. Тя съществува, както добре. 

My следващата е 6. Оттук, от където аз в момента съм в жълто там с това, че средната възел, 6, понастоящем е заключена разстояние. Ако искам да отида по този път, Аз трябва да го изградим себе си. Така че аз ще изчистване на нов възел и има 6 точка там. И след това, отново, аз съм пламнал нови трасета тук. 

Така че аз изчистване на нов възел, така че от че node-- номера на канала и след това вече 9-- ако пътувам 1,769, а аз гледам надолу. Няма нищо в момента спрей боядисани там. Мога да напиша Dartmouth. И аз съм вмъква Дартмут в TRIE. 

Така че това е вмъкване неща минута на TRIE. Сега искаме да потърсите неща. Как да търсим нещата в TRIE? Е, това е почти една и съща идея. Сега ние просто използвайте цифрите на ключа да видим дали можем да се придвижвате от корена до мястото, където искаме да отидем в TRIE. 

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

Така че нека да търси за Harvard в тази синтактично дърво. Започваме в корена. И, отново, ние ще създадете прекосява показалка да направи нашите ходове за нас. От корена ние знаем, че първо място ние трябва да отида е 1, можем да направим това? Да ние можем. Ако съществува безопасно. Ние можем да отидем там. 

Сега, следващото място, което трябва да отида е 6. Пътят 6 Съществува ли от тук? Да, това е така. Ние можем да слезем на пътя 6. И ние в крайна сметка тук. 

Можем ли да върви надолу по пътеката 3 от тук? Е, както се оказва, Да, съществува също. И можем да получим по пътя 6 от тук? Да ние можем. 

Не сме съвсем отговори Все още на въпроса. Все още има още една стъпка, която в момента е ние трябва да се погледне надолу и да видим дали това е actually-- ако ние не търсим Харвард, е, че това, което откриваме, след като изчерпи ключът? В примера ние използваме тук, годините винаги са четири цифри. Но вие може да се използва за пример, където съхранявате речник на думи. 

И така, вместо да се налага 10 показалки за моето място, може да се наложи 26. Един за всяка буква от азбуката. И има някои думи като прилеп, който е подмножество на партида, например. И така, дори и да стигнем до край на ключа и погледнете надолу, може да не видите това, което , което търсите. 

Така че винаги трябва да прекосяват целия път и след това ако сте били в състояние успешно да прекосяват целия път, погледнете надолу и направете едно окончателно потвърждение. Е, че това, което аз търся? Е, аз гледам надолу след започване на върха и ще 1,636. Аз гледам надолу. Виждам Харвард. Така че, да, аз успях. Какво става, ако това, което аз търся не е в TRIE, все пак. Какво става, ако аз съм гледам за Принстън, която е основана през 1746. И така 1746 става ключова ми да навигирате през TRIE. Е, аз започвам в корена. И на първо място искам да върви надолу по пътеката 1. Мога ли да го направя? Да аз мога. 

Мога ли да върви надолу по пътеката 7 от там? Да, мога. Това съществува също. Но мога да сляза на 4 път от тук? Това е като да си зададе въпроса, може I продължите надолу, че малък площад че съм оцветена в жълто? Там няма нищо. Право. 

Няма начин напред по пътеката 4. Ако Принстън е в това Trie, че 4 щеше да бъде изчистена за нас вече. И така, в този момент стигнахме до задънена улица. Ние не можем да отиде по-нататък. И така, можем да кажем, окончателно, не. Принстън не съществува в този синтактично дърво. 

И така, какво означава всичко това? Право. Има много неща се случват тук. Има насоки по цялото място. И, както можете да видите Просто от диаграмата, има много възли, които са вид летенето. Но всеки път, когато забележите, ние искахме да провери дали нещо не е в TRIE, ние само трябваше да направи 4 ходове. 

Всеки път, когато ние искахме да въведете нещо в TRIE, ние трябва да направим 4 ходове, вероятно mallocing някои неща по пътя. Но както видяхме, когато сме вмъква Дартмут в TRIE, понякога някои от пътя може вече да бъде изчистена за нас. И така, нашата синтактично дърво получава по-големи и голяма, имаме направя по-малко работа всеки път да въведете нови неща защото вече сме построена много на междинния клонове по протежение на пътя. Ако ние само някога трябва да разгледаме 4 неща, 4 е просто константа. Ние наистина са вид наближава константно време вмъкване и константно време за справка. Компромис, разбира се, е, че това синтактично дърво, както вероятно можете да кажа, е огромна. Всеки от тези възли заема много място. 

Но това е компромис. Ако искаме наистина бързо вмъкване, наистина бързо изтриване, и наистина бързо търсене, ние трябва да има много данни, които летят наоколо. Ние трябва да се заделят много място и памет за които структурата на данните да съществува. 

И така, това е компромис. Но изглежда, че ние може да са го намерили. Ние може да сме установили, че Светия Граал на структури от данни с бърз вмъкване, заличаване и справка. И може би това ще бъде подходяща структура от данни да се използва за всякаква информация ние се опитваме да я запазите. Аз съм Дъг Лойд, това е cs50.