[Glazbom] Doug LLOYD: Tako smo skroz bliže i bliže da sveti gral podataka strukture, onaj koji se može umetnuti u, izbrisati iz, i gledati u stalnom vremenu. Tako je. To je vrsta cilja. Želimo biti u mogućnosti učiniti stvari vrlo, vrlo brzo. 

Jesmo li ga pronaći ovdje kada govorimo o pokušaja? Pa, neka je pogledati. Dakle, vidjeli smo nekoliko različite strukture podataka što nose mapiranje Takozvani ključ-vrijednost parova, mapiranje neki komad podataka na neki drugi dio podataka tako da znamo gdje se nalazimo Informacije u strukturi. 

Tako je za niz, na primjer, Ključ je indeks element ili niz Mjesto 0 ili 1 polje i tako dalje. A vrijednost podataka koji postoji na tom mjestu. Pa što je pohranjena u nizu 0? Ono što je pohranjena u nizu 1 u odnosu na samo 0 i 1, što bi bilo ključevi. 

Uz hash tablici je vrsta istom idejom. Uz hash tablici, imamo ovu hash funkcija koja stvara hash kodove. Dakle, ključ je hash broj podataka. A vrijednost, osobito razgovarali smo o ulančavanje u video na hash tablica, da je vezan popis podataka da hashes toj Hash broj. Tako je. Što je s drugom pristupu ovaj postupak, iako? Što o metodi gdje je Ključ je zajamčena biti jedinstven, za razliku od hash tablici, gdje smo mogli završiti s dva komada podataka imaju istu Hash. A onda se moramo nositi s da je bilo sondiranja ili više ponajprije ulančavanje popraviti taj problem. 

Tako sada možemo garantirati da je naš ključ će biti jedinstveni. A što ako je naš vrijednost bila samo nešto tako lako kao istinito i lažno da nam kaže da li ili ne da je dio informacija postoji u strukturi? Booleova može biti kao jednostavan kao malo. Realno je vjerojatno Byte češće nego malo. Ali to je puno manje od spremanje možda niz od 50 znakova, na primjer. 

Dakle pokušaja, slično hash tablica, koje kombiniraju polja i povezane popis, pokušava kombinirati polja, strukture i pokazivače zajedno za pohranu podataka u zanimljiv način na koji je prilično razlikuje od sve smo vidjeli do sada. Sada ćemo podatke koristiti kao putokaz za navigaciju ovu strukturu podataka. I ako možemo pratiti Plan, ako mi može slijedite podatke iz početka do kraja, mi ćemo Znaš li te podatke postoje u Trie. 

A ako ne možemo slijediti kartu iz smisao završiti na sve, podaci ne mogu postojati. Opet, ključevi ovdje zasigurno biti jedinstveno. I tako za razliku od hash tablici, nikada nećemo morati baviti sudara ovdje. A nema dva komada podataka imaju točno istu plan osim ako su podaci identični. 

Ako uložite Ivan, a zatim tražimo Ivana. To je dva identična komada podataka, pravo, tražimo kroz. Ali inače, bilo dva komada podataka su zajamčeno da imaju jedinstvene planova kroz ove strukture podataka. A mi ćemo se pogledati vizualni to u samo trenutak. 

Mi ćemo to učiniti pokušavajući stvoriti novu strukturu podataka, mapiranje sljedeće ključne parove vrijednosti. U tom slučaju, nećemo koristiti nešto kao jednostavan kao Boolean. Mi zapravo će pohraniti string. I to string će se naziv sveučilišta. 

A ključ će biti godina kada je osnovana da sveučilište. Sve godine za sveučilišta će biti četiri znamenke. I tako ćemo koristiti te četiri znamenke navigaciju kroz ove strukture podataka. A vidjet ćemo, opet, kako možemo učiniti u samo sekundi. 

