[MUSIC SPILLE] DOUG LLOYD: Så vi har blitt inching nærmere og nærmere den hellige gral av data strukturer, en som vi kan sette inn inn, slette fra, og ser opp i konstant tid. Høyre. Det er liksom i mål. Vi ønsker å være i stand til å gjøre ting veldig, veldig raskt. 

Har vi funnet den her da vi snakker om forsøk? Vel, la oss ta en titt. Så vi har sett flere forskjellige datastrukturer som håndterer kartlegging av såkalt nøkkelverdipar, kartlegge noen stykke data til noen annen del av data så vi vet hvor du finner Informasjonen i strukturen. 

Så for matrisen, for eksempel, Nøkkelen er element indeks eller matrise Plasseringen 0 eller matrisen 1 og så videre. Og verdien er dataene som finnes på denne plasseringen. Så hva er lagret i matrisen 0? Hva blir lagret i matrisen en versus bare 0 og 1, som ville være tastene. 

Med en hash table er det liksom den samme ideen. Med en hash table, har vi denne hash funksjon som genererer hash-koder. Så nøkkelen er hash-kode av dataene. Og verdien, særlig vi snakket om kjeding i videoen på hash tabeller, er at lenket liste av data som hasher til at hashCode. Høyre. Hva om en annen tilnærming denne metoden, skjønt? Hva om en metode der Nøkkelen er garantert å være unik, i motsetning til en hash table, der vi kunne ende opp med to deler av data som har samme hashCode. Og så må vi håndtere at ved å enten sondering eller mer svis chaining å løse det problemet. 

Så nå kan vi garantere at våre nøkkelen vil være unik. Og hva om vår verdi var bare noe så enkelt som sant og usant som forteller oss om eller ikke at opplysning eksisterer i strukturen? En boolsk kan være så enkelt som en bit. Realistisk er det sannsynligvis en byte mer sannsynlig enn en bit. Men det er mye mindre enn lagring kanskje en 50-tegns streng, for eksempel. 

Så prøver, i likhet med hasj tabeller, som kombinerer arrays og lenket liste, prøver kombinere matriser, strukturer, og pekere sammen for å lagre data i en interessant måte som er ganske forskjellig fra noe vi har sett så langt. Nå bruker vi dataene som et veikart å navigere denne datastrukturen. Og hvis vi kan følge veikart, hvis vi kan Følg data fra begynnelse til slutt, vil vi vet om at data eksistere i trie. 

Og hvis vi ikke kan følge kartet fra meningen å avslutte det hele tatt, dataene kan ikke eksistere. Igjen, nøklene her er garantert å være unik. Og så i motsetning til en hash table, vil vi aldri må forholde seg til kollisjoner her. Og ikke to stykker av data har nøyaktig samme veikart hvis ikke at data er identiske. 

Hvis vi setter inn John, deretter vi søker etter John. Det er to identiske stykker av data, ikke sant, vi ser gjennom. Men ellers, noen to stykker av data er garantert å ha unike veikart gjennom denne datastruktur. Og vi kommer til å ta en titt på en visuell av dette i løpet av et øyeblikk. 

Vi vil gjøre dette ved å prøve å opprette en ny datastruktur, kartlegge følgende sentrale verdiparene. I dette tilfellet er vi ikke kommer til å bruke noe så enkelt som en boolsk. Vi har faktisk lagrer strengen. Og at strengen skal være navnet på et universitet. 

Og nøkkelen kommer til å bli året da at universitetet ble grunnlagt. Alle år for universiteter kommer til å være fire sifre. Og så vil vi bruke disse fire sifrene til navigere gjennom denne datastrukturen. Og vi får se, igjen, hvordan vi gjør det i løpet av et sekund. 

