[MUSIK SPELA] DOUG LLOYD: Så vi har inching närmare och närmare den heliga graal av data strukturer, som vi kan sätta in in, radera från, och slå upp i konstant tid. Höger. Det är typ av målet. Vi vill kunna göra saker mycket, mycket snabbt. 

Har vi hittade det här när vi pratar om försök? Nåväl, låt oss ta en titt. Så vi har sett flera olika datastrukturer att hantera mappningen av så kallad nyckel-par, kartläggning viss bit data till någon annan bit data så vi vet var man kan hitta uppgifter i strukturen. 

Så för matris, till exempel, den Nyckeln är elementet index eller array läge 0 eller matrisen en och så vidare. Och värdet är data som existerar på den platsen. Så vad som lagras i uppsättningen 0? Vad lagras i uppsättningen 1 kontra bara 0 och 1, vilket skulle vara nycklarna. 

Med en hash-tabell är det slags samma idé. Med en hash bord, har vi denna hash funktion som genererar hash-koder. Så nyckeln är hash-kod av uppgifterna. Och värdet, särskilt Vi pratade om kedja i videon på hashtabeller, är att länkad lista data som hashar till den hashkod. Höger. Vad sägs om en annan metod denna metod, men? Vad sägs om en metod där nyckeln är garanterad att vara unik, till skillnad från en hash-tabell, där vi kunde sluta med två datadelar har samma hashkod. Och då måste vi ta itu med att genom antingen sondering eller mer företrädesvis kedja för att åtgärda problemet. 

Så nu kan vi garantera att vår nyckel kommer att vara unik. Och vad händer om vårt värde var bara något som lätt så sant och falskt som berättar om eller inte denna del av information existerar i strukturen? Ett booleskt kan vara så enkelt som en bit. Realistiskt är det förmodligen en BYTE mer sannolikt än en bit. Men det är mycket mindre än lagring kanske en 50-teckensträng, till exempel. 

Så försök, liknande hash tabeller, som kombinerar arrayer och länkad lista, försöker kombinera arrayer, strukturer, och pekare tillsammans för att lagra data i ett intressant sätt som är ganska annorlunda från något vi har sett hittills. Nu använder vi uppgifterna som en färdplan att navigera denna datastruktur. Och om vi kan följa färdplanen, om vi kan följ data från början till slut, vi ska veta om dessa uppgifter existerar i trie. 

Och om vi inte kan följa kartan från betyder att sluta på alla, data kan inte existera. Återigen, nycklarna här är garanterat att vara unik. Och så till skillnad från en hash-tabell, vi ska aldrig måste ta itu med kollisioner här. Och ingen två bitar av uppgifter har exakt samma färdplan såvida dessa uppgifter är identiska. 

Om vi ​​sätter John, sedan vi söker för John. Det är två identiska bitar av uppgifter, rätt, vi letar igenom. Men annars, alla två bitar av data garanterat att ha unika färdplaner genom denna datastruktur. Och vi kommer att ta en titt på en visuell av detta på bara ett ögonblick. 

Vi gör detta genom att försöka skapa en ny datastruktur, kartläggning av följande nyckelpar värde. I det här fallet, vi kommer inte att använda något så enkelt som en Boolean. Vi faktiskt kommer att lagra strängen. Och det sträng kommer att vara namnet på ett universitet. 

Och nyckeln kommer att bli året när det universitetet grundades. Alla år för universiteten kommer att vara fyra siffror. Och så vi kommer att använda dessa fyra siffrorna till navigera genom denna datastruktur. Och vi får se, återigen, hur vi gör det på bara en sekund. 

Vid slutet av banan, vi får se namnet av universitetet som motsvarar till nyckeln dessa fyra siffror. Den grundläggande idén bakom en trie är att vi har en central rutt. Så tänk på det som ett träd. Och det är lika i stavning och koncept som ett träd. Generellt när vi tänker på träd i den verkliga världen, de har en rot som är i mark och de växer uppåt och de har filialer och de har blad. Och i princip idén om en trie är exakt densamma, med undantag av att rot är förankrad någonstans på himlen. Och bladen är i botten. 

Så det är ungefär som att ta ett träd och bara vända den upp och ner. Men det finns fortfarande grenar. Och de skulle vara våra vägar, de kommer att vara våra kontakter från roten till bladen. I det här fallet, de vägar, de grenar är märkta med siffror som berättar vilken väg att gå från där vi är. 

Om vi ​​ser en 0, vi går ner denna gren, om vi ser en 1, vi går ner denna gren, och så och så vidare. Tja, vad innebär det? Tja, innebär det att vid varje förbindelsepunkten och varje nod i mitten och varje gren, Det finns 10 möjliga platser som vi kan gå. Så det finns 10 pekare från varje plats. 

