[Daqq tal-mużika] Doug LLOYD: Allura aħna kont qed inching eqreb u eqreb li Grail qaddis ta 'data strutturi, wieħed li nistgħu daħħal fis, iħassru minn, u jfittxu up fi żmien kostanti. Dritt. Dik hija tip ta 'l-għan. Aħna rridu li tkun tista 'tagħmel affarijiet ħafna, malajr ħafna. 

Have we sabuha hawn meta aħna qed jitkellem dwar jipprova? Well, ejja tagħti ħarsa. Allura aħna stajt tidher diversi strutturi differenti ta 'data li jimmaniġġjaw l-immappjar ta ' hekk imsejħa pari b'valur ewlenin, immappjar xi biċċa ta 'data għal xi biċċa oħra ta 'data hekk nafu fejn issib informazzjoni fl-istruttura. 

Allura għal firxa, per eżempju, il- muftieħ huwa l-indiċi element jew firxa lokazzjoni 0 jew firxa 1 u l-bqija. U il-valur huwa d-data li teżisti f'dak il-post. Allura dak li hija maħżuna fil-firxa ta '0? Dak hija maħżuna fil-firxa 1 versus biss 0 u 1, li tkun l-keys. 

Ma 'tabella hash huwa tip ta 'l-istess idea. Ma 'tabella hash, aħna għandna dan hash funzjoni li jiġġenera kodiċijiet hash. Allura l-muftieħ huwa l-kodiċi hash tad-data. U l-valur, partikolarment tkellimna dwar ikkatenar fil-video fuq tabelli hash, huwa dik il-lista marbuta tad-data li hashes għal dak hashcode. Dritt. Xi ngħidu dwar approċċ ieħor dan il-metodu, għalkemm? What about metodu fejn il- muftieħ huwa garantit li tkun unika, b'differenza tabella hash, fejn nistgħu jispiċċaw ma 'żewġ biċċiet ta' data jkollhom l-istess hashcode. U allura għandna biex jittrattaw ma ' li minn xi waħda mill probing jew aktar preferibbilment ikkatenar li tiffissa din il-problema. 

Allura issa nistgħu garanzija li ewlieni tagħna se jkun uniku. U jekk dak il-valur tagħna kien biss xi ħaġa faċli kif vera u falza li tgħidilna jekk jew le li l-biċċa ta 'informazzjoni teżisti fl-istruttura? A Boolean tista 'tkun sempliċi bħala daqsxejn. Realistikament huwa probabbilment Byte aktar probabbli minn daqsxejn. Imma dak li ħafna iżgħar minn ħażna forsi string 50-karattru, pereżempju. 

Allura tentattivi, simili għal hash tabelli, li jikkombinaw arrays u lista marbuta, jipprova jikkombinaw arrays, istrutturi, u indikaturi flimkien biex taħżen data mod interessanti li l- pretty differenti minn xejn Rajna s'issa. Issa aħna nużaw l-informazzjoni bħala pjan direzzjonali biex jinnaviga din l-istruttura tad-data. U jekk aħna tista 'ssegwi il-pjan direzzjonali, jekk nistgħu isegwu d-data mill bidu sat-tmiem, aħna ser taf jekk dik id-data jeżistu fil-trie. 

U jekk aħna ma jistgħux isegwu l-mappa minn tifsira sat-tmiem fil-livelli kollha, ma jistax jeżisti d-data. Għal darb'oħra, il-keys hawn huma garantit li jkun uniku. U hekk b'differenza tabella hash, aħna ser qatt ikollhom jittrattaw mal kolliżjonijiet hawn. U l-ebda żewġ biċċiet ta 'data għandhom eżattament l-istess pjan direzzjonali sakemm dik id-data hija identika. 

Jekk aħna daħħal John, allura aħna tfittxija għall John. C'est żewġ biċċiet identiċi ta ' data, id-dritt, aħna qed tfittex permezz. Iżda mod ieħor, kull żewġ biċċiet ta 'data huma garantit li jkollhom pjanijiet direzzjonali uniku permezz ta 'dan struttura tad-data. U aħna qed tmur biex tagħti ħarsa lejn viżwali ta 'dan fi ftit mument. 