Ved slutten av banen, vi får se navnet av universitetet som tilsvarer til at viktige, de fire sifre. Den grunnleggende ideen bak en trie er at vi har en sentral rute. Så tenk på det som et tre. Og dette er lik i rettskrivning og i konseptet til et tre. Vanligvis når vi tenker på trær i den virkelige verden, de har en rot som er i bakken og de vokser oppover og de har avdelinger og de har blader. Og i utgangspunktet ideen om en trie er akkurat det samme, bortsett fra at roten er forankret et sted i himmelen. Og bladene er på bunnen. 

Så det er litt som å ta et tre og bare vende det opp ned. Men det er fortsatt grener. Og de ville være våre veier, de vil være våre forbindelser fra roten til bladene. I dette tilfelle de som er stier, disse grenene er merket med tall som forteller oss hvilken vei å gå fra der vi er. 

Hvis vi ser en 0, går vi ned denne grenen, hvis vi ser en 1, går vi ned denne grenen, og så og så videre. Vel, hva betyr dette? Vel, det betyr at på hvert knutepunkt og hver node i midten og hver gren, det er 10 mulige steder som vi kan gå. Så det er 10 pekere fra hvert sted. 

Og det er her prøver kan få en litt skremmende for noen som er ikke har mye erfaring i datavitenskap før. Men prøver er egentlig ganske utrolig. Og hvis du har muligheten til å jobbe med dem og du er villig til å grave-in og eksperimentere med dem, de er egentlig ganske interessant datastrukturer å jobbe med. Hvis vi ønsker å sette inn et element inn i trie, alt vi trenger å gjøre er å bygge riktig bane fra roten til bladet. Her er hva hvert steg den måten kan se ut. Vi kommer til å definere en ny data Strukturen for en ny node som kalles en trie. 

Og innsiden av at data Strukturen det er to stykker. Vi kommer til å lagre navn på et universitet. Og vi kommer til å lagre en rekke pekere til andre noder av samme type. Så, igjen, dette er den slags av begrepet overalt vi er, vi på 10 mulige steder vi kan gå. Hvis vi ser en 0, går vi ned denne grenen. Hvis vi ser en en, denne grenen, og så videre og så videre og så videre. Hvis vi sier 9, går vi ned denne grenen. Så på hvert knutepunkt, vi kan gå 10 mulige steder. Så hver node må inneholde 10 pekere til andre noder, til 10 andre noder. 

Og dataene vi lagrer er bare navnet på universitetet. Så la oss bygge en trie. La oss sette inn et par av elementer i vår trie. Så helt på toppen, dette er vår root node. Dette er trolig kommer til å være noe du kommer til globalt olle. Og du kommer til globalt opprett en peker til denne noden alltid. 

Du kommer til å si, root lik, og du er kommer til malloc selv trie node. Og du aldri kommer å røre rot igjen. Hver gang du vil begynne å navigere gjennom, du setter en annen pekeren lik rot, slik som trav, som er eksempel I bruker i mange av mine videoer her på stabler og køer og link lister og så videre. 

Du setter en annen peker kalt trav for traversering. Og du bruker trav å navigere gjennom datastrukturen. Så la oss se hvordan dette kan se ut. Så akkurat nå, hva ikke en node se ut? Vel, akkurat som våre data struktur erklæring antydet, vi har en streng, hvilken i dette tilfellet er tom. Det er ingenting her. 

Og en rekke 10 pekere. Og akkurat nå, bare vi har en node i dette trie. Det er ingenting annet i det. Så alt 10 av dem pekere punkt til null. Det er det den røde indikerer. 

La oss sette strengen Harvard. La oss sette Universitetet i Harvard inn i denne trie, som ble grunnlagt i år 1 636. Vi ønsker å bruke nøkkelen, 1636, for å fortelle oss hvor vi er skal lagre Harvard i trie. Nå, hvordan kan vi gjøre det? 

Det kan se ut omtrent som dette. Vi starter ved roten. Og vi har disse 10 stedene vi kan gå. Roten er akkurat som en hvilken som helst annen node i trie. Det er 10 plasser vi kan gå herfra. 

