[TÓNLIST spila] DOUG LLOYD: Þannig að við höfum verið að fikra nær og nær að Gral gögnum mannvirki, einn sem við getum sett í, eyða úr og líta upp í föstu tíma. Hægri. Það er tegund af markinu. Við viljum vera fær um að gera það mjög, mjög fljótt. 

Höfum við fundið það hér þegar við erum að tala um reynir? Jæja, við skulum taka a líta. Þannig að við höfum séð nokkur mismunandi gögn uppbygging sem annast kortlagningu svokölluð lykill-gildi par, kortleggja nokkur stykki af gögn að einhverju öðru stykki af gögn svo við vitum hvar á að finna Upplýsingar í uppbyggingu. 

Svo fyrir array, til dæmis, að lykill er þáttur vísitölu eða array staðsetningu 0 eða fylki 1 og svo framvegis. Og gildi eru gögnin sem er til staðar á þeim stað. Svo hvað er geymt í array 0? Hvað er geymt í array 1 á móti bara 0 og 1, sem væri lykillinn. 

Með kjötkássa borð það er tegund af sömu hugmynd. Með kjötkássa borð, höfum við þetta kjötkássa fall sem býr til kjötkássa kóða. Svo er lykillinn kjötkássa kóða gögnum. Og verðmæti, sérstaklega við töluðum um chaining í vídeó á kjötkássa matskeið, er að tengist listi af gögnum sem kjötkássa þeirri Tætifall. Hægri. Hvað um aðra nálgun Þessi aðferð, þó? Hvað um aðferð þar sem Lykillinn er tryggt að vera einstakt, ólíkt kjötkássa borð, þar sem við gátum endað með tvö stykki af gögnum hafa sömu Tætifall. Og þá verðum við að takast á við að með því að annað hvort leit eða fleiri helst læsa að laga þessi vandamál. 

Svo nú getum við tryggt sem lykill okkar mun vera einstakt. Og hvað ef gildi okkar var bara eitthvað sem auðvelt eins satt og ósatt sem segir okkur hvort eða ekki stykki af upplýsingar er í uppbyggingu? A Boolean gæti verið eins einfalt og a hluti. Raunhæft er það líklega Byte líklegri en smá. En það er miklu minni en geyma kannski 50 staf band, til dæmis. 

Svo reynir, svipað kjötkássa borð, sem sameina fylki og tengda listanum, reynir sameina fylki, mannvirki og ábendingum saman til að geyma gögn í áhugaverð leið sem er nokkuð frábrugðin eitthvað sem við höfum séð hingað til. Nú notum við gögn sem vegamaður að sigla þessa gögn uppbygging. Og ef við getum fylgst sem vegamaður, ef við getum fylgja gögn frá upphafi til enda, við munum vita hvort þessi gögn eru í Trie. 

Og ef við getum ekki fylgt kortinu frá þýðir að enda á alla, gögn geta ekki til. Aftur, eru lykillinn hér tryggt að vera einstakt. Og svo ólíkt kjötkássa borð, munum við aldrei að takast á við árekstra hér. Og engar tvær stykki af gögnum hafa nákvæmlega sömu vegamaður nema að gögn séu eins. 

Ef við setjum John, þá við að leita að John. Það er tvær samskonar stykki af gögn, rétt, við erum að leita í gegnum. En annars, hvaða tvö stykki af gögn eru tryggt að hafa einstaka roadmaps í gegnum þetta gagnagrind. Og við erum að fara að kíkja á sjón af þessu í bara smá stund. 

Við munum gera það með því að reyna að búa til nýja gögn uppbygging, kortleggja á eftirfarandi gildi pör. Í þessu tilfelli erum við ekki að fara að nota eitthvað eins einfalt og Boolean. Við reyndar mun geyma band. Og það band er að fara að veri nafn háskóla. 

Og lykillinn er að fara að vera ár þegar að Háskólinn var stofnaður. Öll ár til háskóla eru að fara að vera fjórir stafir. Og svo við munum nota þessar fjórar tölur til rata um gögn uppbygging. Og við munum sjá, aftur, hvernig við gerum það í bara annað. 