Aħna ser tagħmel dan billi tipprova tinħoloq struttura ġdida tad-data, immappjar il-pari b'valur ewlenin li ġejjin. F'dan il-każ, aħna mhux ser tuża xi ħaġa sempliċi bħala Boolean. Aħna fil-fatt se taħżen l-sekwenza. U li string se jkun l-isem ta 'università. 

U l-muftieħ se tkun is-sena meta din l-Università twaqqfet. Snin kollha għall-universitajiet ser ikunu erba 'numri. U hekk aħna ser tuża dawn l-erba ċifri jinnavigaw fil din l-istruttura tad-data. U aħna ser tara, għal darb'oħra, kif nagħmlu li fi ftit tieni. 

Fl-aħħar tal-passaġġ, Ser naraw l-isem tal-università li jikkorrispondi għal dak ewlieni, dawn l-erba 'ċifri. L-idea bażika wara trie hija li għandna rotta ċentrali. Allura taħseb dwarha bħal siġra. U dan huwa simili fl-ortografija u fil-kunċett ma 'siġra. Ġeneralment meta naħsbu dwar siġar fid-dinja reali, dawn ikollhom għeruq li fil- art u huma u jikbru l fuq u dawn għandhom fergħat u dawn ikollha l-weraq. U bażikament l-idea ta a trie huwa eżattament l-istess, ħlief li għeruq huwa ankrat x'imkien fis-sema. U l-weraq huma fil-qiegħ. 

Allura huwa tip simili tieħu siġra u biss flipping rasu 'l isfel. Iżda għad hemm fergħat. U dawk ikun mogħdijiet tagħna, dawn se jkunu konnessjonijiet tagħna mill-għeruq li l-weraq. F'dan il-każ, dawk mogħdijiet, dawn il-friegħi jkollhom it-tikketta ċifri li jgħidulna liema mod biex imorru minn fejn ninsabu. 

Jekk naraw 0, aħna jinżlu din il-fergħa, jekk naraw 1, we jinżlu din il-fergħa, u hekk u hekk. Ukoll, dak li jfisser dan? Ukoll, dan ifisser li f'kull punt junction u kull node fil- nofs u kull fergħa, hemm 10 possibbli postijiet li nistgħu mmorru. Allura hemm 10 pointers minn kull post. 

U dan huwa fejn jipprova tista 'tikseb ftit intimidanti għal xi ħadd Min hu ma għandhom ħafna ta ' esperjenza fix-xjenza tal-kompjuter qabel. Imma jipprova huma verament pjuttost tal-biża. U jekk inti għandek l- opportunità li jaħdmu magħhom u int lest biex ħaffer fil u esperiment magħhom, dawn qed verament pjuttost interessanti strutturi tad-dejta li jaħdmu magħhom. Jekk irridu li daħħal element fil-trie, kollha għandna bżonn tagħmel tinbena l-mogħdija korretta mill-għeruq għall-weraq. Hawn dak li kull pass tul il-mod jista 'dehra. Aħna qed tmur biex jiddefinixxu data ġdida struttura għal node ġdid jissejjaħ trie. 

U ġewwa ta 'dik id-data istruttura hemm żewġ biċċiet. Aħna qed tmur biex jaħżnu l- isem ta 'università. U aħna qed tmur biex jaħżnu firxa ta 'indikaturi fin-nodi oħra tal-istess tip. Allura, għal darb'oħra, dan huwa li tip ta tal-kunċett ta 'kullimkien aħna, aħna fil-10 possibbli postijiet nistgħu mmorru. Jekk naraw 0, aħna jinżlu din il-fergħa. Jekk naraw 1, din il-fergħa, u hekk u hekk u hekk. Jekk aħna ngħidu 9, aħna jinżlu din il-fergħa. Allura f'kull punt junction, nistgħu mmorru 10 postijiet possibbli. Allura kull node għandu jkun fiha 10 pointers fin-nodi oħra, għal 10 punti strateġiċi oħrajn. 

U d-data aħna qed ħażna hija biss l-isem tal-università. Mela ejja jibnu trie. Ejja daħħal koppja ta 'oġġetti fis-trie tagħna. Allura fil-quċċata ħafna, dan huwa node għerq tagħna. Dan huwa probabbilment se tkun xi ħaġa int ser globalment jiddikjaraw. U int ser globalment jżommu a pointer għal dan node dejjem. 

