KEVIN SCHMID: Noen ganger, når du bygger en program, kan det være lurt å bruke en datastruktur som kalles en ordbok. En ordbok kart nøkler, som er vanligvis strenger, til verdier, ints, tegn, en peker til et objekt, hva vi ønsker. Det er akkurat som vanlige ordbøker som kart ord gjennom definisjoner. 

Ordbøker gi oss den Muligheten til å lagre informasjon assosiert med noe og slå det opp senere. Så hvordan skal vi faktisk gjennomføre en ordbok i for eksempel C-kode som vi kan bruke i et av våre programmer? Vel, det er mange måter som vi kunne implementere en ordbok. 

For én, kan vi bruke en matrise som vi dynamisk re-størrelse eller vi kunne bruke en lenket liste, hash table eller et binært tre. Men uansett hva vi velger, bør vi være oppmerksom på effektivitet og utførelse av gjennomføringen. Vi bør tenke på algoritmen som brukes å sette inn og se opp elementer inn vår datastruktur. 

For nå, la oss anta at vi ønsker å bruke strenger som nøkler. La oss snakke om én mulighet, en datastruktur som kalles en trie. Så her er en visuell representasjon av en trie. 

Som bildet antyder, en trie er et tre datastruktur med noder koblet sammen. Vi ser at det er helt klart en rot node med noen linker som strekker seg til andre noder. Men hva betyr hver node består av? Hvis vi antar at vi lagrer nøkler med bare alfabetiske tegn, og vi bryr oss ikke om kapitalisering, her er en definisjon av en node som vil være nok. 

Et objekt som type er struct node har to deler kalt data og barn. Vi har forlatt data del som en kommentar for å bli erstattet av en-komponent erklæring når struct node er innarbeidet i en C-program. Dataene del av en node kan være en Boolsk verdi for å indikere hvorvidt ikke noden betegner fullføringen av en ordbok nøkkel eller det kan være en streng som representerer definisjonen av et ord i ordlisten. 

Vi vil bruke en smiley face å indikere når data er tilstede i en node. Det er 26 elementer i vår barn array, en indeks per bokstav. Vi får se betydningen av dette snart. 

La oss ta en nærmere titt på rotnoden i vårt diagram, som ikke har noen data forbundet med den, som antydet med den fravær av smilefjes i datadelen. De piler som strekker seg fra de delene av barna matrise representerer ikke-node pekere til andre noder. For eksempel, med pilen som strekker seg fra det andre elementet i barn representerer bokstaven B i en ordbok nøkkel. Og i større diagram vi merke det med en B. 

Legg merke til at i den større diagrammet, når vi tegner en peker til en annen node, det spiller ingen rolle hvor pilspissen møter den andre noden. Vår eksempel ordbok trie inneholder to ord, som og zoom. La oss gå gjennom et eksempel på leter opp data for en nøkkel. 

Anta at vi ønsket å slå opp Tilsvarende verdi for nøkkel-bad. Vi begynner vår titt opp ved roten node. Så får vi ta den første bokstaven i vår nøkkel, B, og finne tilsvarende få øye på i vår barn array. Legg merke til at det er nøyaktig 26 spots i matrisen, ett for hver bokstav i alfabetet. Og vi vil ha flekkene representerer bokstavene i alfabetet i rekkefølge. 

Vi skal se på den andre indeksen da, index en, for B. Generelt, hvis vi har noen bokstav C vi kunne finne den tilsvarende sted i barn array ved hjelp en beregning som dette. Vi kunne ha brukt større barn matrise hvis vi ønsket å tilby titt opp av taster med et bredere spekter av karakterer, for eksempel hele ASCII-tegnsettet. 

I dette tilfelle pekeren i våre barn matrise på index man ikke er null. Så vi vil fortsette å se opp nøkkelen bad. Hvis vi noen gang støtt på en nullpeker på riktig sted i barna matrise mens vi krysset nodene, Da må vi si at vi kunne ikke finne noe for den tasten. 

Nå vil vi ta den andre bokstaven i vår nøkkel, A, og fortsett med å følge pekere på denne måten før vi kommer til slutten av våre viktigste. Hvis vi nå enden av nøkkelen uten treffe noen blindveier, null pekere, som tilfellet er her, da bare vi må sjekke en ting til. Er dette nøkkelen faktisk i ordlisten? 

I så fall bør vi finne en verdi, vel en smilefjes-ikonet i vår diagrammet der ordet ender. Hvis det er noe annet som er lagret med dataene, så vi kan returnere den. For eksempel, er nøkkelen zoo ikke i ordbok, selv om vi kunne ha nådd slutten av denne nøkkelen uten noensinne treffer en nullpeker, mens vi iterere gjennom trie. 

Hvis vi prøvde å slå opp nøkkelen bad, nest siste node fylking indeks, svarende til bokstaven H, ville har hatt en nullpeker. Så bad er ikke i ordboken. Og så en trie er unik i at nøklene aldri er eksplisitt lagret datastrukturen. Så hvordan setter vi gjør noe inn en trie? 

La oss sette inn nøkkelen dyrehage i vår trie. Husk at et smilefjes på en node kan tilsvare i koden for en enkel Boolsk verdi for å indikere at zoo er i ordlisten, eller det kunne tilsvare mer informasjon som vi ønsker å assosiere med nøkkelen zoo, som definisjonen av ord eller noe annet. På en måte, til prosessen sette noe inn en trie ligner ser opp noe i en trie. 