Í lok leið, við munum sjá nafn háskólans sem svarar við takkann, þessir fjórir tölustafir. Grunnhugmyndin á bak við Trie er að við höfum miðlæga bláæð. Svo hugsa um það eins og tré. Og þetta er svipað í stafsetningu og í hugtak til tré. Almennt þegar við hugsum um tré í hinum raunverulega heimi, þeir hafa rót sem er í jörð og þeir vaxa upp og þeir hafa útibú og þeir hafa leyfi. Og í rauninni er hugmyndin um a Trie er nákvæmlega það sama, nema að rót er fest einhvers staðar á himni. Og blöðin eru neðst. 

Svo það er góður af eins og að taka tré og bara snúa henni á hvolf. En það eru samt útibú. Og þeir væri ferli okkar, þá verður tengingar okkar frá rót til laufum. Í þessu tilviki, þá slóðir, þá útibú eru merktar með tölustöfum sem segja okkur sem leið til að fara þar sem við erum. 

Ef við sjáum 0, við förum niður þessa grein, ef við sjáum 1, við förum niður þessa grein, og svo og svo framvegis. Jæja, hvað þýðir þetta? Jæja, það þýðir að á hverjum mótum stað og hver hnútur í miðju og hvert útibú, það eru 10 mögulegt stöðum sem við getum farið. Þannig að það eru 10 ábendingar frá hverjum stað. 

Og þetta er þar reynir getur fengið svolítið erfið fyrir einhvern sem er ekki með mikið af reynslu í tölvunarfræði áður. En reynir eru í raun nokkuð ógnvekjandi. Og ef þú hefur tækifæri til að vinna með þeim og þú ert tilbúin til að grafa í og tilraunir með þá, þeir eru í raun alveg áhugavert gögn uppbygging til að vinna með. Ef við viljum að setja stak í Trie, allt sem við þurfum að gera er að byggja rétta slóð frá rót til blaða. Hér er það sem hvert skref meðfram hvernig gæti litið út. Við erum að fara að skilgreina ný gögn uppbygging fyrir nýjan hnút kallast Trie. 

Og inni í því gögn uppbygging eru tvö stykki. Við erum að fara til að geyma Heiti háskóla. Og við erum að fara að geyma fjölbreytta ábendingum öðrum hnúður af sömu gerð. Svo aftur, þetta er þessi tegund af hugmyndinni um alls staðar við erum, við erum á 10 hægt stöðum við getum farið. Ef við sjáum 0, við förum niður þessa grein. Ef við sjáum 1, þetta útibú, og svo framvegis og svo framvegis og svo framvegis. Ef við segjum 9, við förum niður þessa grein. Svo á hverjum mótum lið, getum við farið 10 mögulegum stöðum. Svo hefur hver hnútur að innihalda 10 ábendingum öðrum hnúður, til 10 annarra hnúta. 

Og gögn sem við erum að geyma er bara nafn skólans. Svo skulum byggja Trie. Skulum setja nokkrar efna og hluta í Trie okkar. Svo á the mjög toppur, þetta er hnút rót okkar. Þetta er líklega að fara að vera eitthvað þú ert að fara að á heimsvísu, það boðum. Og þú ert að fara að á heimsvísu viðhalda bendi til þessa hnút alltaf. 

Þú ert að fara að segja, rót jafngildir, og þú ert fara að malloc þér Trie hnút. Og þú ert aldrei að fara að snerta rót aftur. Í hvert skipti sem þú vilt að byrja siglingar í gegnum, þú Aðra músina jafn rót, svo sem Trav, sem er dæmi sem ég nota í mörgum myndböndum mínum hér á stöflum og biðröðum og tengja listar og svo framvegis. 

Þú Aðra músina kallað Trav fyrir traversal. Og þú notar Trav að sigla gegnum gögn uppbygging. Þannig að við skulum sjá hvernig þetta gæti litið. Svo núna, hvað er hnúturinn líta út? Jæja, eins og gögn okkar uppbyggingu yfirlýsingu fram, við höfum band, sem í þessu tilfelli er tóm. Það er ekkert hér. 

Og fjölda 10 ábendingum. Og núna, aðeins við hafa 1 hnút í þessum Trie. Það er ekkert annað í henni. Svo allt 10 af þeim ábendingum benda á núll. Það er það sem rauður gefur til kynna. 

Skulum setja band Harvard. Skulum setja Háskóli Harvard í þessa Trie, sem var stofnað árið 1636. Við viljum nota takkann, 1636, til að segja okkur hvar við erum að geyma Harvard í Trie. Nú, hvernig getum við gert það? 

