KEVIN SCHMID: Dažreiz, kad ēka programmu, jūs varētu vēlēties, lai izmantotu datu struktūra pazīstams kā vārdnīcu. Vārdnīca kartes taustiņi, kas ir parasti stīgas, vērtībām, Ints, simboli, rādītāju uz kādu objektu, ko mēs gribam. Tas ir tāpat kā parastās vārdnīcās ka karšu vārdi caur definīcijām. 

Vārdnīcas sniedz mums spēja saglabāt informāciju saistīta ar kaut ko un meklēt to vēlāk. Tātad, kā mēs faktiski īstenot vārdnīca, teiksim, C kodu, ka mēs varam izmantošanai vienā no mūsu programmu? Nu, tur ir vairāki veidi, ka mēs varētu īstenot vārdnīcu. 

Attiecībā uz vienu, mēs varētu izmantot masīvu, ka mēs dinamiski mainīt lielumu vai mēs varētu izmantot saistīts saraksts, hash tabulu vai bināro koku. Bet neatkarīgi mēs izvēlamies, mums vajadzētu jāsargājas no efektivitātes un izpildi īstenošanas. Mums vajadzētu domāt par algoritma ievietot un meklēt priekšmetus Mūsu datu struktūra. 

Tagad, pieņemsim, ka mēs vēlaties izmantot stīgas, atslēgas. Parunāsim par vienu iespēju, datu struktūra, ko sauc par Trie. Tātad, šeit ir vizuāls attēlojums no Trie. 

Kā liekas, Trie ir koks datu struktūra ar mezglu saistīti kopā. Mēs redzam, ka tur ir skaidri saknes mezgls ar dažas saites attiecina uz citiem mezgliem. Bet ko katrs mezgls sastāv? Ja mēs pieņemam, ka mēs esam atslēgu glabāšanas ar tikai alfabēta burtiem, un mums nerūp kapitalizācijas, šeit ir definīciju mezglu, kas pietiks. 

Objekts, kura tips ir struct mezgls ir divas daļas aicināja datus un bērnus. Mēs esam atstājuši datu daļa, kas komentāru aizstāt ar sastāvdaļu deklarācijā, ja struktūrai mezgls ir iekļauts C programmu. Datu daļa mezglā var būt Būla vērtība, kas norāda, vai nav mezglu pārstāv pabeigšanu vārdnīcas atslēgu vai tas varētu būt string pārstāv definīciju ar vārdu vārdnīcā. 

Mēs izmantot smaidiņam norādītu kad dati ir klāt mezglā. Ir 26 elementi mūsu bērni masīvs, viens indekss katru alfabēta burtu. Redzēsim nozīmi tas drīz. 

Būsim tuvāk apskatīt saknes mezgla mūsu diagramma, kas nav datu saistīta ar to, kā norāda neesamība smaidošās sejas datu daļu. Bultas, kas stiepjas no daļām bērni masīvu veido ne-mezglu norādes uz citiem mezgliem. Piemēram, arrow stiepjas no otrais elements bērniem apzīmē burtu B vārdnīcā atslēgu. Un lielākā diagrammā mēs marķēt ar B. 

Jāņem vērā, ka lielākās diagramma, kad mēs izdarīt rādītāju uz citu mezglu, tas nav svarīgi, kur bultas gals atbilst šo citu mezglu. Mūsu izlases vārdnīca trie satur divi vārdi, kas un zoom. Apskatīsim piemēru looking up datus par atslēgu. 

Pieņemsim, ka mēs vēlējāmies, lai meklētu atbilstošo vērtību galveno vannā. Mēs sāksim savu izskatu augšu saknes mezglā. Tad mēs ņemšu pirmo burtu mūsu atslēgu, B, un atrast atbilstošo vietas mūsu bērniem masīvā. Ievērojiet, ka ir tieši 26 punkti masīvā, pa vienai katrā no vēstules alfabēts. Un mums būs plankumi pārstāv burtus alfabēta kārtībā. 

Mēs apskatīt otrajā indeksu, tad, indekss vienu, lai B. Kopumā, ja mēs ir dažas alfabēta burtu C mēs varētu noteikt atbilstošo vietu ar bērnu masīvā, izmantojot aprēķinu, kā šis. Mēs būtu varējuši izmantot lielāku bērnu masīvs, ja mēs vēlējāmies piedāvāt Look veido taustiņi ar plašāku rakstzīmes, , piemēram, visu ASCII rakstzīmju kopu. 

