[Predvaja glasba] Doug LLOYD: Torej smo bili inching bližje in bližje, da je sveti gral podatkov strukture, tista, ki se lahko vstavi v, izbrišete iz in poglej gor v stalnem času. Prav. To je nekako avt. Želimo biti sposoben narediti stvari zelo, zelo hitro. 

Imeli smo ga našli tukaj, ko govorimo o poskusih? No, poglej. Tako smo videli več različne podatkovne strukture ki skrbi za preslikavo ti pari ključ vrednostjo, kartiranje kakšen kos podatkov na nek drug podatek tako da bomo vedeli, kje najti Podatki v strukturi. 

Torej za niz, na primer, Ključ je indeks element ali niz lokacija 0 ali matrika 1 in tako naprej. In je vrednost podatkov da obstaja na tem mestu. Torej, kaj shranjeni v matriki 0? Kaj se shrani v polju 1 v primerjavi s samo 0 in 1, ki bi bili ključi. 

Z hash tabele je sortiranje iste zamisli. Z hash tabele, imamo to hash Funkcija, ki ustvarja hash kode. Torej je ključ hash code podatkov. In vrednost, zlasti smo se pogovarjali o verižni v videu na hash tabele, je ta povezana seznam podatkov da hashes na to hashcode. Prav. Kaj pa drugega pristopa Ta metoda, čeprav? Kaj metodi kadar Ključ je zagotovljeno, da je edinstven, za razliko od hash tabele, kjer smo lahko na koncu z dvema kosoma podatkov ki ima isto hashcode. In potem smo se morali spopasti s da jih bodisi sondiranje ali več možnosti verižnem popraviti to težavo. 

Zdaj bomo lahko zagotovili da bo naša ključna edinstvena. In kaj, če je bil naš vrednost samo nekaj tako enostavno, kot true in false, ki nam pove, ali ali ne, da podatek obstaja v strukturi? Logično bi bilo tako enostavno, kot bit. Realno je to verjetno bajtu bolj verjetno kot bit. Ampak to je veliko manjša od shranjevanje morda niz 50 znakov, npr. 

Torej poskusih podobna hash tabele, ki združujejo nizi in povezani seznam, poskuša združiti nizi, strukture in kazalci skupaj za shranjevanje podatkov v zanimiv način, ki je precej drugačna od kaj smo videli doslej. Zdaj smo uporabili podatke kot načrt krmariti to podatkovno strukturo. In če bomo lahko sledili načrt, če bomo lahko nadaljnje podatke iz začetka do konca, bomo vedeti, ali te podatke obstajajo v trie. 

In če ne moremo slediti zemljevid od kar pomeni, da na koncu sploh, podatkov ne more obstajati. Spet ključi tukaj zagotovljeno, da je edinstven. In tako za razliko od hash tabele, bomo nikoli se morajo ukvarjati z trčenj tukaj. In ni dveh kosov podatkov imajo povsem enak načrt razen če so podatki enaki. 

Če bomo vstavite John, nato iščemo za Janeza. To je dva identična kosov podatki, prav, bomo iskali skozi. Toda drugače, vsak dva kosa podatkov so zagotovljeno, da imajo edinstvene načrte skozi to strukturo podatkov. In bomo si oglejte vizualni to v samo trenutek. 

To bomo storili s poskušanjem ustvariti novo podatkovno strukturo, kartiranje naslednje ključne parov vrednosti. V tem primeru ne bomo uporabljati nekaj tako enostavno, kot logičnim. Bomo dejansko shranite niz. In da je niz se bo je ime univerze. 

In ključ se bo leto ko je bila ta univerza ustanovljena. Vsa leta za univerze se bodo štiri številke. In tako bomo uporabili te štiri cifre na krmariti skozi to strukturo podatkov. In bomo videli, še enkrat, kako storimo, da v samo sekundo. 

