KEVIN Schmid: Ibland, när man bygger en program, kanske du vill använda en datastruktur som kallas en ordbok. En ordbok kartor nycklar, som är oftast strängar, till värden, Ints, tecken, en pekare till något objekt, vad vi vill. Det är precis som vanliga ordböcker att kart ord genom definitioner. 

Ordböcker ger oss förmåga att lagra information förknippas med något och slå upp det senare. Så hur gör vi faktiskt genomför en dictionary i, säg, C-kod som vi kan användning i någon av våra program? Nåväl, det finns många sätt att vi skulle kunna genomföra en ordbok. 

För en, kan vi använda en array som vi dynamiskt ändra storlek eller vi skulle kunna använda en länkad lista, hashtabell eller ett binärt träd. Men vad vi än väljer, bör vi vara uppmärksam på effektivitet och utförandet av implementeringen. Vi borde tänka på den algoritm som används att sätta in och leta upp poster i vår datastruktur. 

För nu, låt oss anta att vi vill använda strängar som nycklar. Låt oss tala om en möjlighet, en datastruktur som kallas en trie. Så här är en visuell representation av en trie. 

Som bilden antyder, en trie är en träddatastruktur med noder kopplas samman. Vi ser att det finns helt klart en rot nod med några länkar som sträcker sig till andra noder. Men vad varje nod består av? Om vi ​​antar att vi lagrar nycklar med endast alfabetiska tecken, och Vi bryr oss inte om kapitalisering, Här är en definition av en nod som tillräcklig. 

Ett objekt vars typ är struct nod har två delar kallas data och barn. Vi har lämnat uppgifterna ingår som en kommentar för att ersättas av en komponent deklaration när struct nod är införlivas i ett C-program. Datadelen hos en nod kan vara en Booleskt värde som anger om inte den nod representerar slutför av en ordbok nyckel eller det kan vara en sträng som representerar definitionen av ett ord i ordlistan. 

Vi kommer att använda en smiley för att ange när data är närvarande i en nod. Det finns 26 element i vår barn array, ett index per bokstav. Vi får se vilken betydelse av detta kort. 

Låt oss få en närmare titt på rotnoden i vårt diagram, som saknar uppgifter samband med det, vilket framgår av den avsaknad av smiley i datadel. De pilar som sträcker sig från de delar som barnen array representerar icke-nod pekare till andra noder. Exempelvis pilen som sträcker sig från den andra delen av barn representerar bokstaven B i en ordbok nyckel. Och i den större schema vi märka den med ett B. 

Notera att i den större diagrammet, när vi dra en pekare till en annan nod, det spelar ingen roll var pilspetsen uppfyller denna andra nod. Vår provet ordboks trie innehåller två ord, det och zooma. Låt oss gå igenom ett exempel på leta upp uppgifter för en nyckel. 

Antag att vi ville slå upp Motsvarande värde för nyckeln badet. Vi börjar vår blick upp vid rotnoden. Sen tar vi den första bokstaven i vår nyckel, B, och hittar motsvarande plats i våra barn array. Lägg märke till att det är exakt 26 platser i arrayen, en för varje bokstav i alfabetet. Och vi kommer att ha fläckarna representerar bokstäverna i alfabetet i ordning. 

Vi tittar på det andra indexet sedan, index en, för B. I allmänhet, om vi har någon bokstav C vi skulle kunna fastställa den motsvarande plats i barn array med en beräkning som denna. Vi kunde ha använt ett större barn matris om vi ville erbjuda titta upp på nycklar med ett bredare utbud av karaktärer, såsom hela ASCII-teckenuppsättning. 

I detta fall pekaren i våra barn array på index man inte är null. Så vi ska fortsätta titta upp nyckeln badet. Om vi ​​någonsin stött på en nollpekare på rätt plats i barnen matris medan vi korsas noderna, då vi måste säga att vi kunde inte hitta något för den tangenten. 

Nu tar vi den andra bokstaven i vår nyckel, A, och fortsätter efter pekare på detta sätt tills vi når slutet av vår nyckel. Om vi ​​kommer till slutet av nyckeln utan träffa några återvändsgränder, null pekare, vilket är fallet här, då bara vi måste kolla en sak. Är det nyckeln faktiskt i ordlistan? 

Om så är fallet, skulle vi finna ett värde, väl en smiley-ikonen i vårt diagram där ordet slutar. Om det är något annat som lagras med data, då kan vi lämna tillbaka den. Till exempel, är nyckeln zoo inte i ordbok, även om vi kunde ha nått slutet av denna nyckel utan att någonsin slå en null-pekare, medan vi iterera igenom trie. 

Om vi ​​försökte leta upp nyckeln bad, näst sista nods fältindex, motsvarar bokstaven H, skulle har haft en null-pekare. Så bad är inte i ordlistan. Och så en trie är unik i det att knapparna är aldrig explicit lagrad i datastrukturen. Så hur ska vi sätta in något in i en trie? 

Låt oss sätta i nyckeln zoo i vår trie. Kom ihåg att en smiley på en nod skulle motsvara i koden till ett enkelt Booleskt värde som tyder på att zoo är i ordboken eller det kan motsvara mer information som vi vill associera med nyckel zoo, liksom definitionen av ord eller något annat. På sätt och vis, att processen för in något i ett trie liknar tittar upp något i ett trie. 

Vi börjar med rotnoden igen, Följande tips motsvarande bokstäverna i vår nyckel. Lyckligtvis kunde vi följa pekare ända tills vi nådde slutet av nyckeln. Eftersom djurparken är ett prefix till ordet zoom, vilket är en medlem av den ordbok, behöver vi inte fördela några nya noder. 

Vi kan modifiera noden för att indikera att banan av tecken som leder till det utgör en nyckel i vår ordlista. Nu ska vi försöka sätta in nyckel BAD i trie. Vi börjar på rotnoden och följ pekare igen. Men i den här situationen, slog vi en död slutar innan vi kan komma till änden av nyckeln. Nu kommer vi att behöva avsätta en del nya kontaktpunkter måste tilldela en ny nod för varje återstående skrivelse av vår nyckel. 

I det här fallet behöver vi bara att tilldela en ny nod. Då kommer vi att behöva göra H-index referera till den nya noden. Återigen kan vi modifiera den nod till indikera att banan av tecken som leder till den representerar en nyckel i vår ordlista. Låt oss resonera om asymptotiska komplexiteten i våra rutiner för dessa två operationer. 

Vi märker att i båda fallen att antalet för steg vår algoritm tog var proportionell mot antalet av bokstäver i sökordet. Det stämmer. När du vill slå upp ett ord i en trie du behöver bara iterera genom bokstäverna en efter en tills du antingen når slutet av ordet eller träffa en återvändsgränd i trie. 

Och när du vill lägga in en nyckel värde-par till ett trie med hjälp av procedur som vi diskuterade, det värsta fallet kommer att få dig att tilldela en ny nod för varje bokstav. Och vi antar att fördelningen är en konstant tids operation. Så om vi antar att nyckellängden är avgränsas av en fast konstant, både insättning och leta upp är konstanta tidsverksamhet för en trie. 

Om vi ​​inte göra detta antagande att nyckellängden är begränsad av ett fast konstant, sedan införandet och titta upp, i värsta fall, är linjär i längden på nyckeln. Observera att antalet objekt som lagras i trie inte påverkar utseendet upp eller inser tid. Det har bara påverkats av den längden på nyckeln. 

Däremot att lägga till poster i, säg, en hashtabell tenderar att göra framtiden ser upp långsammare. Även om detta kanske låter lockande i början, Vi bör hålla i minnet att en gynnsamma asymptotisk komplexitet inte innebär att i praktiken uppgifter strukturen är nödvändigtvis klanderfri. Vi måste också tänka på att lagra en ord i ett trie vi behöver, i värsta fall ett antal noder i proportion till längden av själva ordet. 

Försöker tenderar att använda en hel del utrymme. Det är i motsats till en hash-tabell, där vi behöver bara en ny nod till lagra vissa nyckelvärde paret. Nu, återigen i teorin, stort utrymme konsumtion verkar inte som en stor hantera, speciellt med tanke på att modern datorer har gigabyte och gigabyte minne. Men det visar sig att vi fortfarande har att oroa sig för minnesanvändning och organisation för den skull prestanda, eftersom moderna datorer ha mekanismer enligt huva för att snabba upp minnesåtkomst. 

Men dessa mekanismer fungerar bäst när minnesaccesserna är gjorda i kompakt regioner eller områden. Och noderna i ett trie kunde uppe någonstans i högen. Men dessa är avvägningar att vi måste överväga. 

Kom ihåg att när du väljer en data struktur för en viss uppgift, vi bör tänka på vad slags operationer datastrukturen behöver stöd och hur mycket prestandan av var och en av dem verksamhet är viktigt för oss. Dessa verksamheter kan till och med sträcker sig längre än bara grundläggande utseende upp och insättning. Antag att vi ville genomföra en slags av automatisk komplettering funktionalitet, mycket som Googles sökmotor fungerar. Det vill säga, tillbaka alla nycklar och potentiellt värden som har ett givet prefix. 

En trie är unikt användbar för denna operation. Det är enkelt att iterera igenom den trie för varje karaktär prefixet. Precis som en slå upp operation Vi kunde följa pekare tecken för tecken. Sedan, när vi kommer till slutet av prefix, kunde vi iterera genom återstående del av datastrukturen sedan någon av knapparna bortom denna punkt har prefixet. 

Det är också lätt att få den här informationen i alfabetisk ordning sedan delar av barn arrayen är ordnade alfabetiskt. Så förhoppningsvis kommer du att tänka på givandet försöker ett försök. Jag är Kevin Schmid, och detta är CS50. 

Ah, det här är början av nedgången. Jag är ledsen. Ursäkta. Ursäkta. Ursäkta. 

Strike fyra. Jag är ute. Ursäkta. Ursäkta. Ursäkta. Ledsen för att den som måste redigera bli galen. 

Ursäkta. Ursäkta. Ursäkta. Ursäkta. 

SPEAKER 1: Bra gjort. Det var riktigt bra gjort.