Það gæti litið eitthvað svona. Við byrjum á rót. Og við höfum þessar 10 staði sem við getum farið. Rótin er bara eins og allir annað hnút á Trie. Það eru 10 staðir sem við getum farið héðan. 

Hvert viljum við sennilega að fara ef lykillinn er 1636? Það er í raun tveir valkostir. Hægri. Við getum byggt lykil af hægri til vinstri og byrja með 6. Eða við gætum byggt lykil af frá vinstri til hægri og byrja með 1. 

Það er líklega meira innsæi sem manneskju að skilja við munum bara fara til vinstri til hægri. Og svo ef ég vil setja Harvard í þessa Trie, Ég vil líklega að byrja með því að byrja á rót, horfa á 10 valkostum mínum fyrir framan mig, og sagði Ég vil fara niður 1 braut. OK. 

Nú, 1 leið er nú null. Þannig að ef ég vil halda áfram niður þennan veg að setja þennan þátt í Trie, Ég verð að malloc nýja hnút, hafa 1 benda þar, og þá er ég góður að fara. 

Þannig að ég er í grundvallaratriðum á a lið þar sem ég stend á rót trésins eða á Trie og það eru 10 útibú. En hvert útibú hefur hliðið fyrir framan það. Hægri. Vegna þess að það er ekkert annað er þarna. Engin örugga leið. Það þýðir að það er ekkert niður eitthvað af þessum greinum. Ef ég vil byrja að byggja eitthvað, ég vil fjarlægja hliðið. Mig langar að fjarlægja hliðið framan númer 1. Og ég vil ganga niður að. Og ég vil að byggja annar staður fyrir mig að fara. 

Og það er það sem ég hef gert hér. Svo 1 ekki lengur bendir á núll. Ég hef sagt að það er óhætt að fara niður hér núna. Ég byggði annað hnút. Og þegar ég fæ að hnút, ég hafa annað ákvörðun að gera. Hvert er ég að fara að fara héðan? 

Jæja, ég hef nú þegar farið niður 1. Svo nú vil ég sennilega að fara niður 6. Hægri. Aftur, ég hef 10 staði ég get valið. Svo skulum við fara núna niður númer 6. Svo ég hreinsa hliðið fyrir framan númer 6. Og ég geng þarna niðri. Og ég byggja annan hnút. Og ég hef náð annað mótum lið. 

Aftur, ég hef 10 val fyrir þar sem ég get farið. Ég hef flutt frá 1 til 6. Svo nú vil ég líklega að fara í 3. 3, það er hvergi ég get farið. Svo ég verð að ryðja brautina og byggja mér nýtt rúm. Og þá frá 3, þar sem ég vil fara? Ég vil fara niður 6. 

Og aftur, ég þurfti að hreinsa leið til að gera það. Svo nú hef ég notað lykil til að setja búa hnútar og byrja að byggja þessa Trie. Ég hef byrjað á rót. Ég hef farið niður 1636. Og nú er ég neðst þar á hnút. Og þú might vera fær til sjá það á skjánum. 

Það er auðkenndur með gulum. Það er þar sem ég er nú. Lykill er gert. Ég hef búinn hvert stöðu lykillinn minn. Svo ég get ekki farið lengra. Svo á þessum tímapunkti, allt sem ég þarf virkilega að gera er að segja, OK. Það er góður af eins og að leita niður á jörðina, ef þú ert envisioning sjálfur eins þessa tegund af braut með mismunandi tengingar. Raða af að horfa niður og svoleiðis úða mála Harvard á jörðinni. Það er nafnið á þessu. Veit það er það sem er á þessum stað. Ef við byrjum á rót og við förum niður 1 og síðan 6 og síðan 3 og þá 6, hvar erum við? Jæja, ef við lítum niður og við sjáum Harvard, þá við vitum að Harvard var stofnað árið 1636 byggt á leiðinni við erum að innleiða þessa gögn uppbygging. Svo það var vonandi einfalt. Við erum að fara að gera tvær ísetningar. Og vonandi að það mun hjálpa til sjá þetta gert tvisvar í viðbót. 