Int ser ngħid, għeruq ugwali, u int ser malloc yourself node trie. U int qatt ser tmissx għerq ġdid. Kull darba li inti tixtieq li tibda navigazzjoni permezz, tissettja pointer ieħor daqs għerq, bħal trav, li huwa l-eżempju I użu f'ħafna videos tiegħi hawn fuq stacks u kjuwijiet u listi rabta u l-bqija. 

Tissettja pointer ieħor sejjaħ trav għall traversal. U inti tuża trav biex jinnaviga permezz tal-istruttura tad-data. Mela ejja ara kif dan tista 'tidher. Allura issa dritt, liema ma node look like? Ukoll, biss bħala data tagħna dikjarazzjoni istruttura indikat, għandna string, li f'dan il-każ ikun vojt. M'hemm xejn hawn. 

U l-firxa ta '10 pointers. U d-dritt issa, aħna biss ikollha 1 node f'dan trie. M'hemm xejn fiha. Allura kollha 10 ta 'dawk pointers minn punt tkun tista null. Dak hu l-aħmar jindika. 

Ejja daħħal l-sekwenza Harvard. Ejja daħħal l-Università ta ' Harvard fis dan trie, li twaqqfet fis-sena 1636. Aħna rridu li jużaw l-ewlenin, 1636, biex tgħidilna fejn aħna qed ser taħżen Harvard fil-trie. Issa, kif jista 'nagħmlu dan? 

Hija tista 'tidher xi ħaġa bħal din. Nibdew fl-għeruq. U aħna għandna dawn l-10 postijiet nistgħu mmorru. L-għerq huwa biss bħal kull node oħra tal-trie. Hemm 10 postijiet nistgħu mmorru minn hawn. 

Fejn do we probabilment tixtieq biex imorru jekk il-muftieħ huwa 1636? Hemm verament żewġ għażliet. Dritt. Nistgħu nibnu ċ-ċavetta minn lemin għax-xellug u tibda bl 6. Jew nistgħu nibnu l-muftieħ mill xellug għal-lemin u tibda bil 1. 

Huwa probabbilment aktar intuwittivi bħala bniedem biex jifhmu aħna ser Just go xellug għal-lemin. U hekk jekk irrid li daħħal Harvard fis dan trie, I probabbilment jridu jibdew billi jibda mid-għeruq, tħares lejn 10 għażliet tiegħi quddiem lili, u qal Irrid immur fit-triq 1. KOLLOX SEW. 

Issa, 1 passaġġ bħalissa null. Mela jekk jien tixtieq li tipproċedi isfel f'din it-triq li daħħal dan l-element fil-trie, I għandhom malloc node ġdid, għandhom 1 punt hemmhekk, u mbagħad jien tajba biex tmur. 

So I bażikament am fi punt fejn jien wieqfa l-għerq tal-siġra jew l trie u hemm 10 fergħat. Iżda kull fergħa għandha xatba quddiem ta 'dan. Dritt. Għaliex hemm xejn hemmhekk. L Nru passaġġ mingħajr periklu. Dan ifisser li hemm xejn l-ebda minn dawk il-friegħi. Jekk nixtieq li jibdew bini xi ħaġa, I tixtieq li tneħħi l-bieb. I tixtieq li tneħħi l-bieb quddiem numru 1. U nixtieq li jimxu dan. U nixtieq li jibnu post ieħor għalija li jmorru. 

U dan huwa dak I ghamilt hawn. Allura 1 ma jipponta lejn null. Stajt qal li huwa tajjeb li jinżlu hawn issa. I mibnija node ieħor. U meta niġi biex dik node, I jkollhom deċiżjoni oħra li jagħmlu. Fejn am I se jmorru minn hawn? 

Well, stajt diġà niżlu 1. Allura issa I probabilment tixtieq li jinżlu 6. Dritt. Għal darb'oħra, I jkollhom 10 postijiet I tista 'tagħżel. Mela ejja issa jinżlu numru 6. So I ċar l-gate quddiem numru 6. U I walk stabbiliti hemmhekk. U jien jibnu node ieħor. U stajt laħqu punt junction ieħor. 