Šajā gadījumā rādītājs mūsu bērniem masīvā pie indekss viens nav null. Tāpēc mēs joprojām meklējam up galveno vannā. Ja mēs kādreiz radušās null rādītāju pie pareizas vietas bērniem masīvs kamēr mēs šķērso mezglus, Tad mums būs teikt, ka mēs nevarēju atrast neko par šo taustiņu. 

Tagad mēs ņemšu otro vēstuli Mūsu galvenais, un arī turpmāk pēc norādes šādā veidā, kamēr mēs beigs mūsu atslēgu. Ja beigs atslēgu bez hitting strupceļus, null norādes, kā tas ir šajā gadījumā, tad mēs tikai ir jāpārbauda vēl viena lieta. Tas ir galvenais, kas faktiski vārdnīcā? 

Ja tā, tad mums vajadzētu atrast vērtību, labi smiley sejas ikona mūsu diagrammā, kur vārds beidzas. Ja ir kaut kas cits uzglabā ar datus, tad mēs varam to atpakaļ. Tā, piemēram, galvenais zoo nav vārdnīca, lai gan mēs varētu būt sasnieguši šīs atslēgu, nekad hitting null rādītāju, kamēr mēs atkārtot, izmantojot Trie. 

Ja mēs mēģinājām meklēt atslēgas vanna, Otrais pagājušā mezglu masīva indeksu, atbilst burtu H, būtu ir notika null rādītāju. Tātad, vanna nav vārdnīcā. Un tā trie ir unikāla ar to, ka atslēgas nekad nav skaidri glabāti datu struktūra. Tātad, kā mēs ievietot kaut ko uz Trie? 

Pieņemsim ievietojiet atslēgu zoo mūsu Trie. Atcerieties, ka smiley sejas pie mezglā varētu atbilst kodā uz vienkāršu Būla vērtība, kas norāda, ka zoo ir vārdnīcā vai tas varētu atbilst vairāk informācijas, ka mēs vēlas saistīt ar galveno zoo, piemēram, definīciju vārds vai kaut kas cits. Dažos veidos, process, lai ievietotu kaut uz Trie ir līdzīgs looking up kaut kādā Trie. 

Mēs sāksim ar to saknes mezgla atkal, Šādas norādes atbilst vēstules no mūsu galvenajiem. Par laimi, mēs varējām sekot norādes visu ceļu, līdz nonācām gals atslēgu. Tā zoo ir priedēklis vārda zoom, kas ir dalībniece vārdnīca, mums nav nepieciešams piešķirt jaunus mezgliem. 

Mēs varam mainīt mezglu, lai norādītu, ka ceļš rakstzīmju rezultātā tas ir galvenais mūsu vārdnīcā. Tagad pamēģināsim ievietojot Galvenais PIRTS uz Trie. Mēs sāksim saknes mezgla un izpildiet norādes vēlreiz. Bet šajā situācijā, mēs hit miris beigties pirms mēs esam spējīgi nokļūt gals atslēgu. Tagad mums būs nepieciešams piešķirt kādu jaunu mezgli būs nepieciešams piešķirt vienu jaunu mezglu par katru atlikušo vēstule no mūsu atslēgas. 

Šajā gadījumā, mums ir nepieciešams piešķirt vienu jaunu mezglu. Tad mums būs nepieciešams, lai H indeksu atsauce šo jauno mezglu. Atkal, mēs varam mainīt mezglu norāda, ka ceļš rakstzīmju noved pie tā ir Galvenais mūsu vārdnīcā. Pieņemsim spriest par asimptotiskais sarežģītība mūsu procedūru šos divas operācijas. 

Mēs paziņojuma, kas abos gadījumos numurs Pakāpienu mūsu algoritms bija bija proporcionāls skaita burti atslēgvārdu. Tas ir labi. Ja vēlaties, lai uzmeklēt vārdu trie jums ir nepieciešams atkārtot, izmantojot burti pa vienam, līdz jūs vai nu beigs vārdu vai hit strupceļā ar Trie. 

