[MUSIC JOC] DOUG LLOYD: Deci, am fost mai aproape tarasc și mai aproape ca Sfântul Graal de date structuri, una care putem insera în, ștergeți din, și privi în sus în timp constant. Dreapta. Asta e un fel de gol. Vrem să fie capabil să facă lucruri foarte, foarte repede. 

Au am găsit aici când vorbim despre încercări? Ei bine, haideți să aruncăm o privire. Așa că am văzut de mai multe diferite structuri de date că se ocupe cartografierea așa-numita perechi cheie-valoare, cartografiere unele bucată de date la un alt bucată de date așa că știu unde să găsească Informații în structura. 

Deci pentru matrice, de exemplu, cheie este indicele sau matrice element de Localizare 0 sau 1 matrice și așa mai departe. Și valoarea este datele care există în acea locație. Deci, ceea ce este stocat în matrice 0? Ceea ce este stocat în serie 1 față de doar 0 și 1, care ar fi cheile. 

Cu un tabel hash este un fel de aceeași idee. Cu un tabel hash, avem această hash funcție care generează codurile hash. Deci, cheia este codul de distribuire a datelor. Și valoarea, în special am vorbit despre înlănțuirea în video pe tabele de dispersie, este că lista de date legate de care hashes pentru că hashCode. Dreapta. Ce zici de o altă abordare această metodă, deși? Ce zici de o metodă în cazul în care cheie este garantat să fie unică, Spre deosebire de un tabel hash, în cazul în care am putea termina cu două bucăți de date având aceeași hashCode. Și apoi avem de a face cu care fie sondare sau mai mult preferabil înlănțuirea pentru a remedia această problemă. 

Deci, acum putem garanta că cheia noastră va fi unic. Și ce dacă valoarea noastră a fost doar ceva la fel de ușor ca adevărat și fals, care ne spune dacă sau nu că bucata de informații există în structura? Un Boolean ar putea fi la fel de simplu ca un pic. Realist este, probabil, un octet mai multe sanse decat un pic. Dar asta e mult mai mic decât stocarea poate un șir de 50 de caractere, de exemplu. 

Deci încearcă, similar cu hash tabele, care combină rețele și lista legate, încearcă combina tablouri, structuri, și indicii împreună pentru a stoca date în un mod interesant care este destul de diferit de la tot ce am văzut până acum. Acum vom folosi datele ca o foaie de parcurs pentru a naviga această structură de date. Și dacă putem urmări foaia de parcurs, dacă putem urmați datele din început până la sfârșit, vom știu dacă faptul că datele există în trie. 

Și dacă nu putem urmări pe harta de la ceea ce înseamnă să se încheie la toate, datele nu pot exista. Din nou, tastele sunt aici garantat să fie unic. Și așa mai departe, spre deosebire de un tabel hash, nu am să au de a face cu coliziuni aici. Și nu există două bucăți de date au exact aceeași foaia de parcurs cu excepția cazului în care datele sunt identice. 

Dacă vom introduce John, apoi cautam John. Asta e două bucăți identice de date, dreapta, căutăm prin. Dar altfel, orice două bucăți de date sunt garantat de a avea foi de parcurs unice prin această structură de date. Și am de gând să ia o privire la un vizual de acest lucru în doar un moment. 

Vom face acest lucru prin încercarea de a crea o nouă structură de date, cartografiere următoarele perechi de valori-cheie. În acest caz, nu mergem să utilizeze ceva la fel de simplu ca un Boolean. Noi de fapt, va stoca șir. Și că șir va fie numele unei universități. 

Și cheia va fi anul când a fost înființată ca universitate. Toate ani pentru universități vor fi de patru cifre. Și așa vom folosi cele patru cifre naviga prin această structură de date. Și vom vedea, din nou, cum facem asta în doar o secundă. 

La sfârșitul căii, vom vedea numele a universității care corespunde pentru că cheie, cele patru cifre. Ideea de bază din spatele unui trie este că avem un traseu central. Deci, cred că despre ea ca un copac. Și acest lucru este similar în ortografie și în conceptul de un copac. În general, atunci când ne gândim la copaci în lumea reală, ei au o rădăcină care este în sol și cresc în sus și au filiale și au frunze. Și practic ideea de un trie este exact la fel, cu excepția faptului că rădăcină este ancorat undeva în cer. Și frunzele sunt în partea de jos. 