Na koncu poti, bomo videli ime univerze, ki ustreza v tem ključu, te štiri številke. Osnovna ideja je Trie je imamo osrednjo pot. Torej, razmišljam o tem kot drevo. In to je podobno kot pri črkovanju in v koncept na drevesu. Na splošno, ko razmišljamo o drevesa v resničnem svetu, imajo korenine, ki je v tleh in rastejo navzgor in imajo podružnice in imajo listi. In v bistvu ideja trie je popolnoma enak, razen da je koren zasidrana nekje na nebu. In listi so na dnu. 

Torej, to je nekako kot ob drevo in samo flipping glavo. Vendar še vedno obstajajo panoge. In tisti, bi bilo naše poti, tistih, ki bodo naši povezave od korenin do listov. V tem primeru tistih poti, te podružnice so označeni s številkami, ki nam povedo, v katero smer iti od tam, kjer smo. 

Če vidimo 0, gremo po tej podružnici, če bomo videli 1, gremo po tej podružnici, in tako in tako naprej. No, kaj to pomeni? No, to pomeni, da na vsaki stični točki in vsako vozlišče v srednji in vsaka veja, obstajajo 10 možno kraji, da lahko gremo. Torej obstaja 10 kazalci iz vsake lokacije. 

In to je, če lahko poskuša dobiti malo zastrašujoče za nekoga kdo nima veliko izkušnje na področju računalništva poprej. Ampak poskuša so res precej super. In če imate priložnost za delo z njimi in ste pripravljeni kopati, v in eksperimentira z njimi, oni so res precej zanimivo podatkovne strukture delati. Če želimo vstaviti element v Trie, vse, kar morate storiti, je zgraditi pravo pot od korenin do listov. Tukaj je tisto, kar na vsakem koraku, skupaj kako bi izgledal. Bomo določili novo podatkov strukturo za novo vozlišče, imenovano trie. 

In znotraj teh podatkov Struktura obstajata dva kosa. Mi bomo za shranjevanje ime univerze. In bomo za shranjevanje niz kazalcev z drugimi vozlišči istega tipa. Torej, še enkrat, to je, da sortiranje od koncepta povsod smo, smo na 10 mogoče krajev, lahko gremo. Če vidimo 0, gremo dol to vejo. Če bomo videli 1, ta podružnica, in tako naprej in tako naprej in tako naprej. Če rečemo, 9, gremo dol to vejo. Torej na vsaki stični točki, lahko gremo 10 možnih krajev. Torej vsako vozlišče mora vsebovati 10 kazalcev do drugih vozlišč, do 10 drugih vozlišč. 

In podatke bomo shranjevanje je samo ime univerze. Torej, kaj je zgraditi trie. Oglejmo vstavite par postavk v naši trie. Torej, na samem vrhu, to je naša koren vozlišče. To je verjetno, da bo nekaj boš globalno prijave. In ti boš globalno ohraniti kazalec na tem vozlišču vedno. 

Boste rekli, koren enak, in ste dogaja, da si malloc Trie vozlišče. In ti ne bo nikoli ponovno dotakniti korenin. Vsakič, ko želite Navigacijo začnete s, nastavite drug kazalec enako korena, kot trav, ki je primer I uporabo v veliko mojih videoposnetkov tukaj na kupih in čakalnih vrst in seznami povezav in tako naprej. 

Nastavite drug kazalec pozval trav za prečkanje. In uporabljate trav za navigacijo s podatkovno strukturo. Torej, da vidimo, kako se bo to videti. Torej sedaj, kaj ne vozlišče izgledal? No, tako kot naših podatkih Izjava struktura je navedeno, imamo niz, ki je V tem primeru je prazna. Nič ni tukaj. 

In niz 10 kazalcev. In zdaj smo samo ima pa 1 vozlišče v tem trie. Nič drugega v njej. Tako da vse 10 tistih kazalci pokažite na ničlo. To je tisto, rdeča označuje. 

Oglejmo vstavite niz Harvard. Oglejmo vstavite univerza Harvard v tem trie, ki je bila ustanovljena leta 1636. Želimo, da uporabite tipko, 1636, da nam poveste, kje smo dogaja, da shranite Harvard v trie. Zdaj, kako lahko to storimo? 

