>> [MUSIC nagpe-play]
DOUG LLOYD: Kaya namin na-inching mas malapit at mas malapit na banal na Kopita ng data
kaayusan, isa na maaari naming ipasok sa, tanggalin mula sa, at maghanap ng
nasa tapat na oras.
Right.
Iyan ay ang uri ng layunin.
Gusto naming magawa mga bagay na tunay, tunay mabilis.
>> May natagpuan namin ito dito kapag pinag-uusapan natin ang tungkol sa mga sumusubok?
Well, sabihin kumuha ng isang hitsura.
Kaya nakita namin ang ilang mga iba't ibang kayarian ng data
na panghawakan ang mga pagmamapa ng tinatawag na mga pares ng key-value,
paggawa ng mga mapa sa ilang piraso ng data sa ilang iba pang mga piraso ng data
upang malaman namin kung saan makikita ang impormasyon sa istraktura.
>> Kaya para sa array, halimbawa, ang key ay ang index elemento o array
lokasyon 0 o array 1 at iba pa.
At ang halaga ay ang data na umiiral sa lokasyon na iyon.
Kaya kung ano ang naka-imbak sa array 0?
Ano ay naka-imbak sa array 1 laban lamang 0 at 1, na kung saan ay ang susi.
>> Sa pamamagitan ng isang hash table ito ay uri ng parehong ideya.
Sa pamamagitan ng isang hash table, taglay namin ang hash function na bumubuo hash code.
Kaya ang susi ay ang hash code ng data.
At ang halaga, lalo na usapan natin ang tungkol pagdudugtong
sa video sa hash talahanayan, ay na-link na listahan ng data
na hash sa na hashcode.
Right.
Paano ang tungkol sa iba pang diskarte ang paraan na ito, kahit na?
Ano ang tungkol sa isang paraan kung saan ang key ay garantisadong maging natatangi,
hindi katulad ng isang hash table, kung saan maaari namin end up sa dalawang piraso ng data
pagkakaroon ng parehong hashcode.
At pagkatapos kami ay may sa pakikitungo sa na sa pamamagitan ng alinman sa probing o higit pa
mas mabuti ang pagdudugtong upang ayusin ang problema.
>> Kaya ngayon maaari naming garantiya na ang aming mga key ay kakaiba.
At paano kung ang aming halaga ay isang bagay na tulad ng madaling
bilang tunay at huwad na nagsasabi sa amin kung o hindi na piraso ng impormasyon
umiiral sa istraktura?
Ang isang Boolean maaaring maging kasing simple ng isang bit.
Realistically ito ay maaring isang byte mas malamang kaysa sa isang bit.
Ngunit iyon lamang ang isang pulutong na mas maliit sa pagtatabi marahil ng isang 50-character string,
Halimbawa.
>> Kaya sumusubok, katulad ng hash talahanayan, na kung saan pinagsama array at naka-link na listahan,
pagsamahin ang mga pagsusubok na array, istruktura, at mga payo
sama-sama upang mag-imbak ng data sa isang kawili-wiling paraan na
medyo iba mula sa anumang bagay na nakita namin sa ngayon.
Ngayon kami ay gumagamit ng data bilang isang roadmap upang mag-navigate ito istraktura ng data.
At kung maaari naming sundin ang roadmap, kung maaari naming
sundin ang mga data mula sa simula sa dulo, bibigyan namin ng
alam kung na data umiiral sa trie.
>> At kapag hindi namin na sundin ang mga mapa mula sa ibig sabihin sa mga end sa lahat,
hindi maaaring umiiral ang data.
Muli, ang mga susi dito ay garantisadong maging kakaiba.
At kaya hindi katulad ng isang hash table, bibigyan namin ng hindi kailanman kailangang harapin ang mga banggaan dito.
At walang dalawang piraso ng data may eksakto ang parehong roadmap
maliban na data ay magkapareho.
>> Kung ipasok namin John, pagkatapos paghahanap para sa John.
Iyon ang dalawang magkatulad na mga piraso ng data, right, naghahanap kami sa pamamagitan ng.
Ngunit sa kabilang banda, ang anumang dalawang piraso ng data ay
garantisadong na magkaroon ng natatanging roadmaps sa pamamagitan na ito istraktura ng data.
At kami ay pagpunta sa tumagal ng isang pagtingin sa isang visual ng mga ito sa ilang sandali lamang.
>> Gagawin namin ito sa pamamagitan ng pagsubok sa lumikha ng isang bagong istraktura ng data,
paggawa ng mga mapa ang mga sumusunod na mga pangunahing mga pares ng halaga.
Sa kasong ito, hindi namin pagpunta upang gamitin ang kasing simple ng isang Boolean isang bagay.
Kami ay talagang mag-iimbak ang string.
At na string ay pagpunta sa ang pangalan ng isang unibersidad.
>> At ang susi ay magiging taon kapag na unibersidad ay itinatag.
Lahat ng mga taon para sa mga unibersidad ay magiging apat na digit.
At kaya gagamitin namin ang mga apat na digit navigate sa pamamagitan ng mga istraktura ng data.
At kami makita, muli, kung paano gagawin namin na sa isang segundo lang.
>> Sa dulo ng landas, ipapakita namin makita ang pangalan
ng unibersidad na tumutugma sa na key, ang mga apat na digit.
Ang pangunahing ideya sa likod ng isang trie ay kami ay may isang sentral na ruta.
Kaya mag-isip tungkol sa mga ito tulad ng isang puno.
At ito ay katulad sa spelling at sa konsepto sa isang puno.
Karaniwan kapag sa tingin namin tungkol puno sa tunay na mundo,
mayroon sila ng isang ugat na ang sa lupa at maging sila ay paitaas
at sila ay may sanga at sila ay may mga dahon.
At isa lamang ang mga ideya ng isang trie ay eksaktong kapareho,
maliban ugat na anchor lugar sa kalangitan.
At ang mga dahon ay sa ilalim.
>> Kaya ito ay uri ng tulad ng pagkuha ng isang puno at lamang flipping ito baligtad.
Ngunit may mga sanga pa rin.
At yaong kaya ang ating daanan, mga ito ay ang aming mga koneksyon
mula sa mga ugat ng mga dahon.
Sa kasong ito, ang mga mga landas, mga sanga
ay may label na may mga digit na sabihin sa amin kung aling mga paraan upang pumunta mula sa kung saan kami.
>> Kapag nakita namin ang isang 0, pumunta kami pababa sangay na ito, kung makita natin ang isang 1, pumunta kami pababa sangay na ito,
at iba at iba pa.
Well, kung ano ang ibig sabihin nito?
Well, na nangangahulugan na ang sa bawat kantong point
at ang bawat node sa gitna at ang bawat sanga,
may mga 10 na posible lugar na maaari naming pumunta.
Kaya may mga 10 mga payo mula sa bawat lokasyon.
>> At ito ay kung saan sinusubukan ng maaaring makakuha ng isang Medyo pananakot para sa isang tao
sino ang hindi magkaroon ng isang pulutong ng mga karanasan sa computer science bago.
Ngunit pagsusubok ay talagang medyo kasindak-sindak.
At kung mayroon kang mga pagkakataon upang gumana sa mga ito
at ikaw ay handa na maghukay-in at mag-eksperimento sa mga ito,
ang mga ito ay talagang lubos na interesante istruktura ng data upang gumana sa.
Kung nais namin na ipasok ang isang elemento sa trie, ang lahat ng kailangan naming gawin
ay bumuo ng ang tamang landas mula sa mga ugat sa dahon.
Narito kung ano ang bawat hakbang na kasama maaaring magmukhang ang paraan.
Kami ay pagpunta upang tukuyin ang isang bagong data istraktura para sa isang bagong node tinatawag na isang trie.
>> At sa loob ng na data istraktura ay may dalawang piraso.
Kami ay pagpunta sa tindahan ng pangalan ng isang unibersidad.
At kami ay pagpunta sa mga tindahan ng isang array ng payo
sa iba pang mga nodes ng parehong uri.
Kaya, muli, ito ay na-uri-uriin ng konsepto ng lahat ng dako
tayo, kami sa 10 posibleng lugar na maaari naming pumunta.
Kapag nakita namin ang isang 0, pumunta kami pababa sangay na ito.
Kapag nakita namin ang isang 1, sangay na ito, at iba pa at iba pa at iba pa.
Kung sinasabi nating 9, pumunta kami pababa sangay na ito.
Kaya sa bawat kantong point, kami ay maaaring pumunta 10 posibleng mga lugar.
Kaya ang bawat node ay naglalaman ng 10 mga payo sa iba pang mga nodes, 10 iba pang mga node.
>> At ang data namin ang pag-iimbak ay lamang ang pangalan ng unibersidad.
Kaya ipaalam sa bumuo ng isang trie.
Ipasok ang isang pares Ipaalam ng mga item sa aming trie.
Kaya sa pinakatuktok, ito ay ang aming root node.
Ito ay marahil pagpunta sa maging isang bagay ikaw ay pagpunta sa globally claim.
At ikaw ay pagpunta sa globally mapanatili isang pointer sa node na ito palagi.
>> Ikaw ay pagpunta sa sabihin, ugat ay katumbas ng, at ikaw ay
pagpunta sa malloc iyong sarili trie node.
At hindi ka na pagpunta pindutin muli root.
Sa bawat oras na nais mong magsimulang mag-navigate sa pamamagitan ng,
set ka ng isa pang pointer pantay-pantay sa root, tulad ng mga trav,
na kung saan ay ang mga halimbawa ko gamitin sa maraming ng aking mga video
dito sa stack at queues at mga listahan ng mga link at iba pa.
>> Itakda mo ang isa pang pointer tinatawag trav para traversal.
And mong gamitin trav upang mag-navigate sa pamamagitan ng mga istraktura ng data.
Kaya sabihin makita kung paano maaaring tumingin ito.
Kaya ngayon, kung ano ang hitsura ng isang node tulad?
Well, tulad ng aming data istraktura deklarasyon ipinahiwatig,
kami ay may isang string, na kung saan sa kasong ito ay walang laman.
Mayroong wala dito ang.
>> At isang array ng 10 mga payo.
At ngayon, kami lamang may 1 node sa trie.
May wala pa sa ito ay.
Kaya lahat ng 10 ng mga payo point sa null.
Iyon ay kung ano ay nagpapahiwatig ng pula.
>> Ipasok sa string Harvard Hayaan.
Ni ipasok ang University of Hayaan Harvard sa ito trie, na
ay itinatag noong taong 1636.
Gusto naming gamitin ang susi, 1636, upang sabihin sa amin kung saan hindi namin
pagpunta sa tindahan ng Harvard sa trie.
Ngayon, paano namin gawin iyon?
>> Maaaring tumingin Ito ang isang bagay na tulad nito.
Simulan namin sa root.
At kami ay may mga 10 lugar na maaari naming pumunta.
Ang ugat ay tulad ng anumang iba pang mga node ng trie.
May mga 10 mga lugar na maaari naming pumunta mula dito.
>> Saan ang marahil kami gusto upang pumunta kung ang susi ay 1636?
Mayroon talagang dalawang mga pagpipilian.
Right.
Maaari naming bumuo ng ang key mula sa karapatan sa kaliwa at simulan na may 6.
O maaari kaming bumuo ng mga susi mula sa kaliwa papunta sa kanan at magsimula sa 1.
>> Ito ay marahil mas intuitive bilang isang tao
upang maunawaan namin makikita lang pumunta sa kaliwa papuntang kanan.
At kaya kung gusto kong ipasok Harvard sa ito trie,
Malamang na gusto kong simulan sa pamamagitan ng pagsisimula sa root,
naghahanap sa aking 10 mga pagpipilian sa harap ko, at sinasabi
Gusto kong pumunta down ang 1 path.
SIGE.
>> Ngayon, 1 landas ay kasalukuyang null.
Kaya kung nais kong magpatuloy down na landas upang ipasok ang elementong ito sa trie,
Mayroon akong mag-malloc isang bagong node, may 1 point doon, at pagkatapos ay ako ay magandang pumunta.
>> Kaya talaga ako sa isang kung saan punto ako nakatayo
sa ugat ng puno o ang trie at may 10 sanga.
Subalit ang bawat sangay ay may gate sa harap nito.
Right.
Dahil mayroong wala pa ang mayroong.
Hindi ligtas na daanan.
Iyon ay nangangahulugan na wala doon down ng anuman sa mga sanga.
Kung gusto ko upang simulan ang gusali isang bagay, gusto kong tanggalin ang gate.
Gusto kong alisin ang gate sa harap ng number 1.
At gusto kong maglakad pababa na.
At gusto ko na bumuo ng isa pang lugar para sa akin upang pumunta.
>> At na kung ano ang aking nagawa dito.
Kaya 1 ay hindi na tumuturo sa null.
Sinabi ko na ito ay ligtas na bumaba dito ngayon.
Ako na binuo ng isa pang node.
At kapag nakakuha ako sa na node, ako magkaroon ng isa pang desisyon na gumawa.
Saan ako pagpunta upang pumunta mula dito?
>> Well, na wala na akong pababa ang 1.
Kaya ngayon ay malamang na gusto kong pumunta down ang 6.
Right.
Muli, ako ay may 10 mga lokasyon maaari kong piliin.
Kaya hana ngayon down number 6.
Kaya i-clear ko ang gate sa harap ng number 6.
At lumakad ako doon.
At bumuo ako ng isa pang node.
At naabot ko na ang isa pang kantong point.
>> Muli, ako ay may 10 mga pagpipilian para sa kung saan ang maaari kong pumunta.
Ko na inilipat mula 1 hanggang 6.
Kaya ngayon ay malamang na gusto kong pumunta sa 3.
3, mayroong wala kahit saan ang maaari kong pumunta.
Kaya ko bang i-clear ang paraan at bumuo ng aking sarili ng isang bagong space.
At pagkatapos ay mula sa 3, kung saan ang gusto kong pumunta?
Gusto kong pumunta down 6.
>> At, muli, ako ay upang malinaw na ang paraan upang gawin ito.
Kaya ngayon na ginagamit ko na ang aking mga susi sa ipasok lumikha nodes at magsimula na magtayo ito trie.
Sinimulan ko sa root.
Ako ay wala na down na 1636.
At ngayon ako sa ibaba doon sa na node.
At maaari mo na makita ang mga ito sa iyong screen.
>> Ito ay naka-highlight sa dilaw.
Iyon ay kung saan ako kasalukuyang am.
Aking key ay tapos na.
Naubos ko na ang bawat posisyon sa aking key.
Kaya hindi ako maaaring pumunta sa anumang karagdagang.
Kaya sa puntong ito, ang lahat ng ko talagang kailangan mong gawin ay sabihin, OK.
Ito ay uri ng tulad ng pagtingin down sa lupa,
kung ikaw ay envisioning ang iyong sarili bilang ang uri ng mga landas
na may iba't ibang mga koneksyon.
Pagsunud-sunurin ng naghahanap down at uri ng spray pagpipinta Harvard sa lupa.
Iyan ang pangalan ng mga ito.
Malaman na kung ano ang sa lokasyong ito.
Kung magsisimula kami sa root at pumunta kami pababa 1 at pagkatapos ay 6 at pagkatapos ay 3 at pagkatapos ay 6,
Nasaan ba tayo?
Well kung titingnan namin down na at nakita namin Harvard, pagkatapos
alam namin na Harvard ay itinatag sa 1636 batay sa mga paraan
kami ay pagpapatupad na ito istraktura ng data.
Kaya na ay inaasahan namin na tapat.
Kami ay pagpunta sa gawin ang dalawang higit pang mga pagpapasok.
At sana ito ay makatulong sa makikita ito gawin ng dalawang beses pa.
>> Ngayon, ipasok ang isa pang university ipaalam.
Ni ipasok Yale na ito sa trie Hayaan.
Yale ay itinatag sa 1701.
Kaya makikita namin magsimula sa root, gaya ng lagi naming gawin.
At kami ay itakda ang isang traversal pointer.
Kami ay pagpunta sa paggamit na upang ilipat sa pamamagitan ng.
Ang unang bagay na gusto naming gawin ay pumunta down ang 1 path.
Iyan ang unang titik ng aming mga key.
Sa kabutihang palad, bagaman, ay hindi kami kailangang gawin ang anumang trabaho sa oras na ito.
Ang 1 na landas ang nai-clear.
Nabura ko ito dati noong ako ay pagpasok ng Harvard sa 1,636.
Kaya ko ligtas na ilipat down 1 at pumunta lamang doon.
Kung maaari ilipat pababa ang 1.
>> Ngayon, bagaman, nais kong pumunta sa 7.
Nabura ko ang paraan sa 6.
Alam ko ligtas na ko magpatuloy down ang 6 path.
Ngunit kailangan kong magpatuloy sa 7 path.
Kaya kung ano ang kailangan kong gawin?
Well, tulad lamang ng dati, kailangan ko lang upang i-clear ang gate, lumabas ng daan,
at bumuo ng isang bagong node mula sa 7 path.
Tulad na lamang ng mga ito.
>> Kaya ngayon ay inilipat ko na 1 at pagkatapos ay 7.
At ngayon paunawa, sort ako ng sa bagong subbranch.
Right.
Lahat ng iba pa mula sa 16 on, Wala akong pakialam tungkol sa.
Hindi ako gumagawa ng 16 kahit ano.
Ako ginagawa 17 mga bagay-bagay.
>> Kaya ngayon mula sa 17 on, kailangan kong uri ng alab bagong trails dito.
Ang susunod na digit aking key ay 0.
Ako malinaw na hindi maaaring makakuha ng kahit saan.
Ko lamang binuo ito node.
Kaya alam ko walang mga landas pasulong mula dito.
Kaya kailangan kong gumawa ng isa sa aking sarili.
>> Kaya malloc ko ang isang bagong node at magkaroon ng 0 point doon.
At pagkatapos ng isa pang oras, malloc ko ang isang bagong node at magkaroon ng isang punto doon.
Muli, naubos ko na ang aking mga susi, 1701.
Kaya tumingin ako at ko spray pintura Yale.
Iyan ang pangalan ng mga ito node.
>> At kaya ngayon kung kailangan ko ba upang makita kung Yale ay sa ito trie, sisimulan ko sa root,
Bababa ako 1701, at tumingin pababa.
At kung makikita ko ang spray Yale pininturahan papunta sa lupa, at pagkatapos ay
Alam ko Yale umiiral sa trie.
Ni gawin ang isa pang Hayaan.
Ni ipasok Dartmouth sa ito Hayaan trie, na kung saan ay itinatag sa 1769.
>> Simulan muli sa root.
Aking unang digit ng aking mga susi ay 1.
Maaari ko ligtas na ilipat pababa na path.
Umiiral Na.
Ang susunod na digit ng aking mga susi ay 7.
Maaari ko ligtas na ilipat pababa na path.
Umiiral na ito pati na rin.
>> Ang aking susunod ay 6.
Mula dito, mula sa kung saan ako kasalukuyang am sa dilaw doon sa gitna na node,
6 ay kasalukuyang naka-lock off.
Kung gusto kong pumunta down na landas, Mayroon akong upang bumuo ng ito sa aking sarili.
Kaya kailangan ko malloc isang bagong node at may 6 point doon.
At pagkatapos ay, muli, ako ay nagliliyab bagong trails dito.
>> Kaya malloc ko ang isang bagong node sa gayon ay mula na node-- path numero 9-- at pagkatapos ay ngayon
kung maglakbay ako 1769, at tumingin ako pababa.
May walang kasalukuyang spray pininturahan doon.
Maaari kong isulat Dartmouth.
At ako nakapasok Dartmouth sa trie.
>> Kaya na pagpasok mga bagay-bagay sa trie.
Ngayon gusto naming upang maghanap para sa mga bagay-bagay.
Paano namin maghanap para sa mga bagay-bagay sa trie?
Well, ito ay medyo marami ang parehong ideya.
Ngayon, gamitin lamang namin ang mga digit ng key upang makita kung kami ay maaaring mag-navigate mula sa mga ugat
na kung saan namin gustong pumunta sa trie.
>> Kung ang hit namin ang isang patay na dulo sa anumang punto, at pagkatapos ay alam natin na hindi maaaring umiiral na elemento
o ibang tao na ang path ng gagawin may na-clear.
Kung gawin namin ito sa lahat ng mga paraan upang Sa katapusan, ang lahat ng kailangan naming gawin
ay tumingin down at makita kung na ang elemento kaming naghahanap para sa.
Kung ito ay, sa tagumpay.
Kung ito ay hindi, mabibigo.
>> Kaya sabihin sa paghahanap para sa Harvard sa trie.
Simulan namin sa root.
At, muli, kami ay pagpunta sa lumikha ng isang traversal pointer
na gawin ang aming mga galaw para sa amin.
Mula sa root alam namin na ang unang lugar na kailangan namin upang pumunta ay 1,
maaari naming gawin iyon?
Oo kaya natin.
Kung ligtas na umiiral na.
Maaari naming pumunta doon.
>> Ngayon, sa susunod na lugar kailangan namin upang pumunta ay 6.
Umiiral ba ang 6 na landas mula dito?
Oo, ito ay.
Maaari naming pumunta down ang 6 path.
At kami end up dito.
>> Puwede ba kaming pumunta down ang 3 landas mula dito?
Well, dahil ito ay lumiliko out, yes, na umiiral masyadong.
At maaari naming makakuha ng sa 6 na landas mula dito?
Oo kaya natin.
>> Hindi namin lubos na nasagot ang pa pinag-uusapan.
Mayroong isa pang pa rin hakbang, na ngayon
kailangan namin upang tumingin down at makita kung na actually--
kung kami ay naghahanap para sa Harvard, ay na ano ang nakita namin matapos naming maubos ang key?
Sa halimbawa na aming ginagamit dito, ang taong palaging apat na digit.
Ngunit maaaring gumagamit ka ng mga halimbawa kung saan ang ikaw ay naglalagay ng isang diksyunaryo ng mga salita.
>> At kaya sa halip ng pagkakaroon ng 10 mga payo para sa aking mga lokasyon, maaari kang magkaroon ng 26.
Isa para sa bawat titik ng alpabeto.
At may ilang mga salita tulad ng paniki, kung saan ay isang subset ng mga batch, halimbawa.
At kaya kahit na ikaw ay makakuha sa dulo ng key at tumingin ka down,
maaaring hindi mo makita kung ano ang ikaw ay naghahanap para sa.
>> Kaya palagi kang magkaroon sa pagtawid ang buong landas at pagkatapos ay
kung kayo ay matagumpay na ma upang tumawid ang buong path,
tumingin down at gawin ang isa huling confirmation.
Ay na kung ano Naghahanap ako?
Well, tumungo ako pagkatapos ng simula sa tuktok at pagpunta 1636.
Tumingin ako pababa.
Nakakakita ako ng Harvard.
Kaya, oo, nagtagumpay ako.
Paano kung ano ako ay naghahanap para sa ay wala sa trie, bagaman.
Paano kung Naghahanap ako ng Princeton, na kung saan ay itinatag sa 1746.
At kaya 1746 ay magiging aking mga susi upang mag-navigate sa pamamagitan ng trie.
Well, sisimulan ko sa root.
At ang unang lugar na gusto ko upang pupunta pababa sa 1 path.
Maaari ko bang gawin ito?
Oo, kaya ko.
>> Puwede ba akong mag down ang 7 landas mula doon?
Oo, maaari ko.
Iyon ay umiiral din.
Ngunit ako maaaring pumunta down ang 4 na landas mula dito?
Iyan ay tulad ng pagtatanong ng mga tanong, maaari Magpatuloy ko down na maliit na parisukat
na ko na naka-highlight sa dilaw?
May walang may.
Right.
>> Walang paraan forward down ang 4 path.
Kung Princeton ay sa ito trie, na ang 4 sana ay na-clear para sa amin na.
At kaya sa puntong ito naabot na namin ang isang patay na dulo.
Hindi namin maaaring pumunta anumang karagdagang.
At upang maaari naming sabihin, definitively, hindi.
Princeton ay hindi umiiral sa trie.
>> Kaya kung ano ang ibig sabihin ng lahat?
Right.
Mayroong maraming nagaganap dito.
May mga payo sa lahat ng dako ng lugar.
At, tulad ng makikita mo lamang mula sa diagram,
may isang pulutong ng mga node na ang mga uri ng lumilipad sa paligid.
Ngunit paunawa sa bawat oras na namin nais na suriin kung ang isang bagay ay sa trie,
lamang kami ay upang gumawa ng 4 na gumagalaw.
>> Sa bawat oras na namin nais na ipasok ang isang bagay sa trie,
mayroon kaming gumawa ng 4 na gumagalaw, marahil ay mallocing ilang mga bagay-bagay kasama ang paraan.
Ngunit tulad ng nakita natin kapag ipinasok namin Dartmouth sa trie,
minsan ang ilan sa mga landas maaaring ma-clear para sa amin.
At sa gayon ay ang aming trie ay makakakuha ng mas malaki at mas malaki, mayroon kaming gawin mas mababa sa trabaho sa bawat oras
upang magpasok ng mga bagong bagay dahil hindi namin nai
na binuo ng isang pulutong ng mga intermediate sanga kasama ang paraan.
Kung sakaling lamang namin upang tumingin sa 4 mga bagay-bagay, 4 ay ang tapat lamang.
Kami ay talagang uri ng papalapit constant insertion oras
at pare-pareho ang oras lookup.
Tradeoff, siyempre, na na ito trie, tulad ng maaari mong marahil sabihin,
ay malaking.
Ang bawat isa sa mga ito nodes tumatagal ng hanggang isang pulutong ng mga puwang.
>> Ngunit iyon ang tradeoff.
Kung gusto namin talagang mabilis insertion, talagang mabilis na pagbura,
at talagang mabilis na paghahanap, kami ay may sa magkaroon ng isang pulutong ng mga data na lumilipad sa paligid.
Mayroon kaming upang magtabi ng isang pulutong ng mga puwang at memory para sa na istraktura ng data
para mabuhay.
>> At kaya na ang tradeoff.
Ngunit mukhang namin maaaring may natagpuan ito.
Maaaring Nakakita kami na banal na Kopita ng mga istraktura ng data
may mabilis na paglalagyan, pagtanggal, at lookup.
At marahil ito ay magiging isang naaangkop na istraktura ng data
upang gamitin para sa kahit anong impormasyon kami ay nagsisikap na store.
Ako Doug Lloyd, ito ay cs50.