Hvor skal vi sannsynligvis vil å gå hvis nøkkelen er 1 636? Det er egentlig to alternativer. Høyre. Vi kan bygge ut nøkkelen høyre til venstre og starte med seks. Eller vi kunne bygge nøkkelen fra venstre til høyre og starte med en. 

Det er nok mer intuitivt som et menneske å forstå vi vil bare gå til venstre mot høyre. Og så hvis jeg ønsker å sette inn Harvard inn i denne trie, Jeg ønsker sannsynligvis å starte ved å starte ved roten, ser på mine 10 alternativer foran meg, og sa Jeg ønsker å gå ned en bane. OK. 

Nå er en bane for tiden null. Så hvis jeg ønsker å fortsette ned banen å sette dette elementet inn i trie, Jeg må malloc en ny node, har en peke der, og da er jeg god til å gå. 

Så jeg i utgangspunktet er på et punkt hvor jeg står ved roten av treet, eller trie og det er 10 grener. Men hver gren har en gate foran den. Høyre. Fordi det er ikke noe annet er det. Ingen trygg passasje. Det betyr at det er ingenting ned noen av disse grenene. Hvis jeg ønsker å begynne å bygge noe jeg ønsker å fjerne porten. Jeg ønsker å fjerne porten foran nummer en. Og jeg ønsker å gå ned den. Og jeg ønsker å bygge et annet sted for meg å gå. 

Og det er det jeg har gjort her. Så en ikke lenger peker til null. Jeg har sagt det er trygt å gå ned her nå. Jeg bygde en annen node. Og når jeg kommer til det node, jeg har en annen avgjørelse å ta. Hvor skal jeg gå herfra? 

Vel, jeg har allerede gått ned en. Så nå vil jeg sannsynligvis til å gå ned 6. Høyre. Igjen, jeg har 10 steder jeg kan velge. Så la oss nå gå ned nummer seks. Så jeg fjerne gate foran nummer 6. Og jeg går der nede. Og jeg bygge en annen node. Og jeg har nådd et annet knutepunkt. 

Igjen, jeg har 10 valg for hvor jeg kan gå. Jeg har flyttet fra 1 til 6. Så nå vil jeg trolig gå til tre. 3, det er intet jeg kan gå. Så jeg må rydde veien og bygge meg en ny plass. Og så fra 3, der jeg ønsker å gå gjøre? Jeg ønsker å gå ned 6. 

Og, igjen, måtte jeg rydde vei for å gjøre det. Så nå har jeg brukt min nøkkel til å sette opprette noder og begynne å bygge denne trie. Jeg har begynt på roten. Jeg har gått ned 1636. Og nå er jeg på bunnen der på at node. Og du kan være i stand til å ser det på skjermen. 

Det er markert med gult. Det er der jeg er i dag. Min nøkkel er gjort. Jeg har brukt opp alle posisjoner i min nøkkel. Så jeg kan ikke gå videre. Så på dette punktet, alt jeg virkelig trenger å gjøre er å si, OK. Det er typen som ser ned på bakken, hvis du se for oss selv som denne typen bane med forskjellige tilkoblinger. Liksom ser ned og liksom spray maling Harvard på bakken. Det er navnet på denne. Vet det er det som er på dette stedet. Hvis vi begynner ved roten og vi går ned 1 og deretter 6 og deretter 3 og deretter 6, hvor er vi? Vel, hvis vi ser ned og vi ser Harvard, deretter vi vet at Harvard var grunnlagt i 1636 basert på den måten vi implementere dette datastruktur. Så det var forhåpentligvis grei. Vi kommer til å gjøre to flere innsettinger. Og forhåpentligvis vil det bidra til å ser dette gjøres to ganger mer. 