Deci e un fel de a lua un copac și doar flipping cu susul în jos. Dar există încă ramuri. Iar cei ar fi cai noastre, acestea vor fi conexiunile noastre de la rădăcină la frunze. In acest caz, cei căi, aceste ramuri sunt marcate cu cifre care ne spun care mod de a merge, de unde suntem. 

Dacă vom vedea o 0, vom merge în jos această ramură, dacă vom vedea un 1, vom merge în jos această ramură, și așa și așa mai departe. Ei bine, ce înseamnă asta? Ei bine, asta înseamnă că la fiecare punct de joncțiune și fiecare nod din mijloc și fiecare ramură, există 10 posibile locuri pe care putem merge. Deci, există 10 indicii din orice locație. 

Și acest lucru este în cazul în care încearcă să obține un pic intimidant pentru cineva care e nu are o mulțime de experiență în informatică înainte. Dar încearcă sunt într-adevăr destul de minunat. Și dacă aveți sansa de a lucra cu ei și sunteți dispus să sape în și experimenta cu ei, sunt foarte destul de interesant structuri de date pentru a lucra cu. Dacă vrem să inserați un element în trie, tot ce trebuie să facem este construit calea corectă de la rădăcină până la frunza. Iată ce fiecare pas de-a lungul modul ar putea arata ca. Vom defini o nouă date structură pentru un nou nod numit trie. 

Și în interiorul acestor date Structura există două piese. Vom magazin Numele o universitate. Și am de gând să stoca o serie de indicii la alte noduri de același tip. Deci, din nou, aceasta este ca un fel conceptului de pretutindeni suntem, la 10 mai locuri putem merge. Dacă vom vedea o 0, vom merge în jos această ramură. Dacă vom vedea o 1, această ramură, și așa mai departe și așa mai departe și așa mai departe. Dacă spunem 9, vom merge în jos această ramură. Deci, la fiecare punct de joncțiune, putem merge 10 locuri posibile. Astfel încât fiecare nod trebuie sa contina 10 indicii la alte noduri, la alte 10 noduri. 

Iar datele suntem stocare este doar numele universității. Deci, haideți să construim un trie. Să introduceți un cuplu de articole în trie nostru. Deci, la foarte de sus, acest lucru este nod rădăcină nostru. Acest lucru este, probabil, va fi ceva ai de gând să nivel global declara. Și ai de gând să mențină nivel global un pointer la acest nod întotdeauna. 

Ai de gând să spun, rădăcină este egal, și tu ești O să vă malloc nod trie. Și niciodată nu vei pentru a atinge din nou rădăcină. De fiecare dată când doriți să începe navigarea prin, setați un alt pointer egal cu radacina, cum ar fi trav, care este exemplul I folosi în multe dintre videoclipurile mele aici, pe stive și cozi și liste de link-ul și așa mai departe. 

Puteți seta un alt pointer numit trav pentru traversarea. Și utilizați pentru a naviga trav prin structura de date. Deci, hai sa vedem cum acest lucru ar putea arata. Deci, chiar acum, ceea ce nu un nod arata ca? Ei bine, la fel ca datele noastre declarație structura indicat, avem un șir de caractere, care în acest caz este gol. Nu e nimic aici. 

Și o serie de 10 indicatori. Iar acum, noi doar au un nod în acest trie. Nu e nimic altceva în ea. Deci, toate cele 10 de cei indicii de puncte la null. Asta e ceea ce indică roșu. 

Să introduceți șirul Harvard. Să se introduce la Universitatea din Harvard în această trie, care a fost fondată în anul 1636. Vrem să utilizați tasta, 1,636, să ne spună unde suntem va pentru a stoca Harvard în trie. Acum, cum pot să facem asta? 

S-ar putea arata ceva de genul asta. Începem de la rădăcină. Și avem aceste 10 locuri se poate merge. Rădăcina este la fel ca orice alt nod din trie. Există 10 locuri putem merge de aici. 