Na kraju staze, vidjet ćemo ime sveučilišta koji odgovara na tom ključu, te četiri znamenke. Osnovna ideja iza Trie je da imamo središnju put. Dakle, razmišljam o tome kao stablo. A to je slično u pravopisu i koncept na stablo. Općenito, kada mislimo o stabala u stvarnom svijetu, imaju korijen koji je u zemlju i oni rastu prema gore i oni imaju podružnice i oni imaju lišće. A u osnovi ideja Trie je točno isto, osim što korijen usidrena negdje na nebu. A listovi su na dnu. 

Dakle, to je vrsta kao što je uzimanje stablo i samo ga flipping naopako. No, još uvijek postoje grane. A oni će biti naši putevi, oni će biti naši veze od korijena do listova. U tom slučaju, oni staze, one grane su označeni s brojkama koje nam na koji način da ide odakle smo. 

Ako vidimo 0, idemo dolje ove grane, ako vidimo 1, idemo dolje ove grane, i tako i tako dalje. Pa, što to znači? Pa, to znači da je na svakom čvorištu i svaki čvor u srednje i svaki ogranak, postoje 10 moguće mjesta koja možemo ići. Dakle, tu su 10 pokazivače iz svakog mjesta. 

I ovo je mjesto gdje pokušava može dobiti malo zastrašujuće za nekoga tko nema puno iskustvo u računalnoj znanosti prije. Ali pokušava stvarno prilično strašan. A ako imate priliku raditi s njima i da ste spremni da kopaju-u i eksperimentirati s njima, oni su zapravo prilično zanimljiva strukture podataka raditi. Ako želite umetnuti element u Trie, sve što trebate učiniti je izgraditi ispravan put iz korijena do lista. Evo što svaki korak zajedno način moglo izgledati. Idemo definirati nove podatke Struktura za novi čvor naziva Trie. 

A unutar tog podataka Struktura postoje dva komada. Idemo pohraniti naziv sveučilišta. A mi ćemo pohraniti niz pokazivača s drugim čvorovima istog tipa. Dakle, opet, to je da vrsta koncepta svugdje mi smo, mi na 10 moguće mjesta možemo ići. Ako vidimo 0, idemo dolje ovu granu. Ako vidimo 1, ova grana, i tako dalje i tako dalje i tako dalje. Ako kažemo 9, idemo dolje ovu granu. Dakle, na svakom čvorištu, možemo ići 10 mogućih mjesta. Dakle, svaki čvor mora sadržavati 10 pokazivače s drugim čvorovima, 10 drugih čvorova. 

A podaci smo pohranjivanje je Upravo naziv sveučilišta. Tako ćemo sagraditi Trie. Idemo ubacite par stavki u naš Trie. Dakle, na samom vrhu, to je naš korijen čvor. To je vjerojatno će biti nešto idete na globalnoj razini proglasiti. I ti ćeš na globalnoj razini održavanje pointer na ovom čvoru uvijek. 

Ti ćeš reći, Korijen jednako, a vi ste će malloc sebi Trie čvor. I nikad ne ide opet dotaknuti korijen. Svaki put kada želite početi s navigacijom kroz, postavite pokazivač drugi jednaka korijenu, kao što Trav, koji je sam primjer koristiti u mnogim od mojih videa ovdje na hrpe i redova i veza popisa i tako dalje. 

Možete postaviti još jedan pokazivač pozvao trav za obuhvaćanje. A vi koristite Trav za navigaciju kroz strukturu podataka. Tako ćemo vidjeti kako to može izgledati. Pa sada, što nema čvor izgledati? Pa, baš kao i naše podataka Struktura izjava naznačeno, imamo niz koji u ovom slučaju je prazna. Nema ničega ovdje. 

I niz od 10 upućuje. A sada, samo mi ima 1 čvor u ovom Trie. Nema ništa u njoj. Dakle, sve 10 od onih upućuje točka na nulu. To je ono što je crvena označava. 

Idemo umetnite niz Harvard. Idemo umetnite Sveučilište Harvard u ovom Trie, koji osnovana je 1636 godine. Želimo iskoristiti ključ, 1636, da nam kaže gdje smo će pohraniti Harvarda u Trie. Sada, kako bismo mogli to učiniti? 

