[Musik spiller] DOUG LLOYD: Så vi har været udtørrede tættere og tættere at hellige gral af data strukturer, som vi kan indsætte ind, slette fra, og se op i konstant tid. Højre. Det er en slags målet. Vi ønsker at være i stand til at gøre tingene meget, meget hurtigt. 

Har vi fandt det her, når vi taler om forsøg? Nå, lad os tage et kig. Så vi har set flere forskellige datastrukturer at håndtere kortlægning af såkaldte nøgleværdipar, kortlægning nogle stykke data til en anden stykke data så vi ved, hvor man kan finde oplysninger i strukturen. 

Så for array, for eksempel Nøglen er elementet indeks eller matrix Placeringen 0 eller matricen 1 og så videre. Og værdien er dataene der eksisterer på dette sted. Så hvad der er gemt i arrayet 0? Hvad der er gemt i arrayet 1 versus blot 0 og 1, som ville være nøglerne. 

Med en hash tabel er det slags den samme idé. Med en hash tabel, har vi denne hash funktion, der genererer hash-koder. Så det vigtigste er hash koden for de data. Og værdien, især vi talte om at kæde i videoen på hash tabeller, er, at forbundet liste af data der hashes til denne hashCode. Højre. Hvad med en anden tilgang denne metode, selvom? Hvad med en metode, hvor nøglen er garanteret at være unikke, i modsætning til en hash tabel, hvor vi kunne ender med to stykker data har samme hashCode. Og så er vi nødt til at beskæftige sig med at ved enten sondering eller derover helst kæde at løse dette problem. 

Så nu kan vi garantere at vores nøgle vil være unik. Og hvad hvis vores værdi var bare noget så nemt som sandt og falsk, der fortæller os, om eller ikke at stykke oplysninger findes i strukturen? En boolesk kunne være så simpelt som en smule. Realistisk er det sandsynligvis en byte mere sandsynligt end en smule. Men det er meget mindre end lagring måske en streng 50 tegn, for eksempel. 

Så forsøg, svarende til hash tabeller, som kombinerer arrays og linkede liste, forsøger kombinere arrays, strukturer, og henvisninger sammen for at lagre data i en interessant måde, der er temmelig forskellig fra noget vi har set hidtil. Nu bruger vi data som en køreplan at navigere denne datastruktur. Og hvis vi kan følge køreplanen, hvis vi kan Følg data fra begyndelsen til slutningen, vi får vide, om disse data findes i trie. 

Og hvis vi ikke kan følge kortet fra hvilket betyder at ende på alle, dataene kan ikke eksistere. Igen nøglerne her garanteret at være unik. Og så i modsætning en hash tabel, vil vi aldrig har at gøre med kollisioner her. Og ikke to stykker data har nøjagtig samme køreplan medmindre at data er identiske. 

Hvis vi indsætter John, derefter Vi søger efter John. Det er to identiske stykker data, højre, vi kigger igennem. Men ellers enhver to stykker af data garanteret at have unikke køreplaner gennem denne datastruktur. Og vi kommer til at tage et kig på en visuel af denne på blot et øjeblik. 

Vi vil gøre dette ved at forsøge at oprette en ny datastruktur, kortlægning følgende centrale værdi par. I dette tilfælde er vi ikke kommer til at bruge noget så simpelt som en boolesk. Vi har faktisk gemmer strengen. Og at strengen vil være navnet på et universitet. 

Og nøglen bliver året når at universitetet blev grundlagt. Alle år for universiteterne vil være fire cifre. Og så vi vil bruge disse fire cifre til navigere gennem denne datastruktur. Og vi vil se igen, hvordan vi gør det på bare et sekund. 

Ved enden af ​​stien, vi vil se navnet af universitetets, der svarer til denne nøgle, de fire cifre. Den grundlæggende idé bag en trie er, at vi har en central rute. Så tænker over det som et træ. Og det er ens i stavemåde og koncept til et træ. Generelt, når vi tænker på træer i den virkelige verden, de har en rod, der er i jorden og de vokser opad og de har afdelinger og de har blade. Og dybest set ideen om en trie er nøjagtig den samme, bortset fra at roden er forankret et eller andet sted på himlen. Og bladene er i bunden. 