În cazul în care face, probabil, ne-o dorim pentru a merge în cazul în care cheia este 1,636? Există într-adevăr două opțiuni. Dreapta. Putem construi cheia din la dreapta la stânga și să înceapă cu 6. Sau am putea construi cheia de la la stânga la dreapta și să înceapă cu un. 

Este, probabil, mai intuitiv ca o ființă umană să înțelegem vom Doar du-te la stânga la dreapta. Și așa, dacă vreau să introduceți Harvard în această trie, Probabil că vreau să încep pornind de la rădăcină, uita la mele 10 opțiuni în fața mea, și spunând Vreau să merg pe calea 1. BINE. 

Acum, o cale este în prezent nulă. Deci, dacă vreau să procedeze în jos această cale pentru a introduce acest element în trie, Trebuie să malloc un nou nod, au 1 punct acolo, și atunci eu sunt bine să plec. 

Deci, eu de fapt sunt la o punct în care stau la rădăcina copacul sau trie și există 10 de sucursale. Dar fiecare ramură are un poarta în fața lui. Dreapta. Pentru că nu e nimic altceva nu e. Nici un pasaj în condiții de siguranță. Asta înseamnă că nu e nimic jos oricare dintre aceste ramuri. Dacă vreau pentru a începe construirea ceva, vreau să eliminați poarta. Vreau să eliminați poarta în fața numărului 1. Și vreau să merg pe asta. Și vreau să construiască un alt loc pentru mine să merg. 

Și asta e ceea ce am făcut aici. Deci 1 nu mai arată la null. Am spus că se află în condiții de siguranță să meargă în jos aici, acum. Am construit un alt nod. Și când ajung la acel nod, am o altă decizie de a face. În cazul în care am de gând să merg de aici? 

Ei bine, am plecat deja pe 1. Deci, acum, probabil, vreau să merg în jos 6. Dreapta. Din nou, am 10 de locații pot alege. Deci, hai sa mergem acum pe numărul 6. Așa că am clar poarta în fața numărului 6. Și am mers acolo. Și am construi un alt nod. Și am ajuns la un alt punct de joncțiune. 

Din nou, am 10 variante pentru cazul în care pot merge. Am trecut la 1 la 6. Deci, acum, probabil, eu vreau să merg la 3. 3, nu e nicăieri pot merge. Așa că am să clar modul și cu mine construi un nou spațiu. Și apoi de la 3, în cazul în care vreau să merg? Vreau să merg în jos 6. 

Și, din nou, a trebuit să clar modul de a face acest lucru. Deci, acum am folosit cheia pentru a insera crea noduri și începe să construiască acest trie. Am început de la rădăcină. Am coborât 1636. Și acum sunt în partea de jos acolo pe acel nod. Și s-ar putea fi în măsură să vedea pe ecran. 

Este evidențiat în galben. Acolo am în prezent sunt. Cheia se face. Am epuizat fiecare poziție în cheia mea. Deci, eu nu pot merge mai departe. Deci, la acest moment, tot ce am într-adevăr trebuie să faceți este spus, OK. Este un fel de căutarea în jos, la pământ, dacă sunteți prefigurand te ca acest tip de drum cu diferite conexiuni. Un fel de a privi în jos și un fel de spray-pictura Harvard pe teren. Acesta este numele acestui. Știu că e ceea ce e în această locație. Dacă începem de la rădăcină și vom merge în jos 1 și apoi 6 și apoi 3 și apoi 6, unde suntem? Ei bine, dacă ne uităm în jos si vom vedea la Harvard, apoi știm că a fost la Harvard fondată în 1636 pe baza drum suntem de punere în aplicare această structură de date. Deci asta a fost, sperăm simplu. Vom face mai multe inserții două. Și sperăm că-l vom ajuta să aceasta face de două ori mai mult. 

