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. Undskyld. Undskyld. Undskyld. 

Strike fire. Jeg er ude. Undskyld. Undskyld. Undskyld. Sorry for at gøre den person, der har til at redigere denne gå amok. 

Undskyld. Undskyld. Undskyld. Undskyld. 

SPEAKER 1: Well done. Det var virkelig godt gået.