Għal darb'oħra, I jkollhom 10 għażliet għall fejn I tista 'tmur. Stajt mċaqalqa 1-6. Allura issa I probabilment tixtieq li tmur sa 3. 3, hemm imkien I tista 'tmur. So I jkollhom ċar li l-mod u jibnu myself spazju ġdid. U mbagħad minn 3, fejn ma nixtieq li jmorru? Irrid li jinżlu 6. 

U, għal darb'oħra, I kellhom ċar il-mod kif tagħmel dan. Allura issa stajt użati ewlieni tiegħi biex tiddaħħal joħolqu lymph u jibdew jibnu dan trie. Stajt beda fl-għeruq. Stajt marret isfel 1636. U issa jien fil-qiegħ hemm fuq dik node. U inti tista 'tkun kapaċi tara fuq l-iskrin tiegħek. 

Huwa enfasizzat bl-isfar. Li meta I bħalissa am. Muftieħ My isir. Stajt eżawriti kull pożizzjoni fl-iskema tiegħi. So I ma tistax tmur aktar. Allura f'dan il-punt, I kollha verament bżonn tagħmel hu li jgħidu, OK. Huwa tip ta 'bħal tfittex stabbiliti fuq l-art, jekk int jaħseb lilek innifsek bħala dan it-tip ta 'triq b'konnessjonijiet differenti. Tip ta 'tfittex l isfel u tip ta' sprej pittura Harvard fuq l-art. Dik hija l-isem ta 'dan. Kun af dak hu l fuq dan il-post. Jekk nibdew fil-għerq u aħna jinżlu 1 u mbagħad 6 u mbagħad 3 u mbagħad 6, fejn ninsabu? Ukoll jekk inħarsu l isfel u naraw Harvard, allura nafu li Harvard kien imwaqqfa fl 1636 ibbażata fuq il-mod aħna qed timplimenta din l-istruttura tad-data. Allura li kien nisperaw sempliċi. Aħna qed tmur biex tagħmel żewġ inserzjonijiet aktar. U wieħed jittama li ser tgħin biex tara dan isir darbtejn aktar. 

Issa, ejja daħħal università oħra. Ejja daħħal Yale fis dan trie. Yale twaqqfet fl 1701. Allura aħna ser tibda fil- għerq, kif aħna dejjem do. U waqqafna pointer traversal. Aħna qed tmur għall-użu li jimxu permezz. L-ewwel ħaġa li rridu tagħmel hu li tmur fit-triq 1. Dik hija l-ewwel numru ta 'ċavetta tagħna. Fortunatament, għalkemm, aħna ma għandek tagħmel xi xogħol f'dan il-ħin. Il-passaġġ 1 tkun diġà ġiet ikklerjata. I approvat it preċedentement meta I kien ddaħħal Harvard fl 1636. So I jistgħu b'sigurtà jiċċaqalqu down 1 u biss jmorru hemm. Jekk tista 'timxi l-1. 

Issa, għalkemm, nixtieq li jmorru sa 7. I kklerjat l-mod ta '6. I know I jistgħu b'sigurtà jipproċedi fit-triq 6. Imma I bżonn li tipproċedi fuq il-passaġġ 7. Mela xi do I bżonn tagħmel? Ukoll, bħad qabel, I biss bżonn ċar li l-gate, toħroġ il-mod, u jibnu node ġdid mill-mogħdija 7. Eżatt bħal din. 

Allura issa stajt mċaqalqa 1 u mbagħad 7. U issa avviż, jien sort ta 'fuq din Subbranch ġdid. Dritt. Kollox mill-16 ta ' fuq, jien ma care about. Jien ma tagħmel 16 xejn. Li qed nagħmel 17 Jittieħed. 

Allura issa minn 17 dwar, I għandhom tip ta 'blaze trails ġodda hawn. Il ċifri jmiss muftieħ tiegħi huwa ta '0. I ċertament ma tistax tikseb kullimkien. I biss mibnija din node. So I know hemm l-ebda mogħdijiet quddiem minn hawn. So I għandhom jagħmlu waħda myself. 