Och det är där försök kan få en lite skrämmande för någon som är inte har en hel del erfarenhet av datavetenskap innan. Men försök är verkligen ganska häftigt. Och om du har möjlighet att arbeta med dem och du är villig att gräva in och experimentera med dem, de är egentligen ganska intressant datastrukturer att arbeta med. Om vi ​​vill infoga ett element i trie, allt vi behöver göra är att bygga den rätta vägen från roten till bladet. Här är vad varje steg längs hur kan se ut. Vi kommer att definiera ett nytt data struktur för en ny nod som kallas en trie. 

Och inne av dessa uppgifter struktur finns två stycken. Vi kommer att lagra namn på ett universitet. Och vi kommer att lagra en array av pekare till andra noder av samma typ. Så, återigen, det är den sortens av begreppet överallt vi är, vi på 10 möjliga platser vi kan gå. Om vi ​​ser en 0, vi går ner denna gren. Om vi ​​ser en 1, denna gren, och så vidare och så vidare och så vidare. Om vi ​​säger 9, vi går ner denna gren. Så vid varje knutpunkt, vi kan gå 10 möjliga platser. Så varje nod måste innehålla 10 pekare till andra noder, till 10 andra noder. 

Och data vi lagrar är bara namnet på universitetet. Så låt oss bygga en trie. Låt oss sätta ett par artiklar i vår trie. Så högst upp, detta är vår rotnoden. Detta är förmodligen kommer att bli något du kommer att globalt deklarera. Och du kommer att globalt upprätthålla en pekare till denna nod alltid. 

Du kommer att säga, rot lika, och du är kommer att malloc själv trie nod. Och du kommer aldrig röra rot igen. Varje gång du vill börja navigera igenom, du ställa in en annan pekare lika med roten, såsom trav, vilket är det exempel jag användning i många av mina videor här på stackar och köer och länklistor och så vidare. 

Du anger en annan pekare kallas trav för traverse. Och du använder trav för att navigera genom datastrukturen. Så låt oss se hur det kan se ut. Så just nu, vad gör en nod ut? Jo, precis som våra data struktur förklaring anges, vi har en sträng, som i detta fall är tom. Det finns inget här. 

Och en mängd 10 pekare. Och just nu, bara vi har en nod i denna trie. Det finns inget annat i den. Så alla 10 av dem pekare peka på null. Det är vad den röda indikerar. 

Låt oss sätta strängen Harvard. Låt oss sätta universitet Harvard in i denna trie, vilket grundades år 1636. Vi vill använda nyckeln, 1636, för att tala om för oss där vi är kommer att Harvard lagra i trie. Nu, hur kan vi göra det? 

Det kan se ut så här. Vi börjar vid roten. Och vi har dessa 10 platser vi kan gå. Roten är precis som alla annan nod i trie. Det finns 10 platser vi kan gå härifrån. 

Var gör vi förmodligen vill att gå om nyckeln är 1636? Det finns egentligen två alternativ. Höger. Vi kan bygga nyckeln från höger till vänster och börja med 6. Eller vi kunde bygga nyckeln från vänster till höger och börjar med ett. 

Det är nog mer intuitivt som en människa att förstå att vi kommer bara gå till vänster till höger. Och så om jag vill infoga Harvard in i denna trie, Jag vill nog börja genom att börja vid roten, titta på mina 10 alternativ framför mig, och säger Jag vill gå ner en väg. OK. 

Nu är en väg för närvarande null. Så om jag vill fortsätta den vägen att införa detta element i trie, Jag måste malloc en ny nod, har en peka där, och så är jag bra att gå. 

Så jag är i grund och botten på en punkt där jag står vid roten av trädet eller trie och det finns 10 kontor. Men varje gren har en grind framför den. Höger. Eftersom det finns inget annat finns. Ingen säker passage. Det innebär att det finns inget ner någon av dessa grenar. Om jag vill börja bygga något, jag vill ta bort grinden. Jag vill ta bort grinden framför nummer ett. Och jag vill gå ner det. Och jag vill bygga en annan plats för mig att gå. 

Och det är vad jag har gjort här. Så 1 inte längre pekar på noll. Jag har sagt att det är säkert att gå här nere nu. Jag byggde en annan nod. Och när jag kommer till denna nod, jag har ett annat beslut att göra. Vart ska jag gå härifrån? 

Tja, jag har redan gått ner 1. Så nu vill jag nog att gå ner 6. Höger. Återigen, jag har 10 platser som jag kan välja. Så låt oss nu gå ner nummer 6. Så jag rensa porten framför nummer 6. Och jag går där nere. Och jag bygga en annan nod. Och jag har nått en annan knutpunkt. 