Acum, haideți să introduceți o altă universitate. Să introduceți Yale în această trie. Yale a fost fondată în 1701. Deci, vom începe de la rădăcină, așa cum facem mereu. Și am stabilit un pointer traversarea. Vom folosi pentru a vă deplasa prin. Primul lucru pe care vrem să faceți este să mergeți pe calea 1. Asta e prima cifră de cheie noastre. Din fericire, însă, noi nu trebuie să faci nici o lucrare de această dată. 1 Calea a fost deja eliminate. Am șters anterior, atunci când o am a fost introducerea Harvard la 1636. Deci, eu pot deplasa în siguranță jos 1 și du-te acolo. Dacă se poate deplasa în jos, 1. 

Acum, însă, vreau să merg la 7. Am deschis calea la 6. Știu că pot în condiții de siguranță continua pe 6 calea. Dar am nevoie pentru a trece de pe 7 calea. Deci, ce trebuie să fac? Ei bine, la fel ca înainte, am doar nevoie de pentru a șterge poarta, ieși din drum, și de a construi o nouă nod de 7 cale. La fel ca aceasta. 

Deci, acum am mutat 1 și apoi 7. Și acum observați, sunt un fel de pe acest nou subbranch. Dreapta. Orice altceva de la 16 pe, nu-mi pasă. Nu fac nimic 16. Fac 17 lucruri. 

Deci, acum la 17, am să un fel de vâlvătaie trasee noi aici. Următoarea cifră cheia este 0. Eu în mod clar nu pot ajunge oriunde. Am construit acest nod. Așa că știu nu există nici căi forward de aici. Așa că am să fac eu unul. 

Așa că am malloc un nou nod și au 0 puncte acolo. Și apoi încă o dată, am o malloc nod nou si au un punct de acolo. Din nou, mi-am epuizat cheia, 1701. Așa că am uita în jos și am spray cu vopsea Yale. Acesta este numele acestui nod. 

Și așa acum, dacă am nevoie pentru a vedea dacă Yale este în acest trie, am începe de la rădăcină, Mă duc în jos 1701, și privi în jos. Și dacă văd pulverizare Yale pictat pe pământ, apoi Știu Yale există în acest trie. Hai să facem unul mai mult. Să introduceți Dartmouth în această trie, care a fost fondată în 1769. 

Start la rădăcină din nou. Prima mea cifră de cheia este de 1. Mă pot mișca în siguranță pe această cale. Care există deja. Următoarea cifră de cheia este 7. Mă pot mișca în siguranță pe această cale. El există, de asemenea. 

Urmatorul meu este de 6. De aici, de unde am în prezent sunt în galben acolo, în acel nod de mijloc, 6 este în prezent blocat de pe. Dacă vreau să merg în jos această cale, Trebuie să-l construiască singur. Așa că voi malloc un nou nod și au 6 punctul acolo. Și apoi, din nou, eu sunt aprins noi trasee aici. 

Așa că am malloc un nou nod, astfel încât de la acest număr cale node-- 9-- și apoi acum dacă am de călătorie 1,769, și mă uit în jos. Nu e nimic în prezent pulverizare pictat acolo. Pot să scriu Dartmouth. Și am introdus Dartmouth în trie. 

Așa că e inserarea lucrurile în trie. Acum vrem pentru a căuta lucruri. Cum căutăm lucruri în trie? Ei bine, e destul de mult aceeași idee. Acum vom folosi doar cifrele cheie pentru a vedea dacă putem naviga de la rădăcină unde vrem să mergem în trie. 

Dacă am lovit-o fundătură în orice moment, atunci știm că nu se poate că există elemente sau altceva care ar fi calea au fost deja eliminate. Dacă vom face tot drumul până la cele din urmă, tot ce trebuie să facem este uita în jos și a vedea dacă acesta este elementul căutăm. Dacă este, succesul. În cazul în care nu e, nu. 

Deci, haideți să căuta Harvard în această trie. Începem de la rădăcină. Și, din nou, vom a crea un pointer de traversare de a face miscari noastre pentru noi. Din rădăcina știm că primul loc avem nevoie pentru a merge este de 1, putem face asta? Da putem. Dacă există condiții de siguranță. Putem merge acolo. 

Acum, următorul loc avem nevoie pentru a merge este de 6. Are 6 calea exista de aici? Da, așa e. Putem merge pe calea 6. Și am ajuns aici. 

Putem merge pe calea 3 de aici? Ei bine, se pare că, da, care există de asemenea. Și putem ajunge pe 6 calea de aici? Da putem. 