So I malloc a node ġdid u jkollhom 0 punt hemmhekk. U mbagħad waħda aktar ħin, I malloc a node ġdid u jkollu punt wieħed hemmhekk. Għal darb'oħra, stajt eżawriti ewlieni tiegħi, 1701. So I tfittex l isfel u I isprej taż-żebgħa Yale. Dik hija l-isem ta 'dan node. 

U hekk issa jekk I qatt bżonn biex tara jekk Yale huwa f'dan trie, I tibda fil-għeruq, I jinżlu 1701, u tfittex l isfel. U jekk nara isprej Yale miżbugħa fuq l-art, imbagħad Naf Yale teżisti f'dan trie. Ejja nagħmlu waħda aktar. Ejja daħħal Dartmouth fis dan trie, li twaqqfet fl-1769. 

Ibda fl-għerq ġdid. Ewwel ċifra tiegħi ta 'ċavetta tiegħi huwa 1. I jistgħu b'sigurtà jinżel f'din it-triq. Li diġà teżisti. Il ċifri jmiss tal ċavetta tiegħi hija ta '7. I jistgħu b'sigurtà jinżel f'din it-triq. Jeżisti wkoll. 

My jmiss huwa 6. Minn hawn, minn fejn I am bħalissa bl-isfar hemm f'dak node tan-nofs, 6 bħalissa huwa maqful off. Jekk irrid li jinżlu f'din it-triq, Għandi biex tinbena myself. So I ser malloc a node ġdid u jkollhom 6. punt hemmhekk. U mbagħad, għal darb'oħra, jien tisreġ trails ġodda hawn. 

So I malloc node ġdid sabiex min dak in-numru passaġġ node-- 9-- u mbagħad issa jekk I-ivvjaġġar 1769, u I tfittex l isfel. M'hemm xejn bħalissa sprej miżbugħa hemm. Kapaċi nikteb Dartmouth. U stajt jiddaħħal Dartmouth fil-trie. 

Allura dak li ddaħħal affarijiet fil-trie. Issa rridu li tfittxija għal affarijiet. Kif nistgħu tfittxija għal affarijiet fil-trie? Ukoll, huwa pjuttost l-istess idea. Issa aħna biss jużaw l-ċifri tal-ċavetta biex tara jekk nistgħu jinnavigaw mill-għeruq fejn irridu imorru fil-trie. 

Jekk aħna hit tmiem mejta fi kwalunkwe punt, imbagħad nafu li dan l-element ma jistax jeżisti jew inkella dik it-triq se diġà ġew approvati. Jekk nagħmlu dan il-mod kollu li l-aħħar, kollha għandna bżonn tagħmel huwa tfittex l isfel u tara jekk dan huwa l-element aħna qed tfittex. Jekk huwa, suċċess. Jekk mhuwiex, jonqsu. 

Mela ejja tfittxija għal Harvard f'dan trie. Nibdew fl-għeruq. U, għal darb'oħra, aħna qed tmur biex joħolqu pointer traversal tagħmel jiċċaqlaq tagħna għalina. Mill-għeruq nafu li l- ewwel post għandna bżonn immorru huwa 1, nistgħu nagħmlu dan? Iva, nistgħu. Jekk teżisti mingħajr periklu. Aħna tista 'tmur hemm. 

Issa, il-post li jmiss għandna bżonn immorru huwa 6. Il-passaġġ 6 jeżistu minn hawn? Yeah, ma. Aħna tista 'tmur fit-triq 6. U aħna jispiċċaw hawn. 

Nistgħu jinżlu 3 passaġġ minn hawn? Ukoll, kif jirriżulta, iva, li teżisti wisq. U nistgħu tikseb fuq il-6 passaġġ minn hawn? Iva, nistgħu. 

Aħna ma pjuttost imwieġba il-kwistjoni għadu. Hemm għadu wieħed aktar pass, li issa huwa għandna bżonn li tfittex l isfel u tara jekk dan huwa actually-- jekk aħna qed infittxu Harvard, huwa li dak li nsibu wara we jeżawrixxi d ċavetta? Fl-eżempju aħna qed jużaw hawn, is-snin huma dejjem erba 'numri. Iżda int tista 'tuża l-eżempju fejn inti qed jaħżnu dizzjunarju ta 'kliem. 

