>> KEVIN SCHMID: Nogle gange, når man bygger en program, kan du ønsker at bruge en
datastruktur kendt som en ordbog.
A Dictionary kort nøgler, som er regel strygere, til værdier, ints,
tegn, en pointer til en genstand, hvad vi vil.
Det er bare som almindelige ordbøger at kort ord gennem definitioner.
>> Ordbøger give os den evne til at lagre information
forbundet med noget og slå det op senere.
Så hvordan kan vi faktisk gennemføre en ordbog i, siger, C-kode, som vi kan
brug i en af ​​vores programmer?
Nå, der er en masse måder, vi kunne gennemføre en ordbog.
>> For én, kunne vi bruge et array, vi dynamisk re-størrelse eller vi kunne bruge en
linkede liste, hash tabel eller et binært træ.
Men uanset hvad vi vælger, bør vi være opmærksom på effektivitet og
udførelsen af ​​implementeringen.
Vi bør tænke på den algoritme, der anvendes at indsætte og se op poster i
vores datastruktur.
>> For nu, lad os antage, at vi ønsker at bruge strenge som nøgler.
Lad os tale om en mulighed, en datastruktur kaldet en trie.
Så her er en visuel repræsentation af en trie.
>> Som billedet antyder, en trie er et træ datastruktur med
knudepunkter koblet sammen.
Vi ser, at der er helt klart en rod node med nogle links strækker sig
andre noder.
Men hvad betyder hver node består af?
Hvis vi antager, at vi opbevare nøgler med kun alfabetiske tegn, og
vi er ligeglad kapitalisering, her er en definition af en node, der
vil være tilstrækkeligt.
>> Et objekt, hvis type er struct node har to dele
kaldes data og børn.
Vi har forladt data del som en kommentar at blive erstattet af en komponent
erklæringen når struct node er inkorporeres i et C-program.
Datadelen af ​​et knudepunkt kan være en Boolesk værdi for at angive, om
ikke knudepunktet repræsenterer afslutningen af en ordbog nøgle eller det kan være en
streng, der repræsenterer definitionen af et ord i ordbogen.
>> Vi vil bruge et smilende ansigt for at angive når data er til stede i en knude.
Der er 26 elementer i vores børn array, et indeks
pr bogstav.
Vi vil se betydningen dette snart.
>> Lad os få et nærmere kig på roden node i vores diagram, som ikke har nogen data
forbundet med det, som det fremgår af fravær af det smilende ansigt i
datadel.
Pilene, der strækker sig fra de dele af børnene Array repræsenterer ikke-node
henvisninger til andre noder.
For eksempel pilen der strækker sig fra det andet element i børn
repræsenterer bogstavet B i en ordbog nøgle.
Og i større diagram vi mærke den med en B.
>> Bemærk, at i større diagram, når vi tegne en pointer til en anden node, det
ligegyldigt hvor pilespidsen opfylder dette andet knudepunkt.
Vores stikprøve ordbog trie indeholder to ord, der og zoom.
Lad os gå gennem et eksempel på ser op data for en nøgle.
>> Antag, at vi ønskede at se op tilsvarende værdi for nøglen bad.
Vi begynder vores udseende op ved roden node.
Så tager vi det første bogstav i vores nøgle, B, og finde den tilsvarende
øje på vores børn array.
Bemærk, at der er nøjagtig 26 spots i arrayet, en for hvert bogstav i
alfabetet.
Og vi vil have pletter repræsenterer bogstaver i alfabetet i orden.
>> Vi ser på det andet indeks da, indeks et, B. I almindelighed, hvis vi
har nogle bogstav C, vi kunne bestemme den tilsvarende plet
i børn array ved hjælp af en beregning som dette.
Vi kunne have brugt en større børn matrix, hvis vi ønskede at tilbyde udseendet af
nøgler med en bredere vifte af figurer, såsom hele
ASCII tegnsæt.
>> I dette tilfælde, er pointeren i vores børn array
indeks man ikke er nul.
Så vi vil fortsætte med at kigge nøglens bad.
Hvis vi nogensinde mødt en null-pointer på det rette sted i børnenes
vifte, mens vi gennemkøres knudepunkter, så vil vi nødt til at sige, at vi
kunne ikke finde noget for denne nøgle.
>> Nu vil vi tage det andet bogstav på vores nøgle, A, og fortsætte med at følge
pointere i denne måde, indtil vi nå slutningen af ​​vores nøgle.
Hvis vi når enden af ​​nøgle uden ramme nogen blindgyder, null pointers,
som det er tilfældet her, så vi kun nødt til at tjekke en ting mere.
Er denne nøgle faktisk i ordbogen?
>> Hvis det er tilfældet, bør vi finde en værdi, godt en smiley ikon ansigt i vores diagram, hvor
ordet ender.
Hvis der er noget andet gemt med data, så vi kan returnere den.
For eksempel, nøglen zoo ikke i ordbog, selv om vi kunne have
nået slutningen af ​​denne nøgle uden nogensinde rammer en null-pointer, mens vi
gentage gennem trie.
>> Hvis vi prøvede at kigge op nøglen bad, næstsidste node arrayindeks,
svarer til bogstavet H, ville har afholdt en null-pointer.
Så bad ikke findes i ordbogen.
Og så en trie er enestående i, at tasterne aldrig eksplicit lagret i
datastrukturen.
Så hvordan vi indsætter noget i en trie?
>> Lad os indsætte nøglen zoo i vores trie.
Husk, at et smilende ansigt på en node kunne svare i kode til en simpel
Boolesk værdi for at indikere, zoo findes i ordbogen, eller det kunne
svarer til flere oplysninger, som vi ønsker at forbinde med nøglen zoo,
som definitionen af ord eller noget andet.
På nogle måder, at processen indsætte noget i en trie ligner
kigge op noget i en trie.
>> Vi begynder med rodnoden igen, følgende pejlemærker, der svarer til
bogstaverne i vores nøgle.
Heldigvis var vi i stand til at følge pointers hele vejen, indtil vi nåede
udgangen af ​​nøglen.
Da zoo er et præfiks af ordet zoom, der er medlem af
ordbog, behøver vi ikke at tildele nye noder.
>> Vi kan ændre den node indikere, at stien karakterer, der fører til
det repræsenterer en nøgle i vores ordbog.
Nu, lad os prøve at indsætte nøgle BATH i trie.
Vi starter ved roden node og følg pointers igen.
Men i denne situation, vi ramte en død slutter, før vi er i stand til at komme til
spidsen af ​​nøglen.
Nu vil vi nødt til at afsætte nogle nye knudepunkter bliver nødt til at afsætte en ny
node for hvert resterende brev af vores nøgle.
>> I dette tilfælde har vi bare brug at tildele en ny node.
Så vil vi nødt til at gøre H-indeks henvise til denne nye node.
Igen kan vi ændre den node indikerer, at stien karakterer
fører til det repræsenterer en nøglen i vores ordbog.
Lad os ræsonnere om den asymptotiske kompleksiteten af ​​vores procedurer for disse
to operationer.
>> Vi bemærker, at der i begge tilfælde kan antallet af trin vores algoritme tog blev
proportional med antallet af bogstaver i søgeordet.
Det er rigtigt.
Når du ønsker at se et ord op i en trie du bare nødt til at gentage gennem
bogstaverne én efter én, indtil du enten nå slutningen af ​​ordet eller
ramte en blindgyde i trie.
>> Og når du ønsker at indsætte en nøgle værdi par i en trie ved hjælp af
procedure, vi diskuterede, i værste fald vil få dig til at afsætte en ny knude
for hvert bogstav.
Og vi vil antage, at fordelingen er en konstant tid operation.
Så hvis vi antager, at nøglelængde er afgrænset af en fast konstant, både
indsættelse og kigge op er konstante time operationer for en trie.
>> Hvis vi ikke gør dette antagelse, at nøglelængden er afgrænset af en fast
konstant, så indsættelse og se op, i værste tilfælde er lineær i
længden af ​​nøglen.
Bemærk, at antallet af poster er gemt i trie påvirker ikke udseendet op
eller insertion tid.
Det er kun påvirket af længden af ​​nøglen.
>> Derimod tilføjer indgange til, sige, en hash tabel tendens til at gøre
fremtiden ser op langsommere.
Selvom det kan lyde tiltalende ved første, vi skal huske på, at en
gunstige asymptotiske kompleksitet ikke betyder, at i praksis data
struktur er nødvendigvis uanfægtelig.
Vi må også overveje, at for at gemme en ord i en trie vi har brug for, i værste
tilfælde et antal knudepunkter proportional til længden af ​​ordet selv.
>> Forsøg tendens til at bruge en masse plads.
Det er i modsætning til en hash-tabel, hvor vi kun har brug for en ny node til
gemme nogle nøgleværdi par.
Nu igen i teorien stort rum forbrug ikke virke som en stor
håndtere, især i betragtning, at moderne computere har gigabytes og
gigabyte hukommelse.
Men det viser sig, at vi stadig har at bekymre sig om brug af hukommelse og
organisation af hensyn til resultater, da moderne computere
har mekanismer under hætte til at fremskynde hukommelse adgang.
>> Men disse mekanismer fungerer bedst, når hukommelse adgange er lavet i kompakt
regioner eller områder.
Og knudepunkter i en trie kunne opholde overalt i denne bunke.
Men disse er afvejninger at vi skal overveje.
>> Husk det, når du vælger en data struktur for en bestemt opgave, vi
bør tænke over, hvilke former for operationer datastrukturen skal
støtte og hvor meget ydelse i hver af disse
operationer spørgsmål til os.
Disse operationer kan endda strække sig ud over bare
grundlæggende kig op og indsættelse.
Antag, at vi ønskede at gennemføre en slags af auto-komplet funktionalitet, meget
Ligesom Google-søgemaskinen gør.
Det vil sige, returnere alle nøglerne og potentielt værdier, som
have givet et præfiks.
>> Et trie er entydigt nyttigt til denne operation.
Det er ligetil at gentage gennem den trie for hver karakter
præfikset.
Ligesom et kig op operation, vi kunne følge pointers
tegn for tegn.
Derefter, når vi frem til slutningen af præfiks, kunne vi gentage gennem
resterende del af datastrukturen idet enhver af nøglerne ud
dette punkt har præfikset.
>> Det er også nemt at få denne liste i alfabetisk rækkefølge, da
elementer af børn matrix er ordnet alfabetisk.
Så forhåbentlig du vil overveje give forsøger en chance.
Jeg Kevin Schmid, og det er CS50.
>> Ah, det er begyndelsen af tilbagegangen.
Undskyld.
>> Strike fire.
Jeg er ude.
Undskyld.
Sorry for at gøre den person, der har til at redigere denne gå amok.
>> Undskyld.
Undskyld.
>> SPEAKER 1: Well done.
Det var virkelig godt gået.