Nå, la oss sette inn et annet universitet. La oss sette Yale inn i denne trie. Yale ble grunnlagt i 1701. Så vi vil starte på rot, som vi alltid gjør. Og vi setter en traversering pekeren. Vi kommer til å bruke den til å bevege seg gjennom. Det første vi ønsker å gjøre er å gå nedover en sti. Det er det første sifferet av våre viktigste. Heldigvis skjønt, gjør vi ikke nødt til å gjøre noe arbeid denne gangen. Den en bane er allerede fjernet. Jeg ryddet det tidligere når jeg ble satt inn Harvard i 1636. Så jeg kan trygt bevege ned en og bare gå dit. Hvis kan flytte ned en. 

Men nå ønsker jeg å gå til syv. Jeg ryddet vei på seks. Jeg vet jeg kan trygt fortsett nedover 6 banen. Men jeg trenger å gå på 7 banen. Så hva må jeg gjøre? Vel, akkurat som før, jeg trenger bare å fjerne gate, komme seg ut av veien, og bygge en ny node fra 7 banen. Akkurat som dette. 

Så nå har jeg flyttet en og deretter 7. Og nå legger merke til, er jeg liksom av på denne nye subbranch. Høyre. Alt annet fra 16 på, jeg bryr meg ikke om. Jeg gjør ikke 16 noe. Jeg gjør 17 ting. 

Så nå fra 17 på, jeg må slags flamme nye stier her. Det neste sifferet min nøkkel er 0. Jeg tydeligvis ikke kan komme hvor som helst. Jeg bare bygget denne noden. Så jeg vet er det ingen stier fremover herfra. Så jeg må lage en selv. 

Så jeg malloc en ny node og har 0 poeng der. Og så en gang til, malloc jeg en ny node og har ett poeng der. Igjen, jeg har brukt opp min nøkkel, 1701. Så jeg ser ned og jeg spraymaling Yale. Det er navnet på denne noden. 

Og så nå hvis jeg noen gang trenger å se om Yale er i denne trie, begynner jeg ved roten, Jeg går ned 1701, og ser ned. Og hvis jeg ser Yale spray malt på bakken, og deretter Jeg vet Yale eksisterer i denne trie. La oss gjøre en mer. La oss sette Dartmouth i denne trie, som ble grunnlagt i 1769. 

Start ved roten igjen. Min første sifferet i min nøkkel er en. Jeg kan trygt flytte ned den veien. Det finnes allerede. Det neste sifferet i nøkkelen min er 7. Jeg kan trygt flytte ned den veien. Det eksisterer også. 

Min neste er 6. Herfra fra der jeg er i dag i gult der i det midterste node, 6 er for øyeblikket låst av. Hvis jeg ønsker å gå ned den veien, Jeg har til å bygge det selv. Så jeg skal malloc en ny node og har seks poeng der. Og så, igjen, jeg er Lynrask nye stier her. 

Så jeg malloc en ny node, slik at det fra at node-- banen tall 9-- og deretter nå hvis jeg reiser 1769 og jeg ser ned. Det er ingenting i dag spray malt der. Jeg kan skrive Dartmouth. Og jeg har satt inn Dartmouth i den trie. 

Så det er å sette inn ting inn i trie. Nå ønsker vi å søke etter ting. Hvordan søker vi etter ting i trie? Vel, det er ganske mye den samme ideen. Nå er vi bare bruke sifrene nøkkelen for å se om vi kan navigere fra roten til der vi ønsker å gå i trie. 

Hvis vi treffer en blindvei på noe punkt, deretter vi vet at dette elementet ikke kan finnes eller annet som bane ville har allerede blitt fjernet. Hvis vi gjør det hele veien til Til slutt, alt vi trenger å gjøre er å se ned og se om det er elementet vi leter etter. Hvis det er, suksess. Hvis det ikke, mislykkes. 

Så la oss søke etter Harvard i denne trie. Vi starter ved roten. Og, igjen, vi kommer til å skape en traversering peker å gjøre våre beveger seg for oss. Fra roten vi vet at første stedet vi trenger å gå er en, kan vi gjøre det? Ja vi kan. Hvis trygt eksisterer. Vi kan gå dit. 