Så det er lidt ligesom at tage et træ og bare flippe det på hovedet. Men der er stadig grene. Og de ville være vore veje, dem vil være vores forbindelser fra roden til bladene. I dette tilfælde, der stier, disse filialer er mærket med tal, der fortæller os hvilken vej at gå fra hvor vi er. 

Hvis vi ser en 0, vi går ned denne gren, hvis vi ser en 1, vi går ned denne gren, og så og så videre. Nå, hvad betyder det? Tja, det betyder, at ved hvert forbindelsespunkt og hver node i midterste og hver gren, der er 10 mulige steder, vi kan gå. Så der er 10 pejlemærker fra hvert sted. 

Og det er her, forsøger kan få en lille smule skræmmende for nogen der er ikke har en masse erfaring i datalogi før. Men forsøger er virkelig temmelig awesome. Og hvis du har den chance for at arbejde med dem og du er villig til at grave-i og eksperimentere med dem, de er virkelig ganske interessant datastrukturer at arbejde med. Hvis vi ønsker at indsætte et element ind i trie, alt, hvad vi behøver at gøre er bygget den korrekte sti fra roden til bladet. Her er, hvad hvert skridt langs den måde kunne se ud. Vi kommer til at definere en ny data struktur for et nyt knudepunkt kaldes en trie. 

Og inde i, at data struktur er der to stykker. Vi kommer til at gemme navn på et universitet. Og vi kommer til at gemme et array af pointere til andre knudepunkter af samme type. Så igen, det er den slags af begrebet overalt vi er, vi ved 10 mulige steder vi kan gå. Hvis vi ser en 0, vi går ned denne gren. Hvis vi ser en 1, denne filial, og så videre og så videre og så videre. Hvis vi siger 9, vi går ned denne gren. Så ved hvert forbindelsespunkt, vi kan gå 10 mulige steder. Så hver node skal indeholde 10 pejlemærker til andre knudepunkter, til 10 andre knudepunkter. 

Og de data, vi lagring er bare navnet på universitetet. Så lad os bygge en trie. Lad os indsætte et par af elementer i vores trie. Så på toppen, dette er vores rod node. Dette er sandsynligvis vil være noget du kommer til globalt erklære. Og du kommer til globalt at opretholde en pointer til denne node altid. 

Du kommer til at sige, rod lig, og du er kommer til at allokere selv trie node. Og du aldrig kommer at røre root igen. Hver gang, du ønsker at begynde at navigere igennem, du indstille en anden pointer lig med rod, såsom trav, som er eksempel I bruge i mange af mine videoer her på stakke og køer og link-lister og så videre. 

Du sætter en anden pointer kaldt trav til traversal. Og du bruger trav til at navigere gennem datastrukturen. Så lad os se, hvordan det kan se ud. Så lige nu, hvad gør en node ud? Nå, lige som vores data struktur erklæring angivet, vi har en streng, der i dette tilfælde er tom. Der er ikke noget her. 

Og en vifte af 10 pointere. Og lige nu kun vi, har 1 node i denne trie. Der er ikke noget andet i det. Så alle 10 af dem pointere point til null. Det er, hvad den røde indikerer. 

Lad os indsætte strengen Harvard. Lad os indsætte Universitet Harvard ind i denne trie, som blev grundlagt i år 1636. Vi ønsker at bruge nøglen, 1636, for at fortælle os, hvor vi er skal opbevares Harvard i trie. Nu, hvordan kan vi gøre det? 

Det kunne se sådan ud. Vi starter ved roden. Og vi har disse 10 steder vi kan gå. Roden er ligesom enhver andet knudepunkt af trie. Der er 10 steder vi kan gå herfra. 

Hvor vil vi sikkert gerne at gå, hvis nøglen er 1636? Der er virkelig to muligheder. Højre. Vi kan bygge nøglen fra højre til venstre og starte med 6. Eller vi kunne bygge nøglen fra venstre til højre og begynder med 1. 