To bi moglo izgledati nešto poput ovoga. Krećemo u korijenu. I mi smo ovih 10 mjesta možemo ići. Korijen je baš kao i bilo drugi čvor Trie. Ima 10 mjesta možemo otići odavde. 

Gdje ćemo vjerojatno želite ići ako je ključ 1636? Tu je stvarno dvije opcije. Tako je. Možemo graditi ključ iz desna na lijevo i početi sa 6. Ili bismo mogli izgraditi ključ iz s lijeva na desno i počnite s 1. 

To je vjerojatno i više intuitivno kao ljudsko biće da razumijemo ćemo Dovoljno je otići s lijeva na desno. I tako, ako želim umetnuti Harvard u ovom Trie, Vjerojatno želite započeti počevši u korijenu, gleda na moje 10 mogućnosti ispred mene i rekao Želim ići dolje 1 put. U REDU. 

Sada, 1 put je trenutno null. Dakle, ako želim nastaviti niz taj put umetnuti taj element u Trie, Moram malloc novi čvor, imaju 1 usmjerite tamo, a onda sam dobar to ići. 

Tako sam zapravo sam u točka u kojoj ja stojim u korijenu stabla ili Trie i ima 10 podružnica. No, svaka grana ima Vrata ispred njega. Tako je. Budući da ništa drugo nema. Ne siguran prolaz. To znači da nema ništa dolje bilo koji od tih grana. Ako želim početi graditi nešto, želim ukloniti vrata. Želim da uklonite vrata ispred broja 1. I želim prošetati toga. I ja želim izgraditi drugo mjesto za mene to ići. 

I to je ono što sam učinio ovdje. Dakle 1 više ne ukazuje na null. Ja sam rekao da je sigurno ići dolje sada ovdje. Napravio sam još jedan čvor. A kad sam doći do tog čvora, ja još jedan odluku. Gdje ću otići odavde? 

Pa, već sam sišao 1. Dakle, sada sam vjerojatno želite ići dolje 6. Tako je. Opet, imam 10 lokacija mogu izabrati. Tako ćemo sada ići dolje broj 6. Tako sam jasan vrata ispred broja 6. I prošetati tamo dolje. I izgraditi još čvor. I sam stigao još jedan čvorište. 

Opet, imam 10 izbora za gdje mogu ići. Ja sam se preselio od 1 do 6. Dakle, sada sam vjerojatno želite ići na 3. 3, postoji nigdje ne mogu otići. Dakle, moram očistiti put i izgraditi sebi novi prostor. A onda od 3, gdje želim ići? Želim ići dolje 6. 

A, opet, morao sam jasan način to učiniti. Dakle, sada sam koristio moje ključ za umetanje izradu čvorovi i početi graditi taj Trie. Ja sam počeo u korijenu. Ja sam sišao 1636. I sad sam na dnu tamo na tom čvoru. A ti bi mogao vidjeti ga na zaslonu. 

To je istaknuto u žuto. To je mjesto gdje sam trenutno. Moj ključ je učinio. Ja sam iscrpljen svaki položaj na moj ključ. Dakle, ja ne mogu ići dalje. Dakle, u ovom trenutku, sve što sam stvarno trebate učiniti je reći, u redu. To je vrsta kao što izgleda dolje na zemlju, Ako ste predviđajući sebe kao ovu vrstu puta s različitim priključcima. Sortiraj gleda prema dolje i vrsta sprej slikarstvo Harvard na terenu. To je naziv za to. Znajte da je ono što je na tom mjestu. Ako počnemo u korijenu i idemo dolje 1, a zatim 6, a potom 3 i zatim 6, gdje se nalazimo? Pa ako ćemo gledati prema dolje i vidimo Harvarda, zatim znamo da je na Harvardu osnovana 1636. temelji se na putu mi smo provedbu ove strukture podataka. Tako da je, nadamo jednostavan. Idemo napraviti još dva umetanja. I nadam se da ću pomoći vidi to učinio dva puta. 

