>> [Muzikos grojimo]
Doug LLOYD: Taigi mes jau pamažu virsta arčiau ir arčiau, kad Gralis duomenų
struktūros, vienas, kad mes galime įterpti į, ištrinti iš, ir ieškoti
nuolat laiko.
Teisė.
Štai tarsi į vartus.
Mes norime, kad būtų galima daryti viskas labai, labai greitai.
>> Ar mes ją radau čia, kai mes kalbame apie bando?
Na, leiskite pažvelgti.
Taigi mes matėme keletą įvairios duomenų struktūros
kad rankena žemėlapių taip vadinamas raktas-reikšmės poros,
kartografavimo kai duomenų gabalas su kitokiu gabalas duomenų
todėl mes žinome, kur rasti informacija į struktūrą.
>> Taigi, masyvą, pavyzdžiui, Svarbiausia yra elementas indeksas arba masyvo
vietą 0 arba 1 masyvas ir taip toliau.
Ir yra, vertės nėra duomenų kad egzistuoja toje vietoje.
Taigi, kas yra saugomi masyve 0?
Kas yra saugomi masyve 1 prieš tiesiog 0, o 1, kuris būtų raktai.
>> Su maišos lentelė tai Rūšiuoti tos pačios idėjos.
Su maišos lentelė, mes turime šį maišos funkcija, kuri generuoja maišos kodai.
Taigi raktas yra maišos kodą iš duomenų.
Ir vertę, ypač mes kalbėjome apie Grupavimo
Kai dėl maišos lentelėmis vaizdo, yra tai, kad susijęs sąrašą duomenų
kad maišos tos hashCode.
Teisė.
Ką apie kitą metodą šis metodas, nors?
Ką apie metodu, kai raktas garantuoja, kad bus unikalus,
skirtingai nuo maišos lentelė, kur mes galėtume galų gale su dviem gabaliukais duomenis
turintys tą patį hashCode.
Ir tada mes turime elgtis su , kad vienos ar daugiau zondavimo
pageidautina Grupavimo nustatyti šią problemą.
>> Taigi, dabar mes galime garantuoti kad mūsų raktas bus unikalus.
Ir ką daryti, jei mūsų vertė buvo tiesiog kažkas taip paprasta,
kaip teisinga ir neteisinga, kad pasakoja, ar ar ne todėl, kad gabalas informacijos
egzistuoja struktūros?
Loginius operatorius gali būti taip paprasta, kaip šiek tiek.
Realiai tai tikriausiai BYTE labiau nei truputį.
Bet tai daug mažesnis nei saugoti gal 50-simbolių,
pavyzdžiui.
>> Taigi bando, panašūs į maišos lenteles, kuri sujungia matricas ir susiję sąrašas
bando sujungti matricos, struktūros, o patarimų
kartu saugoti duomenis įdomus būdas tai
gana skiriasi nuo ką mes matėme iki šiol.
Dabar mes naudojame informaciją, kaip plano naršyti šiuos duomenis struktūrą.
Ir jei mes galime stebėti veiksmų planas, jei mes galime
sekti duomenis iš pradžios iki pabaigos, mes
žinoti, ar tais duomenimis egzistuoja TRIE.
>> Ir jei mes negalime sekti žemėlapį nuo ty baigti ne visi,
duomenys gali neegzistuoja.
Vėlgi, raktai čia yra garantuoja, kad bus unikalus.
Ir taip skirtingai maišos lentelės, mes niekada tenka susidurti su susidūrimų čia.
Ir ne du gabalai duomenis turi lygiai tą patį planą
išskyrus atvejus, kai duomenys yra identiški.
>> Jei mes įterpti Joną, tada mes ieškome Jono.
Štai du identiški gabalus duomenys, tiesa, mes ieškome per.
Bet kitaip, bet koks dviejų dalių duomenys
garantuoja, kad turi unikalią planus per šios duomenų struktūros.
Ir mes ketiname pažvelgti vizualiai tai vos akimirką.
>> Mes tai padaryti bando sukurti naują duomenų struktūrą,
kartografavimo šiuos pagrindinius vertės poras.
Tokiu atveju, mes neketiname naudoti kažkas taip paprasta, kaip Būlio.
Mes iš tikrųjų bus saugomi eilutę.
Ir tai styginių ketina būti universiteto pavadinimą.
>> Ir svarbiausia bus metai kai buvo įkurta, kad universitetų.
Visi universitetams metų ketina sudaryti keturi skaitmenys.
Ir todėl mes naudosime tuos keturis skaitmenis į naršyti šios duomenų struktūros.
Ir mes pamatysime, vėlgi, kaip mes darome, kad vos per sekundę.
>> Tuo kelio pabaigoje, matysime pavadinimą
Universiteto, kuris atitinka į šį raktą, šie keturi skaitmenys.
Pagrindinė idėja yra TRIE yra mes turime pagrindinį maršrutą.
Taigi apie tai galvoti kaip medis.
Ir tai yra panašios rašymo ir koncepcijos iki medį.
Paprastai, kai mes galvojame apie medžiai ir realiame pasaulyje,
jie turi šaknį, kad yra į žemės ir jie auga aukštyn
ir jie turi filialus ir jie turi lapus.
Ir iš esmės yra idėja Trie yra lygiai tas pats,
išskyrus tai, kad šaknys yra įtvirtinta kažkur danguje.
Ir lapai yra apačioje.
>> Taigi, tai lyg atsižvelgiant į medį ir tiesiog prakeiktas jis aukštyn kojom.
Tačiau vis dar yra filialai.
Ir tie būtų mūsų keliai, tie bus mūsų jungtys
nuo iki lapų šaknis.
Šiuo atveju, tie, takai, šie filialai
yra paženklintos skaitmenų kad pasakys mus kuriuo keliu eiti iš kur mes esame.
>> Jei mes matome 0, mes eiti šio filialo, jei matome 1, mes eiti šio filialo,
ir taip ir taip toliau.
Na, ką tai reiškia?
Na, tai reiškia, kad kiekviename sankryžos taško
ir kiekvienas mazgas viduryje ir kiekvieną filialas,
Yra 10 galima vietos, kad mes galime eiti.
Taigi yra 10 patarimų iš kiekvienos vietos.
>> Ir tai, kai bando galite gauti šiek tiek bauginanti kažkam
kas neturi daug patirtis kompiuterių mokslo anksčiau.
Bet bando tikrai gana awesome.
Ir jei jūs turite galimybė dirbti su jais
ir jūs esate pasirengę kasti-in ir eksperimentuoti su jais,
jie tikrai gana įdomi duomenų struktūros dirbti.
Jei norime įterpti elementą į TRIE, visi mes turime daryti
yra sukurti teisingą kelią iš į lapų šaknų.
Štai ką kiekvienas žingsnis kartu būdas gali atrodyti.
Mes ketiname nustatyti naują duomenų struktūra naują mazgo vadinamas TRIE.
>> Ir viduje, kad duomenys struktūra yra du gabalai.
Mes ketiname saugoti Pavadinimas universitete.
Ir mes ketiname saugoti AN nurodymus masyvo
kitų mazgų to paties tipo.
Taigi, vėl, tai yra tai, kad rūšiuoti nuo koncepcijos visur
mes esame, mes ne 10 galima vietos, mes galime eiti.
Jei mes matome 0, mes eiti šiuo filialą.
Jei mes matome 1, tai filialas, ir taip toliau, ir taip toliau, ir taip toliau.
Jei mes sakome, 9, mes eiti šiuo filialą.
Taigi kiekviename sandūros taške, mes galime eiti 10 galimų vietų.
Taigi kiekvienas mazgas turi būti 10 patarimų kitų mazgų, daugiau kaip 10 kitų mazgų.
>> Ir duomenys mes saugoti yra Tiesiog universiteto pavadinimą.
Taigi leiskite statyti TRIE.
Leiskite įdėti pora daiktų į mūsų TRIE.
Taigi pačiame viršuje, tai yra mūsų šaknys mazgas.
Tai turbūt bus kažkas jūs ketinate globaliai skelbiame.
Ir jūs ketinate globaliai išlaikyti rodyklė į šį mazgą visada.
>> Jūs ketinate pasakyti, šaknis lygi, ir jūs
ketina malloc sau TRIE mazgas.
Ir jūs niekada vėl paliesti šaknis.
Kiekvieną kartą, kai norite pradėti naršyti,
galite nustatyti kitą rodyklę lygus šaknis, pavyzdžiui, Trav,
kuris yra pavyzdys, naudoti daugelis mano video
čia kaminai ir eilėse ir nuoroda sąrašai ir pan.
>> Jūs nustatote vieną žymiklį vadinamas Trav už Sankryþos.
Ir jūs naudojate Trav naršyti per duomenų struktūra.
Taigi pažiūrėkime, kaip tai gali atrodyti.
Taigi dabar, ką Ar mazgas atrodo?
Na, kaip mūsų duomenų struktūra deklaracija nurodė,
turime eilutę, kuri šiuo atveju yra tuščias.
Nėra nieko čia.
>> Ir po 10 patarimų masyvo.
Ir dabar, mes tik Turiu 1 mazgas šiame TRIE.
Nėra nieko dar jame.
Taigi visi tie 10 rodyklės taškas į NULL.
Štai ką raudona rodo.
>> Leiskite įterpti eilutę Harvardo.
Leiskite įrašyti universitetas Harvardo į šį TRIE, kuris
buvo įkurta metų 1636.
Mes norime naudoti raktą, 1636, pasakyti mums, kur mes
ketina laikyti Harvardo į TRIE.
Dabar, kaip gali mes tai darome?
>> Tai gali atrodyti kažką panašaus į tai.
Mes pradedame šaknis.
Ir mes turime šiuos 10 vietų, mes galime eiti.
Šaknis yra kaip bet kuris kitas mazgas TRIE.
Yra 10 vietų, mes galime eiti iš čia.
>> Kur mes tikriausiai nori eiti, jei raktas yra 1636?
Yra tikrai du variantai.
Teisė.
Galime pastatyti nuo raktą iš dešinės į kairę ir pradėti su 6.
Arba mes galime sukurti iš raktą į kairę į dešinę ir pradėti 1 d.
>> Tai tikriausiai daugiau intuityvi kaip žmogus
Mes suprantame, kad bus Tiesiog eikite į kairę į dešinę.
Ir taip, jei noriu įterpti Harvardo į šį TRIE,
Aš tikriausiai norite pradėti pradedant šaknis,
žiūri mano 10 variantų priešais mane, ir sako:
Noriu eiti į 1 keliu.
GERAI.
>> Dabar, 1 kelias šiuo metu yra tuščias.
Taigi, jei aš noriu tęsti šiuo keliu įterpti šį elementą į TRIE,
Turiu malloc naują mazgas, turime 1 ten rodo, o tada aš gerai eiti.
>> Taigi aš iš esmės esu ne vieta, kur aš stoviu
tuo medžio arba iš šaknies Trie ir yra 10 skyriai.
Bet kiekvienas filialas turi vartai priešais jį.
Teisė.
Nes ten nieko nėra.
Nėra saugų.
Tai reiškia, kad ten nieko žemyn nors iš šių šakų.
Jei aš noriu pradėti statyti kažkas, aš noriu pašalinti vartai.
Noriu pašalinti vartai priešais skaičius 1.
Ir aš noriu vaikščioti žemyn, kad.
Ir aš noriu statyti kita man kur eiti.
>> Ir tai, ką aš padariau čia.
Taigi 1 nebėra nurodo null.
Sakiau tai saugu eiti čia dabar.
Aš pastatyti dar vieną mazgą.
Ir kai aš gauti tą mazgą, aš turi kitą sprendimą padaryti.
Kur aš ketinu eiti nuo čia?
>> Na, aš jau sumažėjo 1.
Taigi, dabar aš tikriausiai norite eiti į 6 d.
Teisė.
Vėlgi, aš turiu 10 vietas galiu rinktis.
Taigi leiskite dabar eiti numeriu 6.
Taigi aš išvalyti vartai priešais numeriu 6.
Ir aš vaikščioti ten.
Ir aš statyti dar mazgas.
Ir aš pasiekė kitą sankryžos tašką.
>> Vėlgi, aš turiu 10 pasirinkimus o kur aš galiu eiti.
Aš persikėlė nuo 1 iki 6.
Taigi, dabar aš tikriausiai norite eiti į 3 dalis.
3, ten kur aš galiu eiti.
Taigi turiu išvalyti kelią ir kurti sau naują erdvę.
Ir tada iš 3, kur aš noriu eiti?
Noriu eiti 6.
>> Ir vėl, aš turėjau išvalyti kelią tai padaryti.
Taigi, dabar aš naudojamas mano klavišą įterpti sukurti mazgai ir pradėti statyti TRIE.
Aš pradėjau šaknis.
Aš sumažėjo 1636.
Ir dabar aš apačioje ten tą mazgą.
Ir jums gali būti suteikta galimybė matyti ekrane.
>> Jis pabrėžė, geltonos spalvos.
Štai kur aš šiuo metu esu.
Mano pagrindinė daroma.
Aš išnaudojo kiekvieną poziciją mano raktu.
Taigi aš negaliu eiti toliau.
Taigi šiuo metu, viskas, ką aš tikrai reikia padaryti, tai pasakyti, Gerai.
Tai lyg ieškote žemyn į žemę,
jei jūs vizijos Būk kaip šio kelio rūšiuoti
su skirtingų jungčių.
Rūšiuoti žiūri ir tarsi Dažymas purkštuvu, Harvardo ant žemės.
Štai šiuo vardu.
Žinokite, kad tai, kas šioje vietoje.
Jei pradėsime šaknis ir mes eiti 1 ir tada 6 ir tada 3 ir tada 6,
Kur mes esame?
Na, jei mes žiūrime žemyn ir matome Harvardo, tada
mes žinome, kad Harvardo buvo įkurta 1636 remiasi būdu
mes įgyvendinti šiuos duomenis struktūrą.
Taigi, tai buvo tikiuosi paprasta.
Mes ketiname padaryti du intarpais.
Ir tikiuosi, kad bus padėti pamatyti tai padaryti du kartus daugiau.
>> Dabar galime įterpti kitą universitetą.
Leiskite įdėti į šį Yale TRIE.
Yale "buvo įkurta 1701 m.
Taigi mes pradėsime ne šaknis, kaip mes visada darome.
Ir mes nustatyti Sankryþos žymeklį.
Mes ketiname naudoti, kad pereiti per.
Pirmas dalykas, mes norime padaryti, tai eiti į 1 keliu.
Štai pirmas skaitmuo mūsų raktu.
Laimei, nors mes ne daryti bet kokį darbą šį kartą.
1 m kelias jau buvo išvalytas.
Aš vartų anksčiau, kai aš buvo įterpiant Harvardo 1636.
Taigi aš galiu saugiai judėti žemyn 1 ir tiesiog eiti ten.
Jei gali judėti žemyn 1 d.
>> Dabar, nors, aš noriu eiti į 7.
Aš atvėręs kelią po 6.
Žinau, kad galiu saugiai pereiti žemyn 6 kelią.
Bet man reikia pradėti nuo 7 keliu.
Taigi, ką man reikia daryti?
Na, kaip ir anksčiau, aš tiesiog reikia išvalyti vartai, gauti iš kelio,
ir kurti naują mazgą iš 7 keliu.
Tiesiog, kaip šis.
>> Taigi dabar aš persikėlė 1 ir tada 7.
Ir dabar pastebėsite, aš rūšiuoti dėl šios naujos subbranch.
Teisė.
Visa kita nuo 16 , aš nerūpi.
Aš nesu daro 16 nieko.
Darau 17 stuff.
>> Taigi dabar nuo 17, aš turiu rūšiuoti naujų būdų čia.
Kitas skaitmenų mano raktas yra 0.
Aš aiškiai negali gauti bet kur.
Aš tiesiog pastatė šį mazgą.
Taigi aš žinau, nėra keliai į priekį nuo čia.
Taigi turiu padaryti vieną save.
>> Taigi aš malloc naują mazgas ir turi 0 balų ten.
Ir tada dar kartą, aš malloc Naujas mazgas ir turi vieną tašką ten.
Vėlgi, aš išnaudojo savo raktą, 1701.
Taigi man atrodo, ir aš dažų purkštuvu Yale.
Štai šio mazgo vardas.
>> Ir todėl dabar, jei aš kada nors reikės pamatyti, jei Yale yra šiame TRIE, aš pradedu tuo šaknis,
Aš eiti 1701 ir žiūrėti žemyn.
Ir jei matau Yale purkštuvą dažyti ant žemės, tada
Žinau Jeilio egzistuoja šiame TRIE.
Padarykim dar vieną.
Leiskite įdėkite Dartmouth į tai Trie, kuri buvo įkurta 1769 m.
>> Prasideda šaknies iš naujo.
Mano pirmasis skaitmuo mano raktas yra 1.
Galiu drąsiai judėti šiuo keliu.
Tai jau egzistuoja.
Kitas skaitmuo mano raktas yra 7.
Galiu drąsiai judėti šiuo keliu.
Ji egzistuoja, taip pat.
>> Mano šalia yra 6.
Iš čia, iš kur aš esu šiuo metu geltonai ten toje vidurinėje mazgas,
6 šiuo metu yra užrakinta išjungtas.
Jei aš noriu eiti šiuo keliu, Turiu ją kurti save.
Taigi aš malloc naują mazgas ir turi 6 punktas ten.
Ir tada vėl, aš Blazing naujų takai čia.
>> Taigi aš malloc naują mazgą taip, kad iš kad node-- kelio numeris 9-- ir tada dabar
jei aš keliauti 1769 ir žiūriu žemyn.
Nėra nieko šiuo metu purkšti ten dažytos.
Gebu rašyti Dartmouth.
Ir aš įterpti Dartmouth į TRIE.
>> Taigi, kad įterpiant viskas į TRIE.
Dabar mes norime ieškoti dalykų.
Kaip mes ieškoti dalykų TRIE?
Na, tai beveik tas pats idėja.
Dabar mes tiesiog naudoti rakto skaitmenų pamatyti, jei mes galime naršyti nuo šaknų
kur mes norime eiti į TRIE.
>> Jei mes paspauskite aklavietę bet kuriame taške, tada mes žinome, kad šis elementas negali egzistuoja
arba kita, kad planas būtų jau buvo pašalinta.
Jei mes padarysime tai visą kelią į pabaiga, viskas, ką reikia padaryti,
tai pažvelgti ir pamatyti, jei tai elementas mes ieškome.
Jei taip, tai sėkmės.
Jei taip nėra, nepavyks.
>> Taigi leiskite ieškoti Harvardo šiame TRIE.
Mes pradedame šaknis.
Ir, vėlgi, mes ketiname sukurti Sankryþos žymiklį
padaryti mūsų juda už mus.
Nuo šaknų mes žinome, kad Pirmoji vieta turime eiti yra 1,
mes galime padaryti, kad?
Taip, mes galime.
Jei saugiai egzistuoja.
Mes galime eiti ten.
>> Dabar, kitą vietą turime eiti yra 6.
Ar 6 kelias egzistuoja iš čia?
Taip, tai daro.
Mes galime eiti į 6 kelią.
Ir mes galų gale čia.
>> Ar mes galime eiti į 3 kelio nuo čia?
Na, kaip it turns out, Taip, kad egzistuoja per daug.
Ir mes galime gauti apie 6 kelio nuo čia?
Taip, mes galime.
>> Mes ne visai atsakė klausimas dar.
Yra dar viena daugiau žingsnis, kuris yra dabar
mes turime pažvelgti žemyn ir pamatyti, jei tai actually--
jei mes ieškome Harvardo, yra tai, kad Ką mes randame, kai mes išnaudoti raktą?
Pavyzdyje mes naudojame čia metams visada keturi skaitmenys.
Tačiau jums gali būti naudojant pavyzdžiui, kai Jūs saugoti žodžių žodyną.
>> Ir taip užuot 10 patarimų mano vietą, galite turėti 26.
Vienas kiekvienos abėcėlės raidės.
Ir ten yra keletas, kaip šikšnosparnių žodžiai kuris yra partijos poaibis, pavyzdžiui.
Ir net jei jūs gaunate į pabaiga raktą ir jums pažvelgti žemyn,
galbūt nematote, ką Jūs ieškote.
>> Taigi jūs visada turite feed visą kelią ir tada
jei buvo sėkmingai galėtų feed visą kelią,
žiūrėti žemyn ir padaryti vieną galutinį patvirtinimą.
Ar tai, ką aš ieškote?
Na, aš pažvelgti žemyn pradėjus viršuje ir vyksta 1636.
Žiūriu žemyn.
Matau Harvardo.
Taigi, taip, man pavyko.
Ką daryti, jei aš ko yra ne TRIE, nors.
Ką daryti, jei aš ieškau Princeton, kuri buvo įkurta 1746 m.
Ir taip 1746 tampa mano raktas naršyti TRIE.
Na, aš pradedu tuo šaknis.
Ir pirmoji vieta Noriu į krinta 1 keliu.
Ar galiu tai padaryti?
Taip, aš galiu.
>> Ar galiu eiti į 7 kelio nuo ten?
Taip, galiu.
Tai egzistuoja per daug.
Bet aš galiu eiti į 4 kelią iš čia?
Štai tarsi klausia klausimą, gali Aš toliau nustatyta, kad mažai aikštė
kad aš paryškinamas geltonai?
Nėra nieko ten.
Teisė.
>> Nėra žingsnis į priekį žemyn 4 keliu.
Jei Prinstono buvo šiame TRIE, kad 4 būtų buvę prieki mums jau.
Ir kad šiuo metu mes pasiekė aklavietę.
Mes negalime eiti toliau.
Ir taip, mes galime pasakyti, galutinai, ne.
Prinstono neegzistuoja šiame TRIE.
>> Taigi, ką visa tai reiškia?
Teisė.
Yra daug vyksta čia.
Yra patarimų visur.
Ir, kaip jūs galite pamatyti, tik iš diagramos,
ten mazgų daug, kad yra rūšies plaukioja aplink.
Tačiau pastebėti kiekvieną kartą norėjome patikrinti, ar kažkas buvo į TRIE,
mes tik turėjo padaryti 4 žingsnius.
>> Kiekvieną kartą, kai mes norėjome įterpti kažką TRIE,
mes turime padaryti 4 žingsnius, galbūt mallocing kai pakeliui stuff.
Bet, kaip matėme, kai mes įdėta Dartmouth į TRIE,
kartais kai kurie iš kelio gali būti jau prieki už mus.
Ir taip mūsų Trie gauna didesni ir didesni, mes turime padaryti mažiau darbo kiekvieną kartą
įterpti naujus dalykus nes mes jau ve
pastatė tarpinis daug filialai pakeliui.
Jei mes tik kada nors pažvelgti į 4 dalykai, 4 yra tik konstanta.
Mes tikrai yra natūra artėja pastovus laikas įterpimo
ir nuolatinis laiko peržvalgos.
Kompromisas, žinoma, yra ta, kad tai Trie, kaip jūs galite galbūt pasakys,
yra didžiulis.
Kiekvienas iš šių mazgų užima daug vietos.
>> Bet tai kompromisas.
Jei norime tikrai greitai įterpimo, tikrai greitai išbraukta,
ir tikrai greitai peržvalgos, turime turi daug duomenų plaukioja aplink.
Mes turime atidėti daug vietos ir atminties už tą duomenų struktūros
egzistuoti.
>> Ir taip tai kompromisas.
Tačiau atrodo, kad mes galėjo ją radau.
Mes nustatėme, kad gali Gralis duomenų struktūrų
su greito įkišimo išbraukta ir peržvalgos.
O gal tai bus tinkamų duomenų struktūra
naudoti dėl kokios nors informacijos mes bandome parduotuvėje.
Aš Doug Lloyd, tai CS50.