Vi begynner med rotnoden igjen, følgende tips som tilsvarer bokstavene i vår nøkkel. Heldigvis var vi i stand til å følge pekere helt til vi nådde slutten av nøkkelen. Siden dyrehagen er et prefiks av ordet zoom, som er medlem av ordbok, trenger vi ikke å tildele eventuelle nye noder. 

Vi kan modifisere knutepunktet for å indikere at banen for tegnene som fører til det representerer en nøkkel i vår ordbok. Nå, la oss prøve å sette inn Nøkkelen BATH inn i trie. Vi begynner ved roten noden og følg pekere igjen. Men i denne situasjonen, vi traff en død slutt før vi er i stand til å komme til slutten av nøkkelen. Nå må vi fordele litt nytt noder må tildele en ny node for hver gjenværende brev av våre viktigste. 

I dette tilfelle vi bare trenger å tildele en ny node. Da må vi gjøre H-indeksen referere til denne nye noden. Nok en gang, kan vi endre node til indikerer at banen tegn fører til det representerer en nøkkel i vår ordbok. La oss resonnere om den asymptotiske kompleksiteten i våre prosedyrer for disse to operasjoner. 

Vi legger merke til at i begge tilfeller antallet av trinn vår algoritme tok ble proporsjonal med antallet bokstaver i søkeordet. Det er riktig. Når du ønsker å slå opp et ord i en trie du trenger bare å reagere gjennom bokstavene en etter en til du enten kommer til slutten av ordet eller traff en blindvei i trie. 

Og når du ønsker å sette inn en nøkkel verdi-par i en trie bruker prosedyren vi diskuterte, verste fall vil ha deg tildeling av en ny node for hver bokstav. Og vi vil anta at tildeling er en konstant tidsoperasjon. Så hvis vi antar at nøkkellengden er som er avgrenset av en fast konstant, både innsetting og ser opp er konstant gang operasjoner for en trie. 

Hvis vi ikke gjør denne antakelsen at nøkkellengden er avgrenset av en fast konstant, så innsetting og ser opp, i verste fall, blir lineær i Lengden av nøkkelen. Legg merke til at antall elementer som er lagret i trie påvirker ikke utseendet opp eller innsetting tid. Det er bare påvirket av den Lengden av nøkkelen. 

Som kontrast, legge til oppføringer til, si, en hash table tendens til å gjøre fremtiden ser opp saktere. Selv om dette kan høres tiltalende i starten, Vi bør huske på at en gunstig asymptotiske kompleksitet gjør ikke betyr i praksis at dataene Strukturen er nødvendigvis hinsides kritikk. Vi må også tenke på at for å lagre en ord i en trie vi trenger, i verste tilfelle, et antall noder proporsjonal til lengden av selve ordet. 

Prøver en tendens til å bruke mye plass. Det er i motsetning til en nøkkeltabell, hvor vi trenger bare en ny node til lagre noen suse_register_auto.ycp. Nå, igjen i teorien, stor plass forbruket ser ikke ut som en stor håndtere, særlig gitt at moderne datamaskiner har gigabyte og gigabyte minne. Men det viser seg at vi fortsatt har å bekymre deg for minnebruk og organisasjon for moro skyld ytelse, siden moderne datamaskiner har mekanismer på plass under hette for å øke hastigheten på minnetilgang. 

Men disse mekanismene fungerer best når minneaksesser er laget i kompakt regioner eller områder. Og noder av en trie kunne oppholde hvor som helst i denne haugen. Men disse er avveininger at vi må vurdere. 

Husk at når du velger en data Strukturen for en viss oppgave, vi bør tenke på hva slags operasjoner datastrukturen må støtte og hvor mye ytelsen av hver av disse operasjoner er viktig for oss. Disse operasjonene kan selv utvide utover bare grunnleggende utseende opp og innsetting. Anta at vi ønsket å gjennomføre en slags av autofullfør-funksjonalitet, mye som Google søkemotor gjør. Det er, returnere alle nøklene og potensielt verdier som har en gitt prefiks. 

En trie er unikt nyttig for denne operasjonen. Det er ukomplisert å reagere gjennom den trie for hvert tegn i prefikset. Akkurat som en titt opp drift, vi kunne følge pekere tegn for tegn. Deretter, når vi kommer til slutten av prefiks, kunne vi iterere gjennom gjenværende del av datastrukturen ettersom en hvilken som helst av tastene utover dette punktet har prefikset. 

Det er også lett å få tak i denne oppføringen i alfabetisk rekkefølge siden elementer av barn matrise er ordnet alfabetisk. Så forhåpentligvis vil du vurdere gi forsøker et forsøk. Jeg er Kevin Schmid, og dette er CS50. 

Ah, dette er begynnelsen av nedgangen. Jeg beklager. Unnskyld. Unnskyld. Unnskyld. 

Strike fire. Jeg er ute. Unnskyld. Unnskyld. Unnskyld. Sorry for å gjøre den personen som har til å redigere dette gå gale. 

Unnskyld. Unnskyld. Unnskyld. Unnskyld. 

SPEAKER 1: Well done. Det var veldig bra gjort.