Sada, neka je umetnite drugom sveučilištu. Idemo umetnite Yale u ovom Trie. Yale je osnovana 1701. godine. Tako ćemo početi na Korijen, kao što smo uvijek. A mi postaviti obuhvaćanje pokazivač. Ćemo koristiti kako za kretanje kroz. Prva stvar koju želimo učiniti je otići dolje 1 put. To je prvi broj našeg ključa. Srećom, ipak, mi ne moraju ništa raditi ovaj put. U 1. put je već izbrisan. Ja ga izbacila prije kada sam je umetanje Harvard u 1636. Pa ja sigurno mogu kretati niz 1 i samo tamo. Ako se može pomicati prema dolje 1. 

Sada, međutim, želim otići do 7. Izbrisani sam način na 6. Znam sigurno nastavite niz 6 put. Ali moram nastaviti na 7 put. Pa što trebam učiniti? Pa, baš kao i prije, samo trebam očistiti vrata, izaći na putu, i izgraditi novi čvor od 7 puta. Baš ovako. 

Dakle, sada sam se preselio 1, a zatim 7. A sada primjetiti, ja sam neka vrsta od ovog novog Subbranch. Tako je. Sve ostalo od 16 o, ja ne stalo. Ja ne radim 16 ništa. Radim 17 stvari. 

Tako sada od 17, ja moram vrsta sjala nova staza ovdje. Sljedeći znamenkasti moj ključ je 0. Ja očito ne mogu dobiti nigdje. Upravo sam sagradio ovaj čvor. Dakle, ja znam da nema putevi naprijed odavde. Pa moram napraviti jedan sebe. 

Tako sam malloc novi čvor i imaju 0 bod. I onda još jednom, ja malloc novi čvor i ima jedan bod. Opet, ja sam iscrpljena moj ključ, 1701. Dakle, ja gledati prema dolje i sam sprej boje Yale. To je naziv ovog čvora. 

I tako sada, ako sam ikada trebati vidjeti ako Yale je u ovom Trie, počnem u korijenu, Idem dolje 1701., i gledati prema dolje. A ako vidim Yale sprej slikano na tlo, a zatim Znam Yale postoji u ovom Trie. Učinimo još jedan. Idemo umetnite Dartmouth u ovo Trie, koja je osnovana u 1769. 

Počnite u korijenu opet. Moja prva znamenka moje ključ je 1. Ja sigurno mogu kretati prema dolje taj put. To već postoji. Sljedeći znamenkasti mog ključ je 7. Ja sigurno mogu kretati prema dolje taj put. Ona postoji kao dobro. 

Moj sljedeći je 6. S ovog mjesta, odakle sam trenutno uto tamo u toj sredini čvor, 6 je trenutno zaključana off. Ako želim ići dolje taj put, Moram ga graditi sebe. Tako ću malloc novi čvor i imaju 6 bod. A onda, opet, ja sam plamen nove staze ovdje. 

Tako sam malloc novi čvor, tako da od da node-- broj staza 9-- i onda sada ako sam putovati 1769, i ja gledati prema dolje. Nema ništa trenutno sprej oslikana tamo. Mogu napisati Dartmouth. I ja sam umetnuta Dartmouth u Trie. 

Tako da je umetanje stvari u Trie. Sada želimo tražiti stvari. Kako ćemo tražiti stvari u Trie? Pa, to je ljepušan velik dio isti ideja. Sada smo samo koristiti znamenki ključa vidjeti ako možemo kretati iz korijena gdje želimo ići u Trie. 

Ako pogodak ćorsokak u bilo kojem trenutku, a zatim Znamo da je taj element ne može postoji Inače taj put bi već izbrisani. Ako bi ga sve do kraj, sve što trebate učiniti je pogledati dolje i vidjeti ako je to element tražimo. Ako je uspjeh. Ako to nije, uspjeti. 

Tako ćemo tražiti Harvard u ovom Trie. Krećemo u korijenu. A, opet, mi ćemo stvoriti obuhvaćanje pokazivač učiniti naše poteze za nas. Iz korijena mi znamo da je Prvo mjesto moramo ići 1, možemo učiniti? Da možemo. Ako sigurno postoji. Možemo otići tamo. 

