>> KEVIN SCHMID: Soms, wanneer die bou van 'n program, kan jy wil gebruik om 'n
data struktuur bekend as 'n woordeboek.
'N Woordeboek kaarte sleutels, wat gewoonlik snare, met waardes, ints,
karakters, 'n verwysing na 'n voorwerp, wat ons wil.
Dit is net soos gewone woordeboeke die kaart woorde deur definisies.
>> Woordeboeke voorsien ons met die vermoë om inligting te stoor
verband hou met iets en kyk dit later.
So hoe ons eintlik implementeer nie 'n woordeboek in, sê, C-kode wat ons kan
gebruik in een van ons programme?
Wel, daar is 'n baie maniere wat Ons kan 'n woordeboek te implementeer.
>> Vir een, kan ons 'n skikking te gebruik dat ons dinamiese re-grootte of ons kan gebruik om 'n
gekoppel lys hutstabel of 'n binêre boom.
Maar wat ons ook al kies, moet ons wees bewus van die doeltreffendheid en
prestasie van die implementering.
Ons moet dink oor die algoritme gebruik in te voeg en kyk op items in
ons data struktuur.
>> Vir nou, laat ons aanvaar dat ons wil snare te gebruik as sleutels.
Kom ons praat oor 'n moontlikheid, 'n data struktuur genaamd 'n Trie.
So hier is 'n visuele voorstelling van 'n Trie.
>> As die prentjie stel, 'n tydstip waarop is 'n boom data struktuur met
nodes met mekaar verbind.
Ons sien dat daar is duidelik 'n wortel knoop met 'n paar skakels uit te brei na
ander nodes.
Maar wat beteken elke knoop bestaan ​​uit?
As ons aanvaar dat ons stoor sleutels met net letters en
Ons gee nie om oor kapitalisasie, hier is 'n definisie van 'n knoop wat
sal voldoende wees.
>> 'N voorwerp waarvan die tipe is struct node bestaan ​​uit twee dele
data en kinders genoem.
Ons het die data deel gelaat as 'n opmerking vervang word deur 'n komponent
verklaring wanneer struct knoop is opgeneem in 'n C program.
Die data deel van 'n knoop kan wees om 'n Boolese waarde aan te dui of
nie die knoop verteenwoordig die voltooiing van 'n woordeboek sleutel of dit kan wees om 'n
string die definisie wat van 'n woord in die woordeboek.
>> Ons sal 'n smiley face gebruik om aan te dui wanneer data teenwoordig is in 'n knoop.
Daar is 26 elemente in ons kinders skikking, een-indeks
per alfabetletter begin.
Ons sal die betekenis sien van hierdie gou.
>> Kom ons kry 'n nader kyk van die wortel node in ons diagram, wat geen data
verband hou met dit, soos aangedui deur die afwesigheid van die smiley gesig in die
data gedeelte.
Die pyle wat strek van die dele van die kinders skikking verteenwoordig nie-knoop
verwysings na ander nodes.
Byvoorbeeld, die pyl wat strek vanaf die tweede element van kinders
verteenwoordig die letter B in 'n woordeboek sleutel.
En in die groter diagram ons benoem dit met 'n B.
>> Let daarop dat in die groter diagram, wanneer ons trek 'n verwysing na 'n ander knoop, dit
maak nie saak waar die pylpunt voldoen aan die ander knoop.
Ons voorbeeld woordeboek Trie bevat twee woorde, wat en zoom.
Kom ons loop deur 'n voorbeeld van kyk op data vir 'n sleutel.
>> Gestel ons wil om te kyk die ooreenstemmende waarde vir die sleutel bad.
Ons sal begin om ons kyk op aan die wortel node.
Dan sal ons die eerste letter van ons neem sleutel, B, en vind die ooreenstemmende
plek in ons kinders skikking.
Let daarop dat daar presies 26 plekke in die skikking, een vir elke letter van
die alfabet.
En ons sal die kolle verteenwoordig die letters van die alfabet in orde is.
>> Ons sal kyk na die tweede indeks dan indeks een, vir B. In die algemeen, as ons
het 'n paar alfabetletter C ons kon die ooreenstemmende plek bepaal
in die kinders skikking gebruik 'n berekening soos hierdie.
Ons kan 'n groter kinders gebruik het verskeidenheid as ons wou kyk uit aan te bied
sleutels met 'n groter verskeidenheid van die karakters, soos die hele
ASCII karakter stel.
>> In hierdie geval, die wyser in ons kinders opgestel by
indeks een is nie null.
So ons sal voortgaan om te kyk die sleutel bad.
As ons ooit 'n nul pointer teëgekom op die regte plek in die kinders
skikking terwyl ons deurkruis die nodes, dan sal ons moet sê dat ons
kon nie iets kry vir die sleutel.
>> Nou, sal ons die tweede brief van neem ons sleutel, A, en gaan voort om volgende
wysers op hierdie manier, totdat ons bereik die einde van ons sleutel.
As ons die einde van die sleutel bereik sonder slaan enige dood eindig, null wysers,
soos in die geval hier nie, dan net ons het een ding om te kyk.
Is dit die sleutel eintlik in die woordeboek?
>> As dit so is, moet ons 'n waarde vind, goed 'n smiley face ikoon in ons diagram waar
die woord eindig.
As daar is iets anders gestoor met die data, dan kan ons dit terug.
Byvoorbeeld, die sleutel dieretuin is nie in die woordeboek, selfs al het ons kan hê
aan die einde van hierdie sleutel sonder om ooit slaan 'n nul pointer, terwyl ons
Itereer deur die Trie.
>> As ons probeer om op te kyk die sleutel bad, die tweede laaste knoop se skikking indeks,
ooreenstem met die letter H, sou het gehou 'n nul wyser.
So bad is nie in die woordeboek.
En so 'n tydstip waarop is uniek in die sin dat die sleutels nooit uitdruklik in gestoor
die data struktuur.
So hoe iets voeg ons in 'n Trie?
>> Kom ons plaas die sleutel dieretuin in ons Trie.
Onthou dat 'n smiley face op 'n knoop kon ooreenstem in die kode op 'n eenvoudige
Boolean waarde wat dieretuin aan te dui is in die woordeboek of dit kan
ooreenstem met meer inligting wat ons wil assosieer met die sleutel dieretuin,
soos die definisie van die woord of iets anders.
In sommige maniere, om die proses te voeg iets in 'n Trie is soortgelyk aan
soek iets in 'n Trie.
>> Ons begin met die wortel node weer volgende wenke wat ooreenstem met
die letters van ons sleutel.
Gelukkig het ons in staat was om riglyne te volg al die pad totdat ons bereik
die einde van die sleutel.
Sedert dieretuin is 'n voorvoegsel van die woord Klik op die, wat 'n lid van die
woordeboek, het ons nie nodig het om te ken enige nuwe nodes.
>> Ons kan die knoop verander om aan te dui dat die pad van die karakters wat lei tot
dit verteenwoordig 'n belangrike in ons woordeboek.
Nou, laat ons probeer om die plaas van die sleutel BATH in die Trie.
Ons begin by die wortel node en volg aanwysings weer.
Maar in hierdie situasie, ons 'n dooie getref eindig voordat ons in staat is om te kry om die
einde van die sleutel.
Nou, moet ons 'n paar nuwe te ken nodes sal moet een nuwe te ken
knoop vir elke oorblywende letter van die sleutel.
>> In hierdie geval, ons moet net een nuwe knoop toe te ken.
Dan sal ons die H-indeks te maak verwys hierdie nuwe knoop.
Weereens, kan ons die knoop verander na dui daarop dat die pad van die karakters
wat lei tot dit 'n sleutel in ons woordeboek.
Kom ons redeneer oor die asimptotiese kompleksiteit van ons prosedures vir hierdie
twee operasies.
>> Ons sien dat in beide gevalle die aantal stappe ons algoritme geneem het, was
eweredig aan die aantal letters in die navraag.
Dit is reg.
As jy wil om te kyk op 'n woord in 'n Trie jy hoef net te Itereer deur
die letters een vir een totdat jy óf bereik die einde van die woord of
getref 'n doodloopstraat in die Trie.
>> En as jy 'n sleutel in te voeg waarde paar in 'n tydstip waarop die gebruik van die
proses wat ons bespreek het, die ergste geval sal jy die toekenning van 'n nuwe node
vir elke brief.
En ons sal daardie toewysing aanvaar is 'n konstante werking.
So as ons aanvaar dat die sleutel lengte begrens deur 'n vaste konstante, beide
inplanting en kyk konstant tyd bedrywighede vir 'n Trie.
>> As ons maak nie hierdie aanname dat die sleutel lengte begrens deur 'n vaste
konstante, dan inplanting en kyk, In die ergste geval, is lineêr in die
lengte van die sleutel.
Let daarop dat die aantal items gestoor in die Trie raak nie die blik op
of voeg die tyd.
Dit is net beïnvloed deur die lengte van die sleutel.
>> In teenstelling hiermee, voeg inskrywings aan, sê, 'n hutstabel geneig is om te maak
toekoms kyk stadiger.
Hoewel dit mag klink aantreklik op die eerste, Ons moet in gedagte hou dat 'n
gunstige asimptotiese kompleksiteit nie beteken dat in die praktyk die data
struktuur is noodwendig bo verdenking.
Ons moet ook in ag neem dat die stoor 'n woord in 'n tydstip waarop ons nodig het, in die ergste
geval, 'n aantal nodes proporsionele die lengte van die woord self.
>> Drieë is geneig om 'n baie ruimte om te gebruik.
Dit is in teenstelling met 'n hash tafel, waar ons moet net een nuwe node te
slaan 'n paar belangrike waarde paar.
Nou, weer in teorie, 'n groot ruimte verbruik lyk nie soos 'n groot
hanteer, veral gegewe dat die moderne rekenaars GB en
GB van die geheue.
Maar dit blyk dat ons nog bekommerd te wees oor die geheue gebruik en
organisasie ter wille van die prestasie, aangesien die moderne rekenaars
meganismes in plek onder die kap te bespoedig geheue toegang.
>> Maar hierdie meganismes werk die beste wanneer geheue besoeke is gemaak in kompakte
streke of gebiede.
En die knope van 'n Trie kon woon enige plek in die hoop.
Maar dit is trade-offs dat ons moet in ag neem.
>> Onthou dat, wanneer jy 'n data struktuur vir 'n spesifieke taak, ons
moet dink oor watter soort bedrywighede die data struktuur moet
ondersteuning en hoeveel van die prestasie van elk van dié
bedrywighede sake vir ons.
Hierdie bedrywighede kan selfs brei verder as net
basiese voorkoms en inplanting.
Gestel ons wil 'n soort te implementeer van die motor-volledige funksie, baie
soos Google soektog doen.
Dit is, terug al die sleutels en potensieel waardes wat
'n gegewe voorvoegsel.
>> 'N Trie is uniek nuttig vir hierdie operasie.
Dit is maklik om te Itereer deur die tydstip waarop vir elke karakter
die voorvoegsel.
Net soos 'n kyk op die operasie, ons wenke kan volg
karakter deur karakter.
Dan, wanneer ons by die einde van die voorvoegsel, kan ons Itereer deur die
oorblywende gedeelte van die data struktuur aangesien enige van die sleutels buite
hierdie punt het die prefix.
>> Dit is ook maklik om hierdie lys te kry in alfabetiese volgorde, aangesien die
elemente van die kinders skikking word alfabeties gerangskik nie.
So hopelik sal jy dit oorweeg gee probeer om 'n drie te druk.
Ek is Kevin Schmid, en dit is CS50.
>> Ag, dit is die begin van die afname.
Ek is jammer.
Jammer.
>> Staak vier.
Ek is uit.
Jammer.
Jammer vir die maak van die persoon wat te wysig hierdie gaan mal.
>> Jammer.
Jammer.
>> Spreker 1: Wel gedaan.
Dit is baie goed gedoen.