Det er sandsynligvis mere intuitiv som menneske til at forstå, vi vil bare gå til venstre mod højre. Og så hvis jeg ønsker at indsætte Harvard ind i denne trie, Jeg sandsynligvis ønsker at starte ved at starte ved roden, ser på mine 10 indstillinger foran mig, og siger Jeg ønsker at gå ned ad en sti. OK. 

Nu 1 sti er i øjeblikket null. Så hvis jeg ønsker at fortsætte den vej at indsætte dette element i trie, Jeg er nødt til malloc en ny node, have 1 pege der, og så er jeg god til at gå. 

Så jeg dybest set er på et punkt, hvor jeg står ved roden af ​​træet eller Trie og der er 10 filialer. Men hver gren har en gate foran det. Højre. Fordi der ikke er noget andet der er. Ingen sikker passage. Det betyder, at der ikke er noget ned nogen af ​​disse filialer. Hvis jeg ønsker at begynde at bygge noget, jeg ønsker at fjerne porten. Jeg vil fjerne porten foran nummer 1. Og jeg ønsker at gå ned det. Og jeg ønsker at opbygge et andet sted for mig at gå. 

Og det er, hvad jeg har gjort her. Så 1 ikke længere peger til null. Jeg har sagt det er sikkert at gå ned her nu. Jeg byggede en anden node. Og når jeg kommer til det knudepunkt, jeg har en anden beslutning om at gøre. Hvor skal jeg gå herfra? 

Tja, jeg har allerede gået ned 1. Så nu har jeg nok ønsker at gå ned i 6. Højre. Igen, jeg har 10 steder jeg kan vælge. Så lad os nu gå ned nummer 6. Så jeg rydde porten foran nummer 6. Og jeg går dernede. Og jeg bygge en anden node. Og jeg har nået en anden krydset punkt. 

Igen, jeg har 10 valgmuligheder til, hvor jeg kan gå. Jeg har flyttet fra 1 til 6. Så nu har jeg nok ønsker at gå til 3. 3, der er ingen steder jeg kan gå. Så jeg er nødt til at bane vejen og bygge mig en ny plads. Og derefter fra 3, hvor gør jeg ønsker at gå? Jeg ønsker at gå ned 6. 

Og igen, jeg var nødt til at bane vejen for at gøre det. Så nu har jeg brugt min nøgle til at indsætte skabe knudepunkter og begynde at bygge denne trie. Jeg er begyndt ved roden. Jeg har gået ned 1636. Og nu er jeg på bunden der på denne node. Og du kan være i stand til at se det på din skærm. 

Det er markeret med gult. Det er, hvor jeg i øjeblikket er. Min nøgle er færdig. Jeg har opbrugt hver position i min nøgle. Så jeg kan ikke gå længere. Så på dette punkt, alt hvad jeg virkelig skal gøre er at sige, OK. Det er lidt ligesom at kigge ned på jorden, hvis du forestille dig selv som denne slags vej med forskellige forbindelser. Slags ser ned og sortering af sprøjtemaling Harvard på jorden. Det er navnet på dette. Ved det er, hvad der er på denne placering. Hvis vi starter ved roden, og vi går ned 1 og derefter 6 og derefter 3 og derefter 6, hvor er vi? Tja, hvis vi ser ned og vi ser Harvard, så vi ved, at Harvard var grundlagt i 1636 baseret på den måde vi gennemføre denne datastruktur. Så det var forhåbentlig ligetil. Vi kommer til at gøre to flere indrykninger. Og forhåbentlig vil bidrage til at se dette gjort to gange mere. 