Morda bi izgledala nekako takole. Začnemo pri korenu. In imamo teh 10 mest lahko gremo. Korenina je tako kot vsaka drugo vozlišče trie. Obstaja 10 krajev, lahko gremo od tukaj. 

Kam bomo verjetno želeli iti, če je ključ 1636? Tam je res dve možnosti. Prav. Lahko gradimo ključ desne proti levi in ​​začeti s 6. Ali lahko gradimo na ključ od leve proti desni in začeti z 1. 

To je verjetno bolj intuitiven kot človeško bitje da bomo razumeli boste pojdi z leve proti desni. In tako, če želim, da vstavite Harvard v tem Trie, Verjetno želim začeti z začetkom pri korenu, videti na mojih 10 možnosti pred mano in rekel Rad bi šel dol v 1 pot. V REDU. 

Zdaj, 1 Pot je sedaj null. Torej, če želim nadaljevati po tej poti vstaviti ta element v Trie, Moram malloc novo vozlišče, imajo 1 točko tam, in potem sem na dobri poti. 

Tako sem v bistvu sem na točka, kjer stojim na korenu drevesa ali trie in tam so 10 podružnice. Ampak vsaka veja ima vrata pred njim. Prav. Ker ni nič drugega tam. Ne varen prehod. To pomeni, da ni nič katerokoli od teh podružnic. Če želim začeti gradnjo nekaj, želim odstraniti vrata. Želim odstraniti vrata pred številko 1. In želim, da hodi dol, da. In želim graditi drugo mesto za mene, da gredo. 

In to je tisto, kar sem tukaj naredil. Torej 1 ne kaže na null. Sem rekel, da je varno iti tukaj zdaj. Sem zgradil še eno vozlišče. In ko pridem do tega vozlišča, I še eno odločitev, da bo. Kje sem šla od tu? 

No, sem že šel dol po 1. Torej, zdaj bom verjetno želeli, da gredo navzdol 6. Prav. Spet imam 10 lokacij bom lahko izbirate. Torej, kaj je zdaj dol številko 6. Tako sem počistiti vrata Pred številko 6. In jaz sem hodil tja dol. In jaz zgraditi še eno vozlišče. In sem dosegel drugo priključno točko. 

Spet imam 10 izbire za kje lahko grem. Sem se preselil od 1 do 6. Torej, zdaj bom verjetno želeli, da gredo do 3. 3, pa je nikjer ne morem iti. Tako da sem moral počistiti pot in zgraditi sam nov prostor. In potem od 3, Kam želite iti? Rad bi šel dol 6. 

In, še enkrat, sem moral jasen način, da to storite. Torej, zdaj sem uporabil moj ključ za vstavljanje ustvarjanje vozlišča in začeti graditi to trie. Začel sem pri korenu. Sem padel na tla in 1636. In zdaj sem na dnu tam na to vozlišče. In boste morda lahko ga vidite na zaslonu. 

To je poudarjeno v rumeno. To je, kjer sem trenutno jaz. Moj ključ je storiti. Sem izčrpana vsak položaj v mojem ključu. Tako da ne more iti več naprej. Torej, v tem trenutku, vse, kar sem res morate storiti je reči, OK. To je nekako kot je videti v tla, če ste viziranje sebe kot te vrste poti z različnimi priključki. Nekako je videti dol in nekako spray slikarstvo Harvard na terenu. To je ime za to. Vedite, da je tisto, kar je na tej lokaciji. Če začnemo pri korenu in gremo dol 1 in nato 6 in nato 3, nato pa 6, kje smo? No, če pogledamo navzdol in vidimo Harvard, nato vemo, da je Harvard ustanovljeno leta 1636, ki temelji na poti smo izvajanje te podatkovne strukture. Tako da je bil upajmo enostavna. Bomo narediti še dva vstavljanja. In upajmo, da bo to pripomoglo k glej to storjeno dvakrat več. 