Återigen, jag har 10 val för där jag kan gå. Jag har flyttat 1-6. Så nu vill jag nog att gå till tre. 3, det finns ingenstans jag kan gå. Så jag måste bana väg och bygga mig en ny plats. Och sedan från 3, där jag vill gå? Jag vill gå ner 6. 

Och återigen, jag var tvungen att bana väg att göra det. Så nu har jag använt min nyckel för att infoga skapa noder och börja bygga denna trie. Jag har börjat vid roten. Jag har gått ned 1636. Och nu är jag på botten där på den noden. Och du skulle kunna se den på skärmen. 

Det är gulmarkerad. Det är där jag är för närvarande. Min nyckel sker. Jag har uttömt varje position i min nyckel. Så jag kan inte gå längre. Så på denna punkt, allt jag verkligen behöver göra är att säga, OK. Det är ungefär som att titta ner i marken, om du föreställa själv som denna typ av väg med olika anslutningar. Sorts tittar ner och typ av sprutmålning Harvard på marken. Det är namnet på denna. Vet att det är vad som finns på den här platsen. Om vi ​​börjar vid roten och vi går ner 1 och sedan 6 och sedan tre och sedan 6, Vart är vi? Tja, om vi tittar ner och vi ser Harvard, då Vi vet att Harvard var grundat 1636 baserat på vägen vi genomföra denna datastruktur. Så det var förhoppningsvis okomplicerad. Vi kommer att göra ytterligare två insättningar. Och förhoppningsvis kommer att bidra till att se detta gjort ytterligare två gånger. 

Nu ska vi sätta ett annat universitet. Låt oss sätta Yale i denna trie. Yale grundades 1701. Så vi börjar på rot, som vi alltid gör. Och vi sätter ett genomgångs pekare. Vi kommer att använda det för att gå igenom. Det första vi vill göra är att gå ner en väg. Det är den första siffran i vår nyckel. Lyckligtvis, men gör vi inte måste göra något arbete den här gången. 1 väg har redan raderats. Jag rensas det tidigare när jag var att sätta in Harvard vid 1636. Så jag kan säkert flytta ned 1 och bara åka dit. Om det inte går att flytta ner en. 

Men nu vill jag gå till 7. Jag banat väg vid 6. Jag vet att jag kan säkert fortsätta nedför 6 bana. Men jag måste fortsätta på 7 väg. Så vad behöver jag göra? Jo, precis som förut, jag behöver bara att rensa porten, få ur vägen, och bygga en ny nod från 7 väg. Precis som denna. 

Så nu har jag flyttat en och sedan 7. Och nu märker jag är typ av denna nya delförgrening. Höger. Allt annat 16 på, jag bryr mig inte om. Jag gör 16 någonting. Jag gör 17 saker. 

Så nu från 17, jag måste sorts flamma nya spår här. Nästa siffra min nyckel är 0. Jag uppenbarligen inte kan komma någonstans. Jag byggde just denna nod. Så jag vet att det finns ingen vägar framåt härifrån. Så jag måste göra en själv. 

Så jag malloc en ny nod och har 0 poäng där. Och sedan en gång till, malloc jag ny nod och har en poäng där. Återigen, jag har uttömt min nyckel, 1701. Så jag ser ner och jag sprayfärg Yale. Det är namnet på denna nod. 

Och så nu om jag någonsin behöver se om Yale är i detta trie, jag börjar vid roten, Jag går ner 1701, och tittar ner. Och om jag ser Yale sprut målade på marken, då Jag vet Yale finns i denna trie. Låt oss göra en till. Låt oss sätta Dartmouth i detta Trie, som grundades 1769. 

Börja vid roten igen. Min första siffran i min nyckel är en. Jag kan säkert gå den vägen. Det finns redan. Nästa siffra i min nyckel är 7. Jag kan säkert gå den vägen. Den finns också. 

Min nästa är 6. Härifrån, från där jag är för närvarande i gult där i den mellersta noden, 6 är för närvarande låst av. Om jag vill gå den vägen, Jag måste bygga den själv. Så jag ska malloc en ny nod och har sex poäng där. Och sedan, återigen, jag är flammande nya spår här. 

Så jag malloc en ny nod så att från att node-- tåglägesidentitet 9-- och sedan nu om jag reser 1769, och jag tittar ner. Det finns inget för närvarande Spraya målade där. Jag kan skriva Dartmouth. Och jag har insatt Dartmouth in i trie. 

