>> [Ag seinm ceoil]
DOUG LLOYD: Mar sin, tá muid ag inching níos gaire agus níos dlúithe go iomaíocht don duais mhór de shonraí
struchtúir, ceann gur féidir linn a chur isteach isteach, scriosadh as, agus breathnú suas
in am tairiseach.
Ceart.
Sin saghas an sprioc.
Is mian linn a bheith in ann a dhéanamh rudaí an-, go han-tapa.
>> An bhfuil fuair muid anseo nuair muid ag caint faoi iarracht?
Bhuel, a ligean ar ghlacadh le breathnú.
Mar sin, againn le feiceáil roinnt struchtúir éagsúla sonraí
a láimhseáil an mhapáil mar a thugtar air péirí eochair-luach,
mapáil roinnt píosa sonraí go píosa éigin eile de shonraí
mar sin tá a fhios againn nuair a aimsiú faisnéis i struchtúr.
>> Mar sin, le haghaidh eagar, mar shampla, an Is eochair an t-innéacs eilimint nó sraith
suíomh 0 nó sraith 1 agus mar sin de.
Agus is é an luach na sonraí atá ann ag an suíomh sin.
Mar sin, cad é a stóráil i sraith 0?
Cad atá stóráilte i sraith 1 versus díreach 0 agus 1, a bheadh ​​na heochracha.
>> Le tábla hash tá sé saghas an smaoineamh céanna.
Le tábla hash, ní mór dúinn an hash fheidhm a ghineann cóid hash.
Mar sin, is é an eochair an cód hash na sonraí.
Agus an luach, go háirithe Labhair linn faoi shlabhrú
san fhíseán ar tháblaí hash, Is liosta sin nasctha sonraí
go hashes leis hashcode.
Ceart.
Cad mar gheall ar an gcur chuige eile an modh seo, cé?
Cad mar gheall ar mhodh i gcás an eochair ráthaithe a bheith ar leith,
murab ionann agus tábla hash, i gcás ina d'fhéadfadh muid deireadh suas le dhá phíosa sonraí
a bhfuil an hashcode céanna.
Agus ansin ní mór dúinn chun déileáil leis go bhfuil ag ceachtar deacra nó níos mó
b'fhearr shlabhrú a shocrú go fhadhb.
>> Mar sin, anois is féidir linn a chinntiú go mbeidh ár eochair a bheith ar leith.
Agus cad má bhí ár n-luach ach rud éigin chomh héasca
chomh fíor nó bréagach a insíonn dúinn cé acu nó nach bhfuil píosa eolais
ann i struchtúr?
D'fhéadfadh Boole a bheith chomh simplí agus is le beagán.
Go réalaíoch is dócha Beart níos dóchúla ná le beagán.
Ach tá go bhfuil a lán níos lú ná mar a stóráil b'fhéidir teaghrán 50-charachtar,
mar shampla.
>> Mar sin, iarracht, cosúil le táblaí hash, a chur le chéile arrays agus liosta nasctha,
iarracht a chur le chéile arrays, Struchtúir, agus leideanna
le chéile chun sonraí a stóráil i ar bhealach suimiúil go bhfuil
deas difriúil ó rud ar bith againn le feiceáil go dtí seo.
Anois táimid ag úsáid as na sonraí mar treochlár le nascleanúint a struchtúr seo sonraí.
Agus más féidir linn leanúint an treochlár, más féidir linn a
lean na sonraí ó ag tosú ar deireadh, beidh muid a
Tá a fhios an bhfuil na sonraí sin ann sa Trie.
>> Agus más rud é nach féidir linn leanúint ar an léarscáil ó a chiallaíonn go deireadh ar chor ar bith,
nach féidir na sonraí ann.
Arís, is iad na heochracha anseo ráthaithe a bheith ar leith.
Agus mar sin murab ionann agus tábla hash, ní beidh orainn ag déileáil le imbhuailtí anseo.
Agus gan aon dhá phíosa sonraí tá díreach mar an gcéanna treochlár
ach amháin má tá na sonraí sin comhionann.
>> Má táimid Seán cuir isteach, ansin táimid ag cuardach do John.
Sin dhá phíosa comhionann de sonraí, ceart, tá muid ag lorg trí.
Ach a mhalairt, aon Tá dhá phíosa sonraí
ráthaithe a bheith acu treochláir uathúil trí struchtúr seo sonraí.
Agus táimid ag dul a chur le breathnú ar a amhairc an i nóiméad ach.
>> Beidh muid é seo a dhéanamh trí iarraidh a struchtúr sonraí nua a chruthú,
mapáil an eochair péirí luach leanas.
Sa chás seo, ní táimid ag dul a úsáid rud chomh simplí mar Boole.
Beidh muid a stóráil i ndáiríre an teaghrán.
Agus is é sin teaghrán ag dul go dtí bheith ar an t-ainm ollscoil.
>> Agus is é an eochair ag dul a bheith an bhliain nuair a bhí a bunaíodh an ollscoil sin.
Gach blianta d'ollscoileanna ag dul a bheith ceithre dhigit.
Agus mar sin beidh orainn a úsáid na ceithre digití nascleanúint a dhéanamh tríd an struchtúr seo sonraí.
Agus beidh orainn a fheiceáil, arís, conas dhéanaimid sin i díreach an dara.
>> Ag deireadh an cosán, beidh orainn a fheiceáil ar an t-ainm
na hollscoile a fhreagraíonn leis sin eochair, iad siúd ceithre dhigit.
An smaoineamh bunúsach taobh thiar de Trie Is mór dúinn a bealach lárnach.
Mar sin, smaoineamh ar é mar a bheadh ​​crann.
Agus tá sé seo den chineál céanna i litriú agus i gcoincheap le crann.
Go ginearálta nuair a cheapann againn faoi crainn ar fud an domhain fíor,
tá siad ar fhréamh go sa talamh agus iad ag fás aníos
agus tá siad brainsí agus tá siad duilleoga.
Agus go bunúsach an smaoineamh Is Trie díreach mar an gcéanna,
ach amháin go bhfuil an fhréamh ancaire áit éigin sa spéir.
Agus tá na duilleoga ag bun an leathanaigh.
>> Mar sin, tá sé de chineál cosúil le cur crann agus díreach flipping sé bun os cionn.
Ach fós tá brainsí.
Agus bheadh ​​na a bheith ar ár conairí, beidh na a bheith ar ár naisc
ó na fréamhacha go dtí na duilleoga.
Sa chás seo, iad siúd cosáin, na brainsí
bhfuil an lipéadú le digití a insint dúinn cén bealach chun dul ó áit a bhfuil muid.
>> Má fheiceann muid 0, théann muid síos an brainse, má fheiceann muid 1, théann muid síos an brainse,
agus mar sin de agus mar sin de.
Bhuel, cad a chiallaíonn sé?
Bhuel, ciallaíonn sé sin go ag gach pointe acomhal
agus gach nód sa lár agus gach brainse,
tá 10 agus is féidir áiteanna gur féidir linn dul.
Mar sin, tá 10 leideanna ó gach suíomh.
>> Agus é seo i gcás inar féidir iarracht a fháil ar beag giotán imeaglaithe do dhuine éigin
nach bhfuil a lán de tá taithí san eolaíocht ríomhaireachta roimhe.
Ach tá iarracht i ndáiríre uamhnach go leor.
Agus má tá tú ar an deis a bheith ag obair leo
agus an bhfuil tú sásta a tochailt-i agus turgnamh leo,
tá siad i ndáiríre suimiúil go leor struchtúir sonraí a bheith ag obair leis.
Más mian linn a chur isteach gné isteach sa Trie, go léir is gá dúinn a dhéanamh
Tá a thógáil ar an cosán ceart ó na fréamhacha go dtí an duilleog.
Seo an méid gach céim chomh D'fhéadfadh an mbealach cuma mhaith.
Táimid ag dul chun sonraí nua a shainmhíniú struchtúr nód nua ar a dtugtar ar Trie.
>> Agus taobh istigh de na sonraí sin Struchtúr tá dhá phíosa.
Táimid ag dul a stóráil ar an ainm ollscoile.
Agus táimid ag dul a stóráil le sraith de leideanna
le nóid eile den chineál céanna.
Mar sin, arís, tá sé seo gur saghas de choincheap na i ngach áit
tá muid, táimid ag ag 10 féidir áiteanna is féidir linn dul.
Má fheiceann muid 0, théann muid síos an brainse.
Má fheiceann muid 1, an brainse, agus mar sin de agus mar sin de agus mar sin de.
Má deirimid 9, théann muid síos an brainse.
Mar sin, ag gach pointe acomhal, is féidir linn dul ar 10 áiteanna agus is féidir.
Mar sin, tá gach nód a bhfuil 10 leideanna nóid eile, go dtí 10 nóid eile.
>> Agus is é an sonraí táimid stóráil ach an t-ainm na hollscoile.
Mar sin, a ligean ar a thógáil Trie.
A ligean ar chur isteach ar feadh cúpla na míreanna isteach inár Trie.
Mar sin, ag an mbarr an-, is é seo ár n-nód fréimhe.
Is dócha go bhfuil sé seo ag dul a bheith rud éigin tú ag dul dhearbhú a domhanda.
Agus tá tú ag dul a choimeád ar bun a domhanda pointeoir leis an nód i gcónaí.
>> Tá tú ag dul a rá, ionann fréimhe, agus an bhfuil tú
ag dul go dtí malloc féin nód Trie.
Agus riamh bhfuil tú ag dul fhréamh chun teagmháil a dhéanamh arís.
Gach uair is mian leat a tús a nascleanúna tríd,
leagtar tú pointeoir eile cothrom le fhréamh, cosúil le trav,
a bhfuil an sampla I úsáid i gcuid mhaith de mo físeáin
anseo ar stoic agus ar scuainí agus liostaí nasc agus mar sin de.
>> Leagtha tú pointeoir eile iarr trav do traversal.
Agus a úsáideann tú trav nascleanúint tríd an struchtúr sonraí.
Mar sin a ligean ar a fheiceáil conas a d'fhéadfadh sé seo cuma.
Mar sin ceart anois, cad dhéanann nód cuma mhaith?
Bhuel, díreach mar ár sonraí dearbhú struchtúr atá léirithe,
ní mór dúinn a teaghrán, a sa chás seo tá folamh.
Níl rud ar bith anseo.
>> Agus le sraith de 10 leideanna.
Agus an ceart anois, againn ach tá 1 nód sa Trie.
Níl rud ar bith eile ann.
Mar sin go léir 10 de na leideanna pointe a margadh saothair.
Sin an méid léiríonn an dearg.
>> A ligean ar chur isteach ar an teaghrán Harvard.
A ligean ar chur isteach ar an Ollscoil Harvard isteach sa Trie, a
Bunaíodh sa bhliain 1636.
Is mian linn a bhaint as an eochair, 1636, a insint dúinn nuair a bhíonn muid
ag dul a stóráil Harvard sa Trie.
Anois, conas a d'fhéadfadh muid a dhéanamh?
>> D'fhéadfadh sé cuma rud éigin mar seo.
Tús a chur againn ag an fhréamh.
Agus ní mór dúinn na 10 háiteanna is féidir linn dul.
Is é an fhréamh díreach mar aon nód eile den Trie.
Tá 10 áiteanna is féidir linn dul ó anseo.
>> Cá háit ar mian linn a is dócha chun dul go má tá an eochair 1636?
Níl i ndáiríre dhá rogha.
Ceart.
Is féidir linn a thógáil ar an eochair ó ceart ar chlé agus tús le 6.
Nó d'fhéadfadh muid a thógáil ar an eochair ó chlé go deas agus tús a chur le 1.
>> Tá sé dócha níos mó iomasach mar bheith ag an duine
a tuigimid go mbainfidh ach dul chlé go deas.
Agus mar sin más mian liom a chur isteach Harvard isteach sa Trie,
Ba mhaith liom is dócha a thosú ag tosú ag an fhréamh,
ag féachaint ar mo 10 rogha i os comhair dom, agus ag rá
Ba mhaith liom dul síos an cosán 1.
OK.
>> Anois, tá 1 cosán null faoi láthair.
Mar sin, más mian liom dul ar aghaidh síos go cosán a chur isteach an ghné seo isteach sa Trie,
Caithfidh mé a malloc nód nua, tá 1 pointe ann, agus ansin tá mé go maith chun dul.
>> Mar sin, tá mé go bunúsach ag i gcás ina pointe Tá mé ag seasamh
ag an fhréamh an crann nó an Trie agus tá 10 brainsí.
Ach tá gach brainse a geata os comhair é.
Ceart.
Mar níl rud ar bith eile atá ann.
Níl aon pasáiste sábháilte.
Ciallaíonn sé sin go níl rud ar bith síos aon cheann de na brainsí.
Más mian liom a thógáil chun tús a chur rud éigin, ba mhaith liom a bhaint as an geata.
Ba mhaith liom a bhaint as an geata os comhair uimhir 1.
Agus ba mhaith liom ag siúl síos go.
Agus ba mhaith liom a thógáil áit eile dom dul.
>> Agus sin an méid atá déanta agam anseo.
Mar sin, 1 a thuilleadh pointí a margadh saothair.
Dúirt mé tá sé sábháilte chun dul síos anseo anois.
Tógadh mé nód eile.
Agus nuair a rachaidh mé go dtí sin nód, mé ní mór cinneadh eile a dhéanamh.
Áit a bhfuil mé ag dul chun dul ó anseo?
>> Bhuel, tá mé imithe cheana féin síos ar an 1.
Mar sin, anois is mian liom is dócha chun dul síos an 6.
Ceart.
Arís, tá mé 10 láthair is féidir liom a roghnú.
Mar sin, a ligean ar dul síos anois uimhir 6.
Mar sin mé soiléir ar an geata os comhair uimhir 6.
Agus siúl mé síos ann.
Agus mé a thógáil nód eile.
Agus tá mé bainte amach pointe acomhal eile.
>> Arís, tá mé 10 roghanna do nuair is féidir liom dul.
Tá mé ar athraíodh a ionad ó 1 go 6.
Mar sin, anois is mian liom is dócha chun dul go dtí 3.
3, níl aon áit is féidir liom dul.
Ionas go mbeidh mé go soiléir ar an mbealach agus mé féin a thógáil spás nua.
Agus ansin ó 3, i gcás ina bhfuil mhaith liom dul?
Ba mhaith liom dul síos 6.
>> Agus, arís, bhí orm soiléir ar an mbealach chun é a dhéanamh.
Mar sin, anois tá mé úsáid as mo eochair a chur isteach a chruthú nóid agus tús a thógáil ar an Trie.
Tá mé thosaigh ag an fhréamh.
Tá mé imithe síos 1636.
Agus anois tá mé ag bun ann ar an nód.
Agus d'fhéadfá a bheith in ann é a fheiceáil ar do scáileán.
>> Tá sé seo chun suntais i buí.
Sin an áit a bhfuil mé i láthair na huaire.
Is é mo eochair a dhéanamh.
Tá ídithe mé gach post i mo eochair.
Mar sin, ní féidir liom dul níos faide.
Mar sin, ag an bpointe seo, gach mé gá i ndáiríre a dhéanamh ná a rá, OK.
Tá sé seo de chineál ar cosúil lorg síos ag an talamh,
má tá tú ag shamhlú féin mar an saghas cosán
le naisc éagsúla.
Sórtáil de ag féachaint síos agus saghas spraeála péinteáil Harvard ar an talamh.
Sin an t-ainm seo.
Know go bhfuil an méid atá ag an suíomh seo.
Má thosaíonn muid ag an fhréamh agus a théann muid síos 1 agus ansin 6 agus ansin 3 agus ansin 6,
áit a bhfuil muid?
Bhuel má táimid síos agus feicimid Harvard, ansin
tá a fhios againn go raibh Harvard a bunaíodh sa bhliain 1636 bunaithe ar an mbealach
tá muid ag cur chun feidhme an struchtúr seo sonraí.
Mar sin, bhí go súil againn go simplí.
Táimid ag dul a dhéanamh ar dhá insertions níos mó.
Agus táthar ag súil go mbainfidh sé cabhrú le féach sé seo déanta dhá uair níos mó.
>> Anois, a ligean ar chur isteach ollscoil eile.
A ligean ar chur isteach Yale isteach sa Trie.
Bunaíodh i 1701 bhí Yale.
Mar sin, beidh orainn tús a chur ag an fhréamh, mar a bhíonn againn i gcónaí.
Agus leag muid pointeoir traversal.
Táimid ag dul a úsáid a bhaint as go bhfuil a bhogadh tríd.
An chéad rud ba mhaith linn a dhéanamh ná dul síos an cosán 1.
Sin an chéad dhigit de ár eochair.
Fortunately, áfach, ní dhéanaimid a dhéanamh ar aon obair an am seo.
Tá an cosán 1 réitithe cheana.
Glanadh mé é roimhe nuair mé Bhí a chur isteach Harvard ag 1636.
Mar sin, is féidir liom bogadh go sábháilte síos 1 agus díreach dul ann.
Más féidir bogadh síos ar an 1.
>> Anois, áfach, ba mhaith liom dul go dtí 7.
Glanadh mé an bealach ar 6.
Tá a fhios agam is féidir liom go sábháilte dul ar aghaidh síos an cosán 6.
Ach is gá dom dul ar aghaidh ar an gcosán 7.
Mar sin, cad is gá dom a dhéanamh?
Bhuel, díreach mar a bhíodh, is gá mé díreach tar éis go soiléir ar an geata, a fháil amach as an mbealach,
agus a thógáil nód nua as an cosán 7.
Díreach mar seo.
>> Mar sin, anois tá mé ar athraíodh a ionad 1 agus ansin 7.
Agus faoi deara anois, tá mé saghas den ar an subbranch nua.
Ceart.
Gach rud eile ó 16 ar, ní féidir liom cúram faoi.
Níl mé ag déanamh rud ar bith 16.
Tá mé ag déanamh 17 stuif.
>> Mar sin, anois ó 17 ar aghaidh, caithfidh mé a saghas blaze cosáin nua anseo.
Is é mo eochair an dhigit chugainn 0.
Ní féidir liom a fháil go soiléir in áit ar bith.
Tógadh mé díreach tar éis an nód.
Mar sin, tá a fhios agam níl aon cosáin ar aghaidh ó anseo.
Mar sin, caithfidh mé a dhéanamh ar cheann féin.
>> Mar sin, malloc mé nód nua agus tá 0 phointe ann.
Agus ansin amháin níos mó ama, malloc mé nód nua agus tá pointe amháin ann.
Arís, tá mé ídithe mo eochair, 1701.
Mar sin, tá mé síos agus spraeála liom péint Yale.
Sin an t-ainm seo a nód.
>> Agus mar sin anois más gá dom riamh a fheiceáil má Yale Tá an Trie, tús a chur mé ag an fhréamh,
Téim síos 1701, agus breathnú síos.
Agus má fheiceann mé Yale spraeála péinteáilte ar an talamh, ansin
Tá a fhios agam Yale ann sa Trie.
A ligean ar a dhéanamh amháin níos mó.
A ligean ar chur isteach Dartmouth isteach sa Trie, a bunaíodh i 1769 bhí ina.
>> Tosaigh ag an fhréamh arís.
Is é mo chéad dhigit de mo eochair 1.
Is féidir liom dul go sábháilte síos go cosán.
Atá ann cheana.
Is é an dhigit eile de mo eochair 7.
Is féidir liom dul go sábháilte síos go cosán.
Tá sé ann chomh maith.
>> Is é mo chéad 6.
Ón áit seo, ó áit a bhfuil mé i láthair na huaire i buí ann sa mhéid is go nód lár,
6 faoi ghlas faoi láthair as.
Más mian liom dul síos go cosán, Caithfidh mé a thógáil air féin.
Mar sin, beidh mé malloc nód nua agus tá 6 phointe ann.
Agus ansin, arís, tá mé blazing cosáin nua anseo.
>> Mar sin, malloc mé nód nua ionas gur as go bhfuil uimhir cosán node-- 9-- agus ansin anois
má taisteal mé 1769, agus tá mé ag síos.
Níl rud ar bith faoi láthair spraeála péinteáilte ansin.
Is féidir liom scríobh Dartmouth.
Agus tá mé a cuireadh isteach Dartmouth isteach sa Trie.
>> Mar sin, tá go a chur isteach rudaí isteach sa Trie.
Anois, ba mhaith linn a chuardach le haghaidh rudaí.
Conas is féidir linn a chuardach le haghaidh rudaí sa Trie?
Bhuel, tá sé go leor i bhfad ar an smaoineamh céanna.
Anois táimid ag úsáid ach na digití de na príomh a fháil amach an féidir linn a nascleanúint ó na fréamhacha
chun áit ar mhaith linn dul sa Trie.
>> Má bhuail muid ar deireadh marbh ag pointe ar bith, ansin Tá a fhios againn nach féidir eilimint ann
nó eile a bheadh ​​go cosán curtha glanta cheana.
Má dhéanann muid go léir ar an mbealach chun an deireadh, go léir is gá dúinn a dhéanamh
Is breathnú síos agus a fheiceáil más rud é go an eilimint táimid ag lorg.
Má tá sé, rath.
Más rud é nach bhfuil sé, theipeann.
>> Sin a ligean le cuardach Harvard sa Trie.
Tús a chur againn ag an fhréamh.
Agus, arís, táimid ag dul chun pointeoir traversal chruthú
a dhéanamh ar ár bogann dúinn.
Ó na fréamhacha a fhios againn go bhfuil an Is é an chéad áit ní mór dúinn dul 1,
Is féidir linn a dhéanamh sin?
Is féidir linn.
Má ann go sábháilte.
Is féidir linn dul ann.
>> Anois, is é an áit eile is gá dúinn dul 6.
An dtugann an cosán 6 ann ó anseo?
Yeah, a dhéanann sé.
Is féidir linn dul síos an cosán 6.
Agus muid ag deireadh suas anseo.
>> An féidir linn dul síos an cosán 3 ó anseo?
Bhuel, mar a casadh sé amach, yes, ann go bhfuil an iomarca.
Agus is féidir linn a fháil ar an cosán 6 ó anseo?
Is féidir linn.
>> Nach bhfuil againn go leor fhreagair an cheist go fóill.
Níl fós amháin níos mó chéim, atá anois
ní mór dúinn chun breathnú síos agus féach más rud é go actually--
má tá muid ag lorg Harvard é, go cad a fháil againn tar éis dúinn sceite an eochair?
Sa sampla tá muid ag baint úsáide as anseo, Is iad na blianta i gcónaí ceithre dhigit.
Ach d'fhéadfá a bheith ag baint úsáide as an sampla ina tá tú ag a stóráil foclóir de na focail.
>> Agus mar sin in ionad a bheith 10 leideanna do mo suíomh, a bheadh ​​agat 26.
Ceann amháin do gach litir den aibítir.
Agus tá roinnt focail cosúil le sciathán leathair, is fo-thacar de bhaisc, mar shampla.
Agus mar sin, fiú má fhaigheann tú go dtí an deireadh an eochair agus tú ag féachaint síos,
nach dtiocfadh leat a fheiceáil cad bhfuil tú ag lorg.
>> Mar sin, tá tú i gcónaí a lean an cosán ar fad agus ansin
má bhí tú in ann go rathúil chun Traverse an cosán ar fad,
breathnú síos agus a dhéanamh deimhniú deiridh amháin.
An é sin cad tá mé ag lorg?
Bhuel, tá mé síos i ndiaidh tosú ag an mbarr agus ag dul 1636.
Táim ag síos.
Feicim Harvard.
Mar sin, tá, d'éirigh mé.
Cad a tharlaíonn má cad Táim ag lorg nach bhfuil sa Trie, cé.
Cad a tharlaíonn má tá mé ag lorg Princeton, a bunaíodh i 1746.
Agus mar sin 1746 thiocfaidh chun bheith mo eochair chun nascleanúint a dhéanamh tríd an Trie.
Bhuel, tús a chur mé ag an fhréamh.
Agus ar an gcéad dul Ba mhaith liom go téann síos an cosán 1.
An féidir liom a dhéanamh?
Sea, is féidir liom.
>> An féidir liom dul síos an cosán 7 ó ann?
Yeah, is féidir liom.
Atá ann freisin.
Ach is féidir liom dul síos an cosán 4 ó anseo?
Sin cosúil ag iarraidh ar an cheist, is féidir Dul ar aghaidh mé síos go cearnach beag
go atá béim mé i buí?
Níl rud ar bith ann.
Ceart.
>> Níl aon bhealach chun tosaigh síos an cosán 4.
Má bhí Princeton sa Trie, go 4 bheadh ​​glanta dúinn cheana.
Agus mar sin ag an bpointe seo tá muid bainte amach ar deireadh marbh.
Ní féidir linn dul níos faide.
Agus mar sin is féidir linn a rá, go cinntitheach, gan aon.
Ní Princeton ann sa Trie.
>> Mar sin, cad a chiallaíonn sé seo go léir?
Ceart.
Níl a lán ar siúl anseo.
Níl leideanna ar fud na háite.
Agus, mar is féidir leat a fheiceáil díreach ón léaráid,
níl a lán de na nóid sin Tá de chineál ar eitilt timpeall.
Ach faoi deara gach uair a bhíomar ag iarraidh a seiceáil cibé raibh rud éigin sa Trie,
bhí againn ach a dhéanamh 4 mbogann.
>> Gach uair bhíomar ag iarraidh a cuir isteach rud éigin sa Trie,
ní mór dúinn a dhéanamh 4 mbogann, b'fhéidir, mallocing roinnt rudaí feadh na slí.
Ach mar a chonaic muid nuair a cuireadh isteach táimid ag Dartmouth isteach sa Trie,
uaireanta roinnt de na cosán D'fhéadfadh a glanadh cheana féin le haghaidh dúinn.
Agus mar sin mar a fhaigheann ár n-Trie níos mó agus níos mó, ní mór dúinn a dhéanamh obair níos lú gach uair
a chur isteach rudaí nua toisc go bhfuil muid cheana
tógtha a lán de na idirmheánacha brainsí feadh na slí.
Má tá muid ach riamh chun breathnú ar 4 rudaí, tá 4 ach tairiseach.
Táimid i ndáiríre de chineál ar druidim leanas a chur isteach am tairiseach
agus Lookup am tairiseach.
An tradeoff, ar ndóigh, a bheith go an Trie, mar is féidir leat insint is dócha,
Is ollmhór.
Gach ceann de na nóid Bíonn suas go leor de spás.
>> Ach sin an tradeoff.
Más mian linn i ndáiríre tapaidh a chur isteach, scriosadh i ndáiríre tapaidh,
agus Lookup ndáiríre tapaidh, ní mór dúinn a tá a lán de na sonraí eitilt timpeall.
Ní mór dúinn a chur ar ceal a lán de spás agus cuimhne don struchtúr sonraí
a bheith ann.
>> Agus mar sin go bhfuil an tradeoff.
Ach tá sé cosúil linn a d'fhéadfadh a fuair sé.
D'fhéadfadh muid a fuarthas amach go Soitheach Naofa de struchtúir sonraí
le leanas a chur isteach tapa, scriosadh, agus a chuardach.
Agus b'fhéidir go mbeidh sé seo a bheith ina Struchtúr sonraí cuí
a úsáid ar cibé faisnéis táimid ag iarraidh a siopa.
Tá mé Doug Lloyd, is é seo CS50.