Lad os nu indsætte et andet universitet. Lad os indsætte Yale ind i denne trie. Yale blev grundlagt i 1701. Så vi vil starte på rod, som vi altid gør. Og vi sætter en traversal pointer. Vi kommer til at bruge det til at bevæge sig igennem. Den første ting, vi ønsker at gøre er at gå ned ad en vej. Det er det første ciffer i vores nøgle. Heldigvis selvom, vi ikke nødt til at gøre noget arbejde denne gang. Den 1 stien er allerede blevet ryddet. Jeg blokerede den tidligere, når jeg blev indsætte Harvard på 1.636. Så jeg kan trygt bevæge ned 1 og bare gå der. Hvis der kan bevæge sig ned i 1. 

Men nu jeg ønsker at gå til 7. Jeg ryddet vejen ved 6. Jeg ved, jeg kan trygt Fortsæt ned 6 sti. Men jeg har brug for at fortsætte den 7. vej. Så hvad skal jeg gøre? Nå, ligesom før, jeg har bare brug for at rydde porten, komme ud af den måde, og bygge en ny knude fra 7 sti. Ligesom dette. 

Så nu har jeg flyttet 1 og derefter 7. Og nu mærke til, er jeg sortere af denne nye subbranch. Højre. Alt andet fra 16 på, jeg er ligeglad om. Jeg gør ikke 16 noget. Jeg laver 17 ting. 

Så nu fra 17 på, jeg er nødt til slags blis nye stier her. Det næste ciffer min nøgle er 0. Jeg kan naturligvis ikke komme nogen steder. Jeg har lige bygget denne node. Så jeg ved, der er ingen stier frem herfra. Så jeg er nødt til at lave en selv. 

Så jeg malloc en ny knude og har 0 point der. Og så en gang mere, jeg malloc en nyt knudepunkt og har et tidspunkt. Igen, jeg har opbrugt min nøgle, 1701. Så jeg kigger ned, og jeg spraymaling Yale. Det er navnet på denne node. 

Og så nu, hvis jeg nogensinde har brug for at se, om Yale er i denne Trie, jeg starter ved roden, Jeg går ned 1701, og ser ned. Og hvis jeg ser Yale spray malet på jorden, så Jeg ved Yale eksisterer i denne trie. Lad os gøre en mere. Lad os indsætte Dartmouth ind i denne Trie, som blev grundlagt i 1769. 

Start ved roden igen. Min første ciffer i min nøgle er 1. Jeg kan trygt flytte den vej. Det eksisterer allerede. Det næste ciffer i min nøgle er 7. Jeg kan trygt flytte den vej. Det eksisterer også. 

Mit næste er 6. Herfra hvor jeg i øjeblikket er i gul der i denne midterste knudepunkt, 6 er i øjeblikket låst ud. Hvis jeg ønsker at gå den vej, Jeg er nødt til at bygge det selv. Så jeg vil malloc en ny knude og har 6 point der. Og så igen, jeg er flammende nye stier her. 

Så jeg malloc en ny knude, så fra at node-- kanalnummer 9-- og så nu hvis jeg rejser 1769 og jeg ser ned. Der er ikke noget i øjeblikket spray malet der. Jeg kan skrive Dartmouth. Og jeg har indsat Dartmouth i trie. 

Så det er at indsætte ting ind i trie. Nu ønsker vi at søge efter ting. Hvordan kan vi søge efter ting i trie? Tja, det er temmelig meget den samme idé. Nu skal vi bare bruge cifrene i nøglen at se, om vi kan navigere fra roden til hvor vi ønsker at gå i trie. 

Hvis vi ramt en blindgyde på noget tidspunkt, så vi ved, at dette element ikke kan findes eller andet, vej ville Der er allerede blevet ryddet. Hvis vi gør det hele vejen til enden, alt, hvad vi behøver at gøre er at kigge ned og se, om det er elementet, vi leder efter. Hvis det er, succes. Hvis det ikke er, mislykkes. 

Så lad os søge efter Harvard i denne trie. Vi starter ved roden. Og igen, vi kommer til at skabe en traversal pointer at gøre vores bevægelser for os. Fra roden ved vi, at første sted vi nødt til at gå er 1, kan vi gøre det? Ja vi kan. Hvis der findes sikkert. Vi kan gå der. 