Zdaj pa vstavite drugo univerzo. Oglejmo vstavite Yale v tem trie. Yale je bila ustanovljena leta 1701. Torej bomo začeti izvajati koren, kot smo vedno. In smo si zastavili prečkanje kazalec. Bomo uporabili, da se premaknete skozi. Prva stvar, ki jo želimo storiti, je šel dol v 1 pot. To je prva številka našega ključa. Na srečo, čeprav ne bomo morali narediti katerokoli delo, ki ta čas. Se je 1. Pot je že izbil. Jaz žogo izbil prej, ko sem je vstavljanje Harvard na 1636. Tako da sem lahko varno premikanje dol 1. in pojdi tja. Če lahko premaknete navzdol 1. 

Sedaj, čeprav, hočem iti do 7. Sem odprla pot na 6. Vem, da sem lahko varno nadaljuje navzdol 6 pot. Ampak moram nadaljevati na 7 poti. Torej, kaj moram storiti? No, tako kot prej, jaz šele potreba počistiti vrata, ven iz poti, in zgraditi novo vozlišče s 7 poti. Tako kot je ta. 

Torej, zdaj sem se preselil 1 in se nato 7. In zdaj opazili, da sem nekako od te nove Subbranch. Prav. Vse ostalo od 16 no, jaz ne briga. Jaz ne delam 16 ničesar. Delam 17 stvari. 

Torej, zdaj od 17 naprej, moram nekako pokazati nove poti tukaj. Naslednja številka moj ključ je 0. Jaz seveda ne more dobiti nikjer. Pravkar sem zgradil to vozlišče. Zato vem, da ni poti naprej od tod. Tako da sem moral narediti eno sam. 

Tako sem malloc novo vozlišče in imajo 0 točk tam. In potem še enkrat, sem malloc novo vozlišče in ima eno točko tam. Spet sem izčrpana svoj ključ, 1701. Zato sem pogledal dol in sem spray barve Yale. To je ime tega vozlišča. 

In zdaj, če bom kdaj morali videti, če Yale je v tem Trie, začnem pri korenu, Grem dol 1701, in pogledal dol. In če vidim Yale sprej pobarvan na tla, potem Vem Yale obstaja v tem trie. Naredimo še eno. Oglejmo vstavite Dartmouth v to trie, ki je bila ustanovljena leta 1769. 

Spet pri korenu. Moja prva številka mojega ključa je 1. Mirno lahko premikate po tej poti. Ki že obstaja. Naslednja številka mojega ključa je 7. Mirno lahko premikate po tej poti. Obstaja pa tudi. 

Moj naslednji pa je 6. Od tu, od koder sem trenutno jaz v rumeno je v tem osrednjem vozlišču, 6 je trenutno zaklenjena off. Če želim iti po tej poti, Moram ga graditi sam. Torej bom malloc novo vozlišče in imajo 6 točko tam. In potem še enkrat, jaz sem Plamen nove poti tukaj. 

Tako sem malloc novo vozlišče tako, da se od da node-- številka pot 9-- in nato zdaj če potujem 1769, in sem pogledal dol. Nič zdaj spray tam naslikal. Pisati znam Dartmouth. In sem se vstavi Dartmouth v trie. 

Tako da je vstavljanje Stvari v trie. Sedaj želimo iskati stvari. Kako iščemo stvari v trie? No, to je precej isto idejo. Zdaj smo samo uporabo številk ključa da vidim, če smo lahko premikate od korena kam želimo iti v trie. 

Če bomo zadeli slepo ulico na kateri koli točki, nato pa vemo, da ta element ni mogoče obstaja ali pa bi, da je pot že izbil. Če naredimo to vse tja do konec, vse, kar morate storiti, je pogledal dol in videli, če je to element, ki ga iščemo. Če je to uspeh. Če je ne, ne. 

Tako da je iskanje Harvard v tem trie. Začnemo pri korenu. In še enkrat, bomo ustvariti prečkanje kazalec narediti naše poteze za nas. Od korenin vemo, da je prvo mesto moramo iti 1, lahko storimo? Ja lahko. Če varno obstaja. Lahko gremo tja. 

Zdaj, naslednji kraj moramo iti, je 6. Ali 6 pot obstaja od tu? Ja, to počne. Lahko gremo navzdol 6 pot. In smo na koncu tukaj. 