Nú, við skulum setja annað háskóla. Skulum setja Yale inn í þennan Trie. Yale var stofnað árið 1701. Þannig að við munum byrja á því rót, eins og við gerum alltaf. Og við setjum upp Traversal músina. Við erum að fara að nota það til að fara í gegnum. The fyrstur hlutur sem við viljum gera er að fara niður á 1 braut. Það er fyrsta talan lykill okkar. Sem betur fer, þó, er það ekki þarft að gera allir vinna í þetta sinn. The 1 leið hefur þegar verið eytt. Ég ruddi það áður þegar ég var að setja Harvard á 1636. Svo ég get örugglega færa niður 1 og bara fara þangað. Ef hægt að færa niður 1. 

Nú, þó, ég vil fara til 7. Ég ruddi brautina á 6. Ég veit að ég get örugglega áfram niður 6 braut. En ég þarf að halda áfram á 7 braut. Svo hvað þarf ég að gera? Jæja, bara eins og áður, ég þarf bara að hreinsa hliðið, fá út af the vegur, og byggja nýja hnút úr 7 braut. Bara svona. 

Svo nú er ég hef flutt á 1 og síðan 7. Og nú eftir, ég er svona af á þessum nýja subbranch. Hægri. Allt annað frá 16 á, ég hugsa ekki um. Ég ætla ekki að gera 16 neitt. Ég er að gera 17 efni. 

Svo nú úr 17 á, ég verð að konar ótroðnar slóðir hér. Næsta stafa lykillinn minn er 0. Ég greinilega getur ekki fá neitt. Ég byggði bara þennan hnút. Þannig að ég veit að það er engin slóðir áfram héðan. Svo ég verð að gera einn sjálfur. 

Svo ég malloc nýja hnút og hafa 0 tímapunkti. Og svo er eitt skipti, malloc I a Ný hnút og hafa eitt stig þar. Aftur, ég hef búinn lykil, 1701. Svo ég lít niður og ég úða mála Yale. Það er nafn þessarar hnút. 

Og svo nú ef ég þarf alltaf að sjá hvort Yale er í þessum Trie, byrja ég á rót, Ég fer niður 1701, og líta niður. Og ef ég sé Yale úða máluð á jörðu, þá Ég veit Yale til í þessum Trie. Við skulum gera eitt. Skulum setja Dartmouth í þetta Trie, sem var stofnað árið 1769. 

Byrja á rót aftur. Fyrsta stafa minn lykillinn minn er 1. Ég get örugglega fara niður þennan veg. Það er nú þegar til. Næsta stafa af lykillinn minn er 7. Ég get örugglega fara niður þennan veg. Það er eins og heilbrigður. 

Næsta minn er 6. Héðan frá þar sem ég er núna að í gulu þarna í miðjum hnút, 6 er nú læst burt. Ef ég vil fara niður þennan veg, Ég verð að byggja það sjálfur. Þannig að ég ætla malloc nýja hnút og hafa 6 stig þar. Og þá aftur, ég er logi nýjar slóðir hér. 

Svo ég malloc nýja hnút þannig að frá sem node-- slóð tala 9-- og þá nú ef ég ferðast 1769, og ég lít niður. Það er ekkert eins úða mála þar. Ég get skrifað Dartmouth. Og ég hef sett Dartmouth í Trie. 

Svo er það að setja það voru Trie. Nú viljum við að leita að hlutum. Hvernig eigum við að leita að hlutum í Trie? Jæja, það er ansi mikið það sama. Nú notum bara tölustafi takkann til að sjá hvort við getum sigla frá rót þar sem við viljum fara í Trie. 

Ef við högg dauður endi á hverjum stað, þá við vitum að þessi þáttur er ekki til staðar eða annað sem leið myndi hafa þegar verið eytt. Ef við tökum það alla leið til enda, allt sem við þurfum að gera er að líta niður og sjá hvort það er þátturinn sem við erum að leita að. Ef það er, velgengni. Ef það er ekki, mistakast. 

Svo skulum leita Harvard í þessu Trie. Við byrjum á rót. Og aftur, við erum að fara að búa til Traversal músina að gera hreyfingar okkar fyrir okkur. Frá rót og við vitum að Fyrsti staðurinn sem við þurfum að fara er 1, getum við gert það? Já við getum. Ef örugglega til. Við getum farið þangað. 

Nú er næsta stað sem við þurfum að fara er 6. Er 6 leið til hér? Já, er það. Við getum farið niður 6 braut. Og við á endanum hér. 