Nu er den næste sted, vi skal gå, er 6. Har 6 stien eksisterer herfra? Ja, det gør. Vi kan gå ned 6 sti. Og vi ender her. 

Kan vi gå ned 3 stien herfra? Nå, da det viser sig, ja, der findes også. Og kan vi få på 6 stien herfra? Ja vi kan. 

Vi har ikke helt besvaret spørgsmålet endnu. Der er stadig en mere trin, som nu er vi nødt til at kigge ned og se, om det er actually-- hvis vi leder efter Harvard, er, at hvad vi finder, når vi udtømme nøglen? I det eksempel, vi bruger her, årene er altid fire cifre. Men du kan være ved hjælp af eksempel, hvor du gemmer en ordbog over ord. 

Og så i stedet for at have 10 pejlemærker for min placering, kan du have 26. En for hvert bogstav i alfabetet. Og der er nogle ord som flagermus, som er en delmængde af batch, f.eks. Og så selvom du kommer til enden af ​​nøglen, og du kigger ned, du måske ikke se, hvad du leder efter. 

Så du altid har til at krydse hele stien og derefter hvis du var held i stand til at krydse hele stien, kigge ned og gøre en sidste bekræftelse. Er det, hvad jeg leder efter? Nå, jeg ser ned efter start øverst og går 1636. Jeg ser ned. Jeg ser Harvard. Så, ja, det lykkedes jeg. Hvad hvis det, jeg leder efter er ikke i Trie, selv om. Hvad hvis jeg leder efter Princeton, som blev grundlagt i 1746. Og så 1746 bliver min nøgle til at navigere gennem trie. Nå, jeg starter ved roden. Og det første sted jeg vil have til går ned i 1 stien. Kan jeg gøre det? Ja jeg kan. 

Kan jeg gå ned 7 stien derfra? Ja, jeg kan. Der findes også. Men kan jeg gå ned i 4 stien herfra? Det er som at stille spørgsmålet, kan Jeg fortsætter ned at lille firkant at jeg har fremhævet med gult? Der er ikke noget der. Højre. 

Der er ingen vej frem nede 4 sti. Hvis Princeton var i denne trie, at 4 ville have været ryddet for os allerede. Og så på dette punkt Vi har nået en blindgyde. Vi kan ikke gå længere. Og så vi kan sige, endeligt, nej. Princeton findes ikke i denne trie. 

Så hvad betyder alt dette? Højre. Der er en masse foregår her. Der er pegepinde over det hele. Og som du kan se lige fra diagrammet, der er en masse noder, er slags flyver rundt. Men mærke hver gang vi ønskede at kontrollere, om der var noget i trie, Vi havde kun at lave 4 træk. 

Hver gang vi ønskede at indsætte noget i trie, vi er nødt til at gøre 4 bevæger sig, muligvis mallocing nogle ting undervejs. Men som vi så, da vi indsat Dartmouth i trie, undertiden nogle af stien måske allerede blive ryddet for os. Og så vores Trie bliver større og større, har vi at gøre mindre arbejde, hver gang at indsætte nye ting fordi vi har allerede bygget en masse af mellemproduktet grene undervejs. Hvis vi kun nogensinde nødt til at se på 4 ting, 4 er bare en konstant. Vi er virkelig slags nærmer konstant tid indsættelse og konstant tid opslag. Tradeoff naturligvis er, at denne trie, som du kan sandsynligvis fortælle, er enorme. Hver af disse knuder optager en masse plads. 

Men det er den afvejning. Hvis vi ønsker virkelig hurtig insertion, virkelig hurtig sletning, og virkelig hurtig opslag, vi er nødt til at har en masse data flyver rundt. Vi er nødt til at afsætte en masse plads og hukommelse til at datastruktur at eksistere. 

Og så er det tradeoff. Men det ser ud som vi kunne have fundet det. Vi kunne have fundet, at hellige gral af datastrukturer med hurtig indsættelse, deletion og opslag. Og måske dette vil være en passende datastruktur til brug for de oplysninger vi forsøger at gemme. Jeg er Doug Lloyd, det er CS50.