U għalhekk minflok li 10 pointers għall-lokazzjoni tiegħi, inti jista 'jkollok 26. Wieħed għal kull ittra tal-alfabett. U hemm xi kliem bħal BAT, li hu subsett ta 'lott, per eżempju. U hekk anke jekk ikollok il- aħħar tas-ċavetta u inti tfittex l isfel, inti tista 'ma tara dak inti qed tfittex. 

Allura inti dejjem ikollhom biex travers il-passaġġ kollu u mbagħad jekk inti kienu kapaċi b'suċċess travers il-passaġġ kollu, tfittex l isfel u jagħmlu konferma finali wieħed. Hija li dak li jien tfittex? Well, I tfittex l isfel wara li tibda fil-quċċata u jmorru 1636. I tfittex l isfel. Nara Harvard. Allura, iva, I irnexxielu. X'jiġri jekk dak I infittex mhuwiex fil-trie, għalkemm. X'jiġri jekk I infittex Princeton, li twaqqfet fl 1746. U hekk 1746 isir ewlenin tiegħi li jinnavigaw fil-trie. Well, I tibda fil-għerq. U l-ewwel post nixtieq li tmur fit-triq 1. Nista 'nagħmel dan? Iva, nista '. 

Nista jinżlu 7 triq minn hemm? Yeah, I jistgħu. Li teżisti wisq. Imma nista 'mmur l-4 triq minn hawn? Dik hija simili tistaqsi l-mistoqsija, jista I jipproċedi isfel li ftit kwadru li stajt enfasizzat bl-isfar? M'hemm xejn hemmhekk. Dritt. 

M'hemm l-ebda triq 'il quddiem fit-triq 4. Jekk Princeton kien f'dan trie, li 4 kien ikun approvat għalina diġà. U hekk f'dan il-punt konna laħaq tmiem mejta. Aħna ma tistax tmur aktar. U hekk nistgħu ngħidu, b'mod definittiv, ebda. Princeton ma jeżistix f'dan il-trie. 

Allura dak li jfisser dan kollu jfisser? Dritt. Hemm ħafna jiġri hawn fuq. Hemm indikaturi kollha fuq il-post. U, kif tistgħu taraw biss mid-dijagramma, hemm ħafna ta 'punti ta' konġunzjoni li huma tip ta 'jtajru madwar. Iżda avviż kull darba li ridna tivverifika jekk xi ħaġa kienet fil-trie, aħna biss kellhom jagħmlu 4 jiċċaqlaq. 

Kull darba ridna daħħal xi ħaġa fil-trie, irridu nkunu 4 jiċċaqlaq, possibilment mallocing xi għalf matul it-triq. Imma kif rajna meta aħna inserit Dartmouth fil-trie, kultant xi wħud mill-passaġġ Wieħed diġà jista kklerjati għalina. U hekk kif trie tagħna tkompli tikber u akbar, għandna nagħmlu inqas xogħol kull darba li daħħal affarijiet ġodda għaliex aħna ħadthom diġà mibnija ħafna tas-sustanza intermedja fergħat tul it-triq. Jekk aħna biss qatt tħares lejn 4 affarijiet, 4 huwa biss kostanti. Aħna verament huma tip ta 'toqrob inserzjoni ħin kostanti u lookup ħin kostanti. Il tradeoff, naturalment, hija li dan trie, kif inti tista 'probabbilment tgħid, huwa enormi. Kull waħda minn dawn in-nodi jieħu ħafna spazju. 

Imma dak li l-tradeoff. Jekk irridu tassew mgħaġġla inserzjoni, tħassir tassew mgħaġġla, u lookup tassew mgħaġġla, irridu għandhom ħafna ta 'data jtajru madwar. Irridu twarrab ħafna spazju u l-memorja għal dik l-istruttura tad-data jeżistu. 

U għalhekk dak l-tradeoff. Iżda jidher qisu aħna jista sabuha. Aħna jista sabu li Grail qaddis ta 'strutturi ta' dejta ma inserzjoni malajr, tħassir, u Lookup. U forsi dan se jkun istruttura xierqa data għall-użu għal kwalunkwe informazzjoni aħna qed jippruvaw biex jaħżnu. Jien Doug Lloyd, dan huwa CS50.