Lahko gremo dol 3 poti od tu? No, kot se izkaže, ja, da obstaja preveč. In lahko pridemo na 6 poti od tu? Ja lahko. 

Nismo povsem odgovoril vprašanje še ni. Tam je še ena več korak, ki je sedaj moramo pogledati navzdol in vidim, če je to actually-- Če iščemo Harvardu, je, da Kaj smo ugotovili, ko smo izčrpali ključ? V našem primeru smo z uporabo tukaj, leta so vedno štiri številke. Vendar vas bo morda s pomočjo primer, če ste shranjevanje slovar besed. 

In tako namesto ob 10 kazalcev za mojo lokacijo, boste morda morali 26. Eno za vsako črko abecede. In tam so nekatere besede kot bat, ki je podmnožica serije, npr. In tako tudi, če prideš do Konec ključa in jo potem tla morda ne boste videli, kaj iščete. 

Tako boste vedno imeli za prečkanje celotna pot in nato če ste bili uspešno mogli prečkanje celotno pot, pogledal dol in naredil eno končno potrditev. Je to tisto, kar iščem? No, sem pogledal dol po začetku na vrhu in bo 1636. Sem pogledal dol. Vidim Harvard. Torej, ja, mi je uspelo. Kaj pa, če kaj iščem ni v Trie, čeprav. Kaj pa, če iščem Princeton, ki je bila ustanovljena leta 1746. In tako je leta 1746 postal moj ključ krmariti skozi trie. No, naj začnem pri korenu. In na prvem mestu želim da gre navzdol 1 pot. Ali lahko to storim? Ja lahko. 

Lahko grem dol 7 poti od tam? Ja, lahko. Da obstaja preveč. Ampak lahko grem dol s 4 poti od tu? To je kot asking vprašanje, lahko Sem se nadaljuje navzdol, da malo square da sem označen z rumeno barvo? Nič ni tam. Prav. 

Ni šans, naprej dol po 4 poti. Če je Princeton v tem Trie, da 4 bi bili izbil za nas že. In tako se na tej točki smo dosegli slepo ulico. Mi ne more iti več naprej. In tako lahko rečemo, dokončno, št. Princeton ne obstaja v tem trie. 

Torej, kaj vse to pomeni? Prav. Tam je veliko dogaja. Tam je kazalci po vsem mestu. In, kot lahko vidite samo iz diagrama, tam je veliko vozlišč, ki so nekako plujejo okoli. Ampak obvestilo vsakič, ko smo želeli preveriti, ali je bilo nekaj v Trie, smo imeli šele, da bi 4 poteze. 

Vsakič, ko smo želeli nekaj vstavili v Trie, moramo narediti 4 poteze, po možnosti mallocing nekaj stvari na tej poti. Toda, kot smo videli, ko smo vstavi Dartmouth v Trie, včasih nekatere sredino je morda že izbil za nas. In tako kot naša trie dobi večji in večji, moramo storiti manj dela vsakič vstaviti nove stvari Ker smo že zgradili veliko vmesna veje vzdolž poti. Če bomo samo kdaj pogledati 4 stvari, 4 je le konstantna. Res smo se nekako približuje stalen čas vstavitve in konstantna čas iskanje. Kompromis, seveda, le da to trie, kot si verjetno lahko povem, je ogromno. Vsak od teh vozlišč zavzame veliko prostora. 

Ampak to je kompromis. Če želimo res hitro vstavljanje, res hiter izbris, in res hitro iskanje, moramo imajo veliko podatkov plujejo okoli. Moramo prahi veliko prostora in pomnilnik za te strukture podatkov obstajati. 

In tako, da je kompromis. Ampak izgleda, da mi Morda so ga našli. Smo lahko ugotovili, da Sveti gral podatkovnih struktur s hitro vstavljanje, izbris in iskanje. In morda to bo ustrezno strukturo podatkov uporabiti za katerega koli informacij poskušamo trgovini. Sem Doug Lloyd, to je CS50.