Så det är att sätta in saker i trie. Nu vill vi att leta efter saker. Hur ska vi söka efter saker i trie? Tja, det är ganska mycket samma idé. Nu har vi bara använda siffrorna i nyckeln för att se om vi kan navigera från roten där vi vill gå i trie. 

Om vi ​​träffar en återvändsgränd vid något tillfälle, då Vi vet att denna omständighet inte kan före annars den vägen skulle har redan raderats. Om vi ​​gör det hela vägen till slutet, allt vi behöver göra är att titta ner och se om det är elementet vi letar efter. Om det är, framgång. Om det inte misslyckas. 

Så låt oss söka efter Harvard i denna trie. Vi börjar vid roten. Och, återigen, vi kommer att skapa en genomgångs pekare att göra våra rörelser för oss. Från roten vet vi att första vi måste gå är en, kan vi göra det? Ja vi kan. Om ett säkert sätt finns. Vi kan åka dit. 

Nu, nästa plats som vi måste gå är 6. Har 6 vägen existerar härifrån? Ja, det gör det. Vi kan gå ner 6 väg. Och vi hamna här. 

Kan vi gå ner i tre väg härifrån? Tja, som det visar sig, ja, finns det också. Och kan vi få på 6 väg härifrån? Ja vi kan. 

Vi har inte riktigt svarat frågan än. Det finns fortfarande ett mer steg, som nu är Vi måste titta ner och se om det är actually-- Om vi ​​letar efter Harvard, är att vad vi hittar när vi uttömmer nyckeln? I exemplet vi använder här, åren är alltid fyra siffror. Men du kanske ska använda exempel där du lagrar en ordbok av ord. 

Och så i stället för att ha 10 pekare för min plats, kanske du har 26. En för varje bokstav i alfabetet. Och det finns några ord som slagträ, vilket är en delmängd av sats, till exempel. Och så även om du kommer till änden av nyckeln och du tittar ner, du kanske inte se vad du letar efter. 

Så du alltid måste passera hela vägen och sedan om du var framgångsrikt kunna att korsa hela banan, titta ner och göra en slutlig bekräftelse. Är det vad jag letar efter? Tja, jag tittar ner efter start upptill och gå 1636. Jag tittar ner. Jag ser Harvard. Så, ja, lyckades jag. Tänk om vad jag letar efter är inte i trie, dock. Vad händer om jag letar efter Princeton, som grundades år 1746. Och så 1746 blir min nyckel att navigera genom trie. Tja, jag börjar vid roten. Och det första jag vill till går ner en väg. Kan jag göra det? Ja det kan jag. 

Kan jag gå ner i 7 väg därifrån? Ja, jag kan. Som existerar också. Men kan jag gå ner i fyra väg härifrån? Det är som att ställa frågan, kan Jag fortsätter ner det lilla torget att jag har markerat i gult? Det finns inget där. Höger. 

Det finns inget sätt framåt ned 4 väg. Om Princeton var i denna trie att 4 skulle ha rensats för oss redan. Och så på denna punkt Vi har nått en återvändsgränd. Vi kan inte gå längre. Och så att vi kan säga, definitivt, nej. Princeton existerar inte i denna trie. 

Så vad betyder då allt detta? Höger. Det är mycket som händer här. Det finns pekare överallt. Och, som ni kan se bara från diagrammet det finns en hel del noder som är typ att flyga runt. Men märker varje gång vi ville kontrollera om något var i trie, vi bara var tvungna att göra 4 drag. 

Varje gång vi ville infoga något i trie, Vi måste göra 4 rör sig, möjligen mallocing några saker längs vägen. Men som vi såg när vi införas Dartmouth in i trie, ibland en del av banan kanske redan rensas för oss. Och så vår trie blir större och större, vi har att göra mindre arbete varje gång att infoga nya saker eftersom vi har redan byggt en hel del av den mellanliggande grenar längs vägen. Om vi ​​bara har någonsin att titta på 4 saker, är 4 bara en konstant. Vi verkligen typ av närmar konstant tid insättning och konstant tid lookup. Kompromissen är naturligtvis är att Detta trie, som ni kan nog säga, är enorm. Var och en av dessa noder tar upp en hel del utrymme. 

Men det är kompromissen. Om vi ​​vill verkligen snabb insättning, riktigt snabb radering, och riktigt snabb sökning, måste vi har en hel del uppgifter som flyger runt. Vi måste avsätta en hel del utrymme och minne för den datastruktur Att finnas. 

Och så det är kompromissen. Men det ser ut som vi kanske har hittat det. Vi kanske har funnit att heliga graal datastrukturer med snabb insättning, radering och sökning. Och kanske detta kommer att bli ett lämplig datastruktur att använda för den information vi försöker att lagra. Jag är Doug Lloyd, är detta CS50.