Noi nu am destul de răspuns întrebarea încă. Există încă o mai pas, care este acum avem nevoie să se uite în jos și vedea dacă e actually-- dacă suntem în căutarea pentru Harvard, este că ceea ce vom găsi după ce epuizează cheia? În exemplul folosim aici, anii sunt întotdeauna patru cifre. Dar s-ar putea să fie folosind exemplul în care sunteți stocarea unui dicționar de cuvinte. 

Și astfel încât în ​​loc de a avea 10 indicii pentru locația mea, s-ar putea avea 26. Unul pentru fiecare literă a alfabetului. Și există unele cuvinte, cum ar fi BAT, care este un subset al lotului, de exemplu. Și astfel, chiar dacă tu a lua la sfârșitul cheia și te uiți în jos, s-ar putea să nu vezi ce sunteți în căutarea pentru. 

Deci, va trebui întotdeauna să traverseze întreaga cale și apoi dacă ai fost capabil succes pentru a traversa întreaga cale, privi în jos și de a face o confirmare finală. Asta caut? Ei bine, m-am uita în jos după începerea în partea de sus și merge 1,636. Mă uit în jos. Văd Harvard. Deci, da, am reușit. Ce se întâmplă dacă ceea ce caut nu este în trie, totuși. Ce se întâmplă dacă caut Princeton, care a fost fondată în 1746. Și astfel 1,746 devine cheia mea pentru a naviga prin trie. Ei bine, eu încep de la rădăcină. Și primul loc vreau a se duce în jos 1 calea. Pot să o fac? Da, eu pot. 

Pot să mă duc pe calea 7 de acolo? Da, pot. Care există prea. Dar pot merge pe calea 4 de aici? E ca și cum pune întrebarea, poate Am continua pe aia pătrat care l-am evidențiat în galben? Nu e nimic acolo. Dreapta. 

Nu există nici o cale de urmat pe calea 4. Dacă Princeton a fost în acest trie, că 4 ar fi fost eliminate deja pentru noi. Și astfel, în acest moment am ajuns într-o fundătură. Nu putem merge mai departe. Și astfel putem spune, definitiv, nr. Princeton nu există în acest trie. 

Deci, ce inseamna toate acestea? Dreapta. Există o mulțime întâmplă aici. Există indicii peste tot. Și, după cum puteți vedea doar din diagrama, există o mulțime de noduri care sunt un fel de zbor în jurul. Dar observați de fiecare dată când am vrut să verifică dacă ceva a fost în trie, am avut doar pentru a face 4 mutări. 

De fiecare dată când am vrut să introduceți ceva în trie, avem de a face 4 mutări, eventual mallocing unele lucruri de-a lungul drum. Dar, așa cum am văzut când am introdus Dartmouth în trie, uneori o parte din calea ar putea fi deja eliminate pentru noi. Și astfel ca trie nostru devine mai mare și mai mare, ne-am făcut mai puțin de lucru de fiecare dată pentru a introduce lucruri noi pentru că ne-am deja a construit o mulțime de intermediar ramuri de-a lungul drum. Dacă avem doar vreodată să se uite la 4 lucruri, 4 este doar o constantă. Suntem intr-adevar sunt un fel de abordare inserție timp constant și de căutare constantă de timp. Compromisul, desigur, fiind că acest trie, după cum puteți, probabil, spune, este imens. Fiecare dintre aceste noduri ocupă o mulțime de spațiu. 

Dar asta e compromisul. Dacă vrem cu adevărat rapid inserție, ștergere foarte repede, și de căutare foarte rapid, trebuie să ne au o mulțime de date de zbor în jurul. Trebuie să pună deoparte o mulțime de spațiu și memorie pentru ca structura de date A exista. 

Și așa că e compromisul. Dar se pare ca ne-am s-ar putea l-au găsit. S-ar putea au descoperit ca Sfântul Graal al structurilor de date cu inserție rapidă, ștergerea, și de căutare. Și poate acest lucru va fi un structură de date corespunzătoare de a utiliza pentru orice informații încercăm să magazin. Sunt Doug Lloyd, aceasta este CS50.