Við getum farið niður 3 leið frá hér? Jæja, eins og það kemur í ljós, já, það er til líka. Og við getum fengið á 6 leið frá hér? Já við getum. 

Við höfum ekki alveg svarað spurningin enn. Það er enn eitt skref, sem er nú við þurfum að líta niður og sjá hvort það er actually-- ef við erum að leita að Harvard, er að hvað er að finna eftir að við útblástur takkann? Í dæminu sem við erum að nota hér, árin eru alltaf fjórir tölustafir. En þú gætir verið að nota td þegar þú ert að geyma orðabók yfir orð. 

Og svo í stað þess að hafa 10 ábendingum fyrir staðsetningu mína, þú might hafa 26. Einn fyrir hvern staf í stafrófinu. Og það eru nokkur orð eins og kylfu, sem er hluti af lotu, til dæmis. Og svo jafnvel ef þú færð til endir af the lykill og þú lítur niður, þú getur ekki séð hvað þú ert að leita að. 

Þannig að þú þarft alltaf að fara yfir allt leið og þá ef þú værir með góðum árangri fær til að fara yfir allt leið, líta niður og gera eitt endanlega staðfestingu. Er það það sem ég er að leita að? Jæja, ég lít niður eftir að byrja efst og fara 1636. Ég lít niður. Ég sé Harvard. Svo, já, tók ég. Hvað ef það sem ég er að leita að er ekki í Trie, þó. Hvað ef ég er að leita að Princeton, sem var stofnað árið 1746. Og svo 1746 verður lykillinn minn að fletta í gegnum Trie. Jæja, byrja ég á rót. Og í fyrsta sæti sem ég vil að fer niður 1 braut. Get ég gert það? Já ég get. 

Get ég farið niður 7 leið þaðan? Já, ég get. Sem er til staðar líka. En get ég farið niður 4 leið frá hér? Það er eins og að spyrja spurningu, getur Ég að halda áfram niður að lítill ferningur sem ég hef bent á gula? Það er ekkert þar. Hægri. 

Það er engin leið fram niður 4 braut. Ef Princeton var í þessum Trie, sem 4 hefði verið eytt fyrir okkur nú þegar. Og svo á þessum tímapunkti við höfum náð dauðum enda. Við getum ekki farið lengra. Og svo við getum sagt, endanlega, nr. Princeton er ekki til í þessum Trie. 

Svo hvað þýðir þetta allt þýðir? Hægri. Það er mikið um að vera hér. Það er ábendingum um allan stað. Og, eins og þú sérð bara af myndinni, það er mikið af hnúður sem eru eins konar fljúga í kring. En taka hvert skipti sem við vildum að athuga hvort eitthvað var í Trie, við þurftum aðeins að gera 4 hreyfingar. 

Í hvert skipti sem við vildum að setja eitthvað í Trie, við verðum að gera 4 færist hugsanlega mallocing smá dót á leiðinni. En eins og við sáum þegar við bætist Dartmouth í Trie, stundum sumir af þeirri braut gæti þegar verið eytt fyrir okkur. Og svo eins og Trie okkar fær stærri og stærri, höfum við gert minna vinna í hvert skipti að setja nýja hluti vegna þess að við höfum nú þegar byggt mikið af millistig Útibú leiðinni. Ef við höfum bara alltaf að horfa á 4 hlutir, 4 er bara stöðug. Við raunverulega eru konar nálgast stöðug tími innsetningu og stöðug tími útlit. The tradeoff, að sjálfsögðu, að vera að þetta Trie, eins og þú geta sennilega sagt, er mikil. Hver einn af þessum hnúður tekur upp mikið pláss. 

En það er tradeoff. Ef við viljum virkilega fljótur innsetning, mjög fljótur eyðingu, og mjög fljótur útlit, verðum við að hafa mikið af gögnum að fljúga í kring. Við verðum að leggja til hliðar mikið pláss og minni fyrir það gögn uppbygging að vera til. 

Og svo er að tradeoff. En það lítur út eins og við gæti hafa fundið það. Við gætum hafa komist að því að Gral gögn uppbygging með fljótur ísetningu eyðingu, og útlit. Og kannski þetta verður viðeigandi gögn uppbygging að nota fyrir hvaða upplýsingar við erum að reyna að geyma. Ég er Doug Lloyd, þetta er CS50.