>> 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.
>> Strike fire.
Jeg er ute.
Unnskyld.
Sorry for å gjøre den personen som har til å redigere dette gå gale.
>> Unnskyld.
Unnskyld.
>> SPEAKER 1: Well done.
Det var veldig bra gjort.