Sada, sljedeći mjesto moramo ići je 6. Da li postoji 6 put odavde? Da, tako je. Možemo ići dolje 6 put. I mi završiti ovdje. 

Možemo ići dolje 3 put odavde? Pa, kao što se ispostavilo, Da, da postoji previše. I možemo dobiti na 6. put odavde? Da možemo. 

Nismo baš odgovorio pitanje još. Postoji još jedan korak, koji je sada trebamo gledati prema dolje i vidjeti ako je to actually-- ako tražimo Harvardu, da što smo pronašli nakon što smo iscrpili ključ? U primjeru smo pomoću ovdje godine su uvijek četiri znamenke. Ali možda se na primjeru gdje pohranjujete rječnika riječi. 

I tako, umjesto da 10 pokazivače za moje mjesto, možda imate 26. Jedan za svako slovo abecede. A tu su i neke riječi poput šišmiša, što je podskup serije, na primjer. I tako, čak i ako se na kraj tipke i gledati prema dolje, možda nećete vidjeti što tražiš. 

Dakle, uvijek morate proći cijeli put, a zatim ako ste bili u mogućnosti uspješno prijeći cijeli put, pogledati dolje i napraviti jednu konačnu potvrdu. Je li to ono što ja tražim? Pa, gledam dolje nakon početka na vrhu i ide 1636. Gledam dolje. Vidim Harvarda. Dakle, da, uspio sam. Što ako je ono što tražim nije u Trie, ipak. Što ako tražim Princeton, koja je osnovana u 1746. I tako 1746. postaje moj ključ za navigaciju kroz Trie. Pa, ja početi u korijenu. A prvo mjesto želim da ide dolje na 1 put. Mogu li to učiniti? Da ja mogu. 

Mogu li ići dolje na 7 put od tamo? Da, mogu. Što postoji previše. Ali ja mogu ići dolje na 4. put odavde? To je kao da postavlja pitanje, može I nastavite niz onaj mali trg koje sam istaknuo u žuto? Nema ništa tamo. Tako je. 

Nema šanse naprijed niz 4 puta. Ako Princeton je u ovom Trie, da 4 bi bio jasan za nas već. I tako u ovom trenutku smo stigli u slijepu ulicu. Mi ne možemo ići dalje. I tako možemo reći, definitivno, ne. Princeton ne postoji u ovom Trie. 

Pa što to sve znači? Tako je. Postoji mnogo događa ovdje. Postoji naputke sve više mjesta. I, kao što možete vidjeti Upravo iz dijagrama, postoji puno čvorova da su vrsta leti okolo. Ali primijetite svaki put smo htjeli provjerite je li nešto nije u Trie, imali smo samo napraviti 4 poteze. 

Svaki put kad smo htjeli ubacite nešto u Trie, moramo napraviti 4 poteze, možda mallocing neke stvari na putu. No, kao što smo vidjeli kad smo umetnuta Dartmouth u Trie, ponekad nekim naprijed možda već biti izbrisani za nas. I tako je naš Trie dobiva veći i veći, moramo učiniti manje posla svaki put umetnuti nove stvari jer smo već izgrađen puno intermedijer grana na putu. Ako mi samo ikada pogledati 4 stvari, 4 je samo konstantna. Mi zapravo vrsta približava konstanta umetanje vrijeme i stalno Vrijeme pretraživanja. Tradeoff, naravno, u tome što ovo Trie, kao što vjerojatno možete reći, je ogroman. Svaka od tih čvorova zauzima puno prostora. 

Ali to je tradeoff. Ako želimo stvarno brzo umetanje, stvarno brzo brisanje, i stvarno brzo pretraživanje, moramo ima puno podataka leti okolo. Moramo izdvojiti puno prostora i memorija za tu strukturu podataka postojati. 

I tako to je tradeoff. No, izgleda da Možda su ga pronašli. Možda smo otkrili da Sveti gral strukture podataka s brzim umetanje, brisanje i pretraživanje. A možda će to biti odgovarajuća struktura podataka koristiti za bilo informacija Pokušavamo trgovine. Ja sam Doug Lloyd, ovo je cs50.