Nå, det neste stedet vi trenger å gå er 6. Eksisterer den 6 sti herfra? Ja, det gjør det. Vi kan gå ned 6 banen. Og vi ender opp her. 

Kan vi gå ned tre stien herfra? Vel, som det viser seg, ja, det finnes også. Og kan vi få på seks sti herfra? Ja vi kan. 

Vi har ikke helt svarte spørsmålet ennå. Det er fortsatt en mer trinn, som nå er vi trenger å se ned og se om det er actually-- hvis vi leter etter Harvard, er at hva vi finner når vi utmatte nøkkelen? I eksempelet bruker vi her, årene er alltid fire sifre. Men du kanskje bruker eksempelet der du lagrer en ordbok med ord. 

Og så i stedet for å ha 10 pekere for min plassering, kan du ha 26. Én for hver bokstav i alfabetet. Og er det noen ord som balltre, som er en undergruppe av batch, f.eks. Og så selv om du kommer til enden av nøkkelen, og du ser ned, du kan ikke se hva du leter etter. 

Så har du alltid å traversere hele banen og deretter hvis du var vellykket stand å krysse hele banen, se ned og gjøre en endelig bekreftelse. Er det det jeg leter etter? Vel, jeg ser ned etter start ved toppen og går 1.636. Jeg ser ned. Jeg ser Harvard. Så, ja, lyktes jeg. Hva om det jeg leter etter er ikke i trie, skjønt. Hva om jeg leter etter Princeton, som ble grunnlagt i 1746. Og så 1 746 blir min nøkkel å navigere gjennom trie. Vel, jeg begynner ved roten. Og det første stedet jeg vil ha å går nedover en sti. Kan jeg gjøre det? Ja det kan jeg. 

Kan jeg gå ned 7 sti derfra? Ja, det kan jeg. Det finnes også. Men kan jeg gå ned fire sti herfra? Det er som å stille spørsmålet, kan Jeg går ned den lille firkanten som jeg har uthevet i gult? Det er ingenting der. Høyre. 

Det er ingen vei videre nedover fire bane. Hvis Princeton var i dette trie, at fire ville ha blitt ryddet for oss allerede. Og så på dette punktet Vi har nådd en blindvei. Vi kan ikke gå videre. Og så kan vi si, definitivt, nei. Princeton finnes ikke i dette trie. 

Så hva betyr alt dette? Høyre. Det er mye som skjer her. Det finnes pekere over alt. Og, som du kan se bare fra diagrammet, det er mye av noder som er slags flyr rundt. Men legg merke til hver gang vi ønsket å sjekke om noe var i trie, vi bare måtte gjøre 4 trekk. 

Hver gang vi ønsket å sette noe i trie, vi har å gjøre 4 trekk, muligens mallocing noen ting underveis. Men som vi så når vi satt inn Dartmouth i den trie, noen ganger noen av banen kan allerede være ryddet for oss. Og slik som vår trie blir større og større, har vi mindre arbeid hver gang for å sette inn nye ting fordi vi allerede har bygget mye av den mellomliggende grener langs veien. Hvis vi bare trenger å se på 4 ting, er fire bare en konstant. Vi er slags nærmer konstant tid innsetting og konstant tid oppslag. Ulempen er selvfølgelig være at dette trie, som du kan sikkert fortelle, er enorme. Hver og en av disse nodene tar opp mye plass. 

Men det er kompromisset. Hvis vi ønsker virkelig rask innsetting, virkelig rask sletting, og veldig rask oppslag, må vi har mye data som flyr rundt. Vi må sette av mye plass og minne for den datastrukturen å eksistere. 

Og så det er kompromisset. Men det ser ut som vi kanskje har funnet det. Vi har kanskje funnet ut at hellige gral av datastrukturer med rask innsetting, sletting, og oppslag. Og kanskje dette vil være en passende datastrukturen til bruk for den informasjonen vi prøver å lagre. Jeg er Doug Lloyd, dette er CS50.