Un, ja jūs vēlaties, lai ievietotu atslēgu vērtība pāri par Trie, izmantojot procedūru mēs apspriedām, sliktākajā gadījumā būs jums piešķirot jaunu mezglu katram burtam. Un mēs pieņemam, ka sadalei ir nemainīgs laika darbību. Tātad, ja mēs pieņemam, ka atslēgas garums ir ko ierobežo noteiktu konstanti, gan ievietošanas un meklēt ir konstants laika operācijas ir Trie. 

Ja mums nav šo pieņēmumu, ka atslēgas garumu ierobežo fiksētu nemainīgs, tad ievietošanas un meklēt, sliktākajā gadījumā, ir lineāra atslēgas garums. Ievērojiet, ka vienību skaits ir saglabāti kas Trie neietekmē izskatu up vai ievietošanas laika. Tas ir tikai ietekmē atslēgas garums. 

Turpretī, pievienojot ierakstus, teiksim, hash tabulu mēdz darīt Nākotne izskatās lēnāk. Lai gan tas var likties pievilcīgs sākumā, mums ir jāpatur prātā, ka labvēlīgs asimptotiskās sarežģītība nav nozīmē, ka praksē datu struktūra ir obligāti nevainojama. Mums jāņem vērā, ka, lai saglabātu vārds ir Trie mums ir nepieciešams, jo sliktākajā gadījumā, vairāki mezglu proporcionāls ar garumu vārda together. 

Mēģina mēdz izmantot daudz vietas. Tas ir pretstatā hash tabulu, kur mums ir nepieciešama tikai viena jauna mezgla uz uzglabāt dažas galvenās vērtības pāri. Tagad atkal teorētiski, liela telpa patēriņš nav šķist liels risinātu, it īpaši ņemot vērā, ka mūsdienu datori ir gigabaitiem, un gigabaitu atmiņu. Bet izrādās, ka mums vēl ir jāuztraucas par atmiņas izmantošanu un organizācijas dēļ sniegumu, jo mūsdienu datoriem ir mehānismi, ar kapuce paātrināt atmiņas piekļuvi. 

Taču šie mehānismi darbojas vislabāk, kad atmiņas Pieejas tiek veikti kompakts reģioniem vai teritorijām. Un mezglus, kuru Trie varētu uzturēties jebkur šajā kaudzē. Bet tie ir kompromisi ka mums ir jāapsver. 

Atcerieties, ka, izvēloties datu struktūra, lai noteiktu uzdevumu, mēs vajadzētu domāt par to, kāda veida darbības datu struktūra ir atbalstu un cik daudz sniegumu katra no tām Operācijas ar jautājumiem pie mums. Šīs operācijas var pat pārsniedz tikai pamata uzmeklēt un ievietošanas. Pieņemsim, ka mēs vēlējāmies īstenot veida auto-pilnīgs funkcionalitāti, daudz piemēram, Google meklēšanas dzinējs nav. Tas ir, atpakaļ visas atslēgas un potenciāli vērtības, kas ir dota prefiksu. 

Trie ir unikāli noderīgs Lai veiktu šo darbību. Tas ir vienkārši atkārtot, izmantojot trie katra raksturu prefiksu. Tāpat kā uzmeklēt darbību, mēs varētu sekot norādes raksturu pēc rakstura. Pēc tam, kad mēs nonāktu beigās priedēklis, mēs varētu atkārtot, izmantojot atlikušo daļu datu struktūru jo jebkuru no taustiņiem aiz Šis punkts ir prefiksu. 

Tas ir arī viegli iegūt šo ierakstu alfabētiskā secībā, jo elementi bērnu masīva ir pasūtīts pēc alfabēta. Tāpēc cerams, jūs uzskatāt pasniegšanas mēģina mēģināt. Es esmu Kevin Schmid, un tas ir CS50. 

Ah, tas ir sākums krituma. Piedod. Piedodiet. Piedodiet. Piedodiet. 

Strike četri. Es esmu ārā. Piedodiet. Piedodiet. Piedodiet. Atvainojos par to personu, kas ir, lai rediģētu to go crazy. 

Piedodiet. Piedodiet. Piedodiet. Piedodiet. 

SPEAKER 1: Labi darīts. Tas bija ļoti labi darīts.