[Music kucheza] DOUG LLOYD: Kwa hiyo tumekuwa inakaribia karibu na karibu kwamba takatifu grail ya data miundo, moja kwamba tunaweza kuingiza ndani ya, kufuta kutoka, na kuangalia juu muda mara kwa mara. Kulia. Hiyo ni aina ya lengo. Tunataka kuwa na uwezo wa kufanya mambo sana, kwa haraka sana. 

Na sisi kupatikana hapa wakati tunazungumzia inajaribu? Naam, hebu tuangalie. Hivyo tumeona kadhaa miundo mbalimbali data kwamba kushughulikia ramani ya kinachojulikana muhimu-thamani jozi, ramani baadhi kipande cha data kwa baadhi kipande nyingine ya data hivyo sisi kujua wapi kupata habari katika muundo. 

Hivyo kwa safu, kwa mfano, muhimu ni kipengele index au safu eneo 0 au safu ya 1 na kadhalika. Na thamani ya data ambayo ipo katika eneo hilo. Kwa hiyo kile ni kuhifadhiwa katika safu 0? Nini ni kuhifadhiwa katika safu 1 dhidi tu 0 na 1, ambayo itakuwa ni funguo. 

Kwa meza hash ni aina ya wazo moja. Kwa meza hash, tuna hash hii kazi ambayo inazalisha codes hash. Hivyo ni muhimu hash kanuni za data. Na thamani, hasa kuongelea chaining katika video juu ya meza hash, ni kwamba orodha wanaohusishwa ya data kwamba hashes kwa kuwa Msimboreli. Kulia. Je kuhusu mbinu nyingine njia hii, ingawa? Je kuhusu mbinu ambapo ufunguo ni uhakika kuwa ya kipekee, tofauti na hash meza, ambapo tunaweza kuishia na vipande viwili vya data kuwa Msimboreli huo. Na kisha sisi kuwa na kushughulika na kuwa na aidha uchunguzi au zaidi ikiwezekana chaining kurekebisha tatizo hilo. 

Hivyo sasa tunaweza kuhakikisha kuwa ufunguo yetu itakuwa ya kipekee. Na nini kama thamani yetu ilikuwa tu kitu kama rahisi kama kweli na uongo ambayo hutueleza ikiwa au si kwamba kipande cha habari ipo katika muundo? Boolean inaweza kuwa rahisi kama kidogo. Kwa kweli pengine ni Byte zaidi kuliko kidogo. Lakini hiyo ni mengi ndogo kuliko kuhifadhi labda kamba 50-tabia, kwa mfano. 

Hivyo inajaribu, sawa na hash meza, ambayo kuchanganya arrays na orodha wanaohusishwa, inajaribu kuchanganya arrays, miundo, na kuyatumia pamoja ili kuhifadhi data katika njia ya kuvutia hiyo ni pretty tofauti na chochote tumeona hadi sasa. Sasa sisi kutumia data kama mkakati navigate muundo huu data. Na kama tunaweza kufuata mpango wa, kama tunaweza kufuata takwimu kutoka mwanzo hadi mwisho, tutaweza kujua kama takwimu ambazo zipo katika trie. 

Na kama hatuwezi kufuata ramani kutoka kwa maana ya kumaliza kabisa, data haiwezi kuwepo. Tena, funguo hapa ni uhakika kuwa ya kipekee. Na hivyo tofauti na meza hash, tutaweza kamwe kuwa na kushughulika na migongano hapa. Na hakuna vipande viwili vya data na hasa mpango wa sawa isipokuwa takwimu ambazo ni kufanana. 

Kama sisi kuingiza John, basi sisi kutafuta John. Hiyo ni vipande viwili kufanana ya data, kulia, sisi ni kuangalia kwa. Lakini vinginevyo, yoyote vipande viwili vya data uhakika wa kuwa na roadmaps kipekee kupitia muundo huu data. Na tunakwenda tuangalie Visual ya hii katika muda tu. 

Tutaweza kufanya hivyo kwa kujaribu kujenga muundo mpya data, ramani ifuatayo thamani jozi ufunguo. Katika kesi hiyo, sisi siyo kwenda kutumia kitu rahisi kama Boolean. Sisi kwa kweli itakuwa kuhifadhi kamba. Na kamba hiyo ni kwenda kuwa jina la chuo kikuu. 

Na ufunguo ni kwenda kuwa mwaka wakati chuo kikuu kuwa ilianzishwa. Miaka yote kwa vyuo vikuu ni kwenda kuwa tarakimu nne. Na hivyo tutaweza kutumia wale tarakimu nne kwa navigate kupitia muundo huu data. Na tutaweza kuona, tena, jinsi sisi kufanya hivyo katika haki ya pili. 

Mwishoni mwa njia, tutaona jina ya chuo kikuu kwamba sambamba kwa kuwa suala muhimu, tarakimu wale wanne. Wazo msingi nyuma ya trie ni tuna njia ya kati. Hivyo kufikiri juu yake kama mti. Na hii ni sawa katika herufi na katika dhana ya mti. Kwa ujumla wakati sisi kufikiri juu miti katika ulimwengu wa kweli, wana mizizi hiyo ni katika ardhi na wao kukua zaidi na wana matawi na wana majani. Na kimsingi wazo la trie ni sawa, ila kwa kuwa mizizi ni nanga mahali fulani katika anga. Na majani ni chini. 

Hivyo ni aina ya kama kuchukua mti na tu flipping kichwa chini. Lakini bado kuna matawi. Na wale itakuwa njia yetu, wale itakuwa uhusiano wetu kutoka mizizi kwa majani. Katika kesi hiyo, wale njia, matawi hayo ni kinachoitwa na tarakimu kuwa kutuambia ambayo njia ya kwenda kutoka ambapo sisi ni. 

Kama tunaona 0, sisi kwenda chini tawi hili, kama tunaona 1, sisi kwenda chini tawi hili, na hivyo na kadhalika. Naam, hii ina maana gani? Naam, hiyo ina maana kwamba katika kila hatua ya makutano na kila nodi katika katikati na kila tawi, kuna watu 10 iwezekanavyo maeneo ambayo tunaweza kwenda. Hivyo kuna kuyatumia 10 kutoka kila eneo. 

Na hii ni mahali ambapo inajaribu wanaweza kupata kidogo vitisho kwa mtu ambaye ni hana mengi ya uzoefu katika sayansi ya kompyuta kabla. Lakini inajaribu ni kweli pretty kutisha. Na kama una nafasi ya kufanya kazi pamoja nao na uko tayari kuchimba katika na majaribio na wao, wao ni kweli ya kuvutia kabisa miundo data kufanya kazi pamoja. Kama tunataka kuingiza kipengele ndani ya trie, kila tunahitaji kufanya ni kujenga njia sahihi kutoka mizizi kwa jani. Hapa ni nini kila hatua pamoja njia ili kuangalia kama. Tunakwenda kufafanua takwimu mpya muundo wa nodi mpya iitwayo trie. 

Na ndani ya takwimu kwamba muundo kuna vipande viwili. Tunakwenda kuhifadhi jina la chuo kikuu. Na tunakwenda kuhifadhi safu ya kuyatumia kwa nodes nyingine ya aina moja. Hivyo, tena, hii ni aina hiyo kwa dhana ya kila mahali sisi ni, sisi saa 10 iwezekanavyo maeneo tunaweza kwenda. Kama tunaona 0, sisi kwenda chini tawi hilo. Kama tunaona 1, tawi hili, na kadhalika na kadhalika na kadhalika. Tukisema 9, sisi kwenda chini tawi hilo. Hivyo katika kila hatua ya makutano, tunaweza kwenda 10 maeneo iwezekanavyo. Hivyo kila node ana vyenye kuyatumia 10 kwa nodes nyingine, hadi 10 nodes nyingine. 

Na data sisi ni hifadhi ni tu jina la chuo kikuu. Basi hebu kujenga trie. Hebu kuingiza wanandoa ya vitu ndani ya trie yetu. Hivyo katika sana juu, hii ni nodi mizizi yetu. Hii pengine ni kwenda kuwa kitu wewe ni kwenda kimataifa kutangaza. Na wewe ni kwenda duniani kudumisha pointer nodi hii daima. 

Wewe ni kwenda kusema, mzizi sawa, na uko kwenda malloc mwenyewe trie nodi. Na wewe kamwe kwenda kugusa mzizi tena. Kila wakati unataka kuanza punde kwa njia, kuweka pointer mwingine sawa na mizizi, kama vile trav, ambayo ni mfano mimi kutumia katika wengi wa video yangu hapa mwingi na foleni na orodha kiungo na kadhalika. 

Kuweka pointer mwingine aitwaye trav kwa traversal. Na matumizi trav navigate kwa njia ya muundo data. Basi hebu angalia jinsi hii ili kuangalia. Hivyo sasa hivi, nini haina nodi kuangalia kama? Naam, tu kama takwimu zetu muundo wa tamko unahitajika, tuna kamba, ambayo katika kesi hii ni tupu. Kuna kitu hapa. 

Na safu ya kuyatumia 10. Na hivi sasa, sisi tu 1 nodi katika trie hii. Kuna kitu kingine ndani yake. Hivyo yote 10 ya wale kuyatumia hatua kwa null. Hiyo ni nini nyekundu inaonyesha. 

Hebu kuingiza kamba Harvard. Hebu kuingiza Chuo Kikuu cha Harvard katika trie hii, ambayo ilianzishwa mwaka 1636. Tunataka kutumia ufunguo, 1636, kutuambia ambapo tuko kwenda kuhifadhi Harvard katika trie. Sasa, tunawezaje kufanya hivyo? 

Inaweza kuangalia kitu kama hiki. Sisi kuanza katika mizizi. Na tuna hizi maeneo 10 tunaweza kwenda. Mzizi ni kama yoyote nodi wengine wa trie. Kuna sehemu 10 tunaweza kwenda kutoka hapa. 

Ambapo kufanya sisi pengine wanataka kwenda kama ufunguo ni 1636? Kuna kweli chaguzi mbili. Kulia. Tunaweza kujenga muhimu kutoka kulia na kushoto na kuanza na 6. Au tunaweza kujenga muhimu kutoka kushoto na kulia na kuanza na 1. 

Ni pengine zaidi Intuitive kama mwanadamu kuelewa tutaweza tu kwenda kushoto na haki. Na hivyo kama nataka kuingiza Harvard katika trie hii, Mimi labda unataka kuanza na kuanzia saa mizizi, kuangalia chaguzi wangu 10 mbele yangu, na kusema Nataka kwenda chini 1 njia. SAWA. 

Sasa, 1 njia sasa null. Hivyo kama nataka kuendelea chini njia kwamba kuingiza kipengele hiki katika trie, Mimi na malloc nodi mpya, na 1 uhakika huko, na kisha mimi nina nzuri ya kwenda. 

Hivyo mimi kimsingi niko kwenye mahali ambapo mimi nina amesimama mizizi ya mti au trie na kuna matawi 10. Lakini kila tawi ina lango mbele yake. Kulia. Kwa sababu kuna kitu kingine kuna. Hakuna kifungu salama. Hiyo ina maana kwamba kuna kitu chini yoyote ya matawi hayo. Kama mimi nataka kuanza kujenga kitu, nataka kuondoa lango. Nataka kuondoa lango mbele ya namba 1. Na mimi nataka kutembea chini kwamba. Na mimi nataka kujenga mahali pengine kwa niende. 

Na kwamba ni nini mimi tumefanya hapa. Hivyo 1 tena pointi null. Nilivyosema ni salama kwenda chini hapa sasa. Mimi kujengwa nodi mwingine. Na wakati mimi kupata kwamba nodi, mimi kuwa uamuzi nyingine ya kufanya. Ambapo mimi kwenda kwenda kutoka hapa? 

Naam, nimekuwa tayari wamekwenda chini 1. Hivyo sasa mimi pengine wanataka kwenda chini 6. Kulia. Tena, nina maeneo 10 Naweza kuchagua. Basi hebu sasa kwenda chini namba 6. Hivyo mimi wazi mlango mbele ya namba 6. Na mimi kutembea chini pale. Na mimi kujenga nodi mwingine. Na nimekuwa imefikia hatua nyingine makutano. 

Tena, nina 10 uchaguzi kwa ambapo naweza kwenda. Nimekuwa wakiongozwa 1-6. Hivyo sasa mimi pengine wanataka kwenda 3. 3, kuna mahali pa siwezi kwenda. Hivyo nina kusafisha njia na kujenga mwenyewe nafasi mpya. Na kisha kutoka 3, ambapo mimi nataka kwenda? Nataka kwenda chini 6. 

Na, tena, nilikuwa na kusafisha njia ya kufanya hivyo. Hivyo sasa nimekuwa kutumika ufunguo wangu kuingiza kujenga nodes na kuanza kujenga trie hii. Nimeanza kwenye mizizi. Nimekuwa wamekwenda chini 1636. Na sasa mimi nina chini huko juu kwamba nodi. Na unaweza kuwa na uwezo wa kuona kwenye kioo. 

Ni yalionyesha katika njano. Hiyo ambapo mimi sasa niko. Ufunguo wangu ni kosa. Nimekuwa nimechoka kila nafasi katika ufunguo wangu. Hivyo siwezi kwenda yoyote zaidi. Hivyo katika hatua hii, wote mimi kweli wanahitaji kufanya ni kusema, sawa. Ni aina ya kama kuangalia chini ya ardhi, kama wewe ni envisioning mwenyewe kama aina hii ya njia wenye uhusiano tofauti. Aina ya kuangalia chini na aina ya dawa uchoraji Harvard juu ya ardhi. Hiyo ni jina la hii. Kujua kwamba ni nini katika eneo hili. Kama sisi kuanza katika mizizi na sisi kwenda chini 1 na kisha 6 na kisha 3 na kisha 6, ambapo ni sisi? Vizuri kama sisi kuangalia chini na tunaona Kikuu cha Harvard, kisha Tunajua kwamba Harvard alikuwa ilianzishwa mwaka 1636 kulingana na njia sisi ni utekelezaji wa muundo huu data. Ili kwamba ilikuwa hopefully moja kwa moja. Sisi ni kwenda kufanya insertions mbili zaidi. Na hopefully utakuwa msaada kwa kuona hii kufanyika mara mbili zaidi. 

Sasa, hebu kuingiza chuo kikuu mwingine. Hebu kuingiza Yale katika trie hii. Yale ilianzishwa mwaka 1701. Hivyo tutaweza kuanza saa mizizi, kama sisi daima kufanya. Na sisi kuweka traversal pointer. Tunakwenda kutumia kwamba hoja kwa njia ya. Jambo la kwanza tunataka kufanya ni kwenda chini 1 njia. Hiyo ni tarakimu ya kwanza ya ufunguo yetu. Kwa bahati nzuri, ingawa, hatufanyi una kufanya kazi yoyote wakati huu. Njia 1 imekwisha akalipa. Mimi akalipa ni awali wakati mimi ilikuwa kuingiza Harvard katika 1636. Hivyo siwezi salama hoja chini ya 1 na tu kwenda huko. Kama unaweza hoja chini 1. 

Hata hivyo, sasa nataka kwenda hadi 7. Mimi akalipa njia saa 6. Najua naweza salama kuendelea chini 6 njia. Lakini nahitaji kuendelea juu 7 njia. Basi je, mimi haja ya kufanya? Naam, tu kama kabla, mimi tu haja wazi mlango, kutoka nje ya njia, na kujenga nodi mpya kutoka 7 njia. Tu kama hii. 

Hivyo sasa nimekuwa wakiongozwa 1 na kisha 7. Na sasa taarifa, mimi nina aina ya juu ya subbranch hii mpya. Kulia. Kila kitu kingine kutoka 16 juu, mimi hawajali. Mimi si kufanya kitu chochote 16. Mimi nina kufanya 17 mambo ya ajabu. 

Hivyo sasa kutoka 17 na kuendelea, nina aina ya kuwaka trails mpya hapa. Tarakimu ijayo muhimu yangu ni 0. Mimi wazi hawawezi kupata mahali popote. I just kujengwa nodi hii. Hivyo najua hakuna njia mbele kutoka hapa. Hivyo nina kufanya moja mwenyewe. 

Hivyo mimi malloc nodi mpya na 0 hatua huko. Na kisha mara moja zaidi, mimi malloc nodi mpya na kuwa moja ya hatua huko. Tena, nimekuwa nimechoka ufunguo wangu, 1701. Hivyo mimi kuangalia chini na mimi dawa rangi Yale. Hiyo ni jina la nodi hii. 

Na hivyo sasa kama mimi milele haja ya kuona kama Yale ni katika trie hii, mimi kuanza katika mizizi, Mimi kwenda chini 1701, na kuangalia chini. Na kama mimi kuona Yale dawa walijenga kwenye ardhi, kisha Najua Yale ipo katika trie hii. Hebu kufanya moja zaidi. Hebu kuingiza Dartmouth katika hili trie, ambayo ilianzishwa mwaka 1769. 

Kuanza katika mizizi tena. Tarakimu wangu wa kwanza wa ufunguo wangu ni 1. Siwezi salama hoja chini njia hiyo. Ambayo tayari zipo. Tarakimu kijacho cha muhimu yangu ni 7. Siwezi salama hoja chini njia hiyo. Ipo pia. 

Yangu ijayo ni 6. Kutoka hapa, kutoka ambapo mimi sasa niko katika njano huko katika nodi kwamba katikati, 6 sasa imefungwa mbali. Kama Nataka kwenda chini njia hiyo, Nina kujenga mwenyewe. Hivyo mimi itabidi malloc nodi mpya na 6 hatua huko. Na kisha, tena, mimi nina mkali trails mwezi hapa. 

Hivyo mimi malloc nodi mpya ili kutoka kwamba node-- njia idadi 9-- na kisha sasa kama mimi kusafiri 1769, na mimi kuangalia chini. Kuna kitu kwa sasa dawa walijenga huko. Siwezi kuandika Dartmouth. Na nimekuwa kuingizwa DARTMOUTH katika trie. 

Hivyo hiyo ni kuingiza mambo ndani trie. Sasa tunataka kutafuta mambo. Je, sisi kutafuta mambo katika trie? Naam, ni wazo moja kiasi pretty. Sasa sisi tu kutumia ufunguo wa tarakimu ili kuona kama tunaweza kuvuka kutoka mzizi ambapo tunataka kwenda katika trie. 

Kama sisi kugonga maiti ya mwisho katika hatua yoyote, basi Tunajua kwamba kwamba kipengele hawawezi ipo au mwingine njia ambayo ingekuwa tayari akalipa. Kama sisi kufanya hivyo njia yote ya mwisho, kila tunahitaji kufanya ni kuangalia chini na kuona kama hiyo ni kipengele sisi ni kuangalia kwa. Kama ni, mafanikio. Kama siyo, kushindwa. 

Basi hebu kutafuta Harvard katika trie hii. Sisi kuanza katika mizizi. Na, tena, tunakwenda kujenga traversal pointer kufanya hatua yetu kwa ajili yetu. Kutoka mizizi tunajua kwamba nafasi ya kwanza tunahitaji kwenda ni 1, Tunaweza kufanya hivyo? Ndio tunaweza. Kama salama lipo. Tunaweza kwenda huko. 

Sasa, nafasi ya pili tunahitaji kwenda ni 6. Je 6 njia zipo kutoka hapa? Yeah, ni gani. Tunaweza kwenda chini 6 njia. Na sisi kuishia hapa. 

Tunaweza kwenda chini njia 3 kutoka hapa? Naam, kama ni zamu nje, ndiyo, kwamba ipo pia. Na tunaweza kupata katika njia 6 kutoka hapa? Ndio tunaweza. 

Sisi si kabisa akajibu swali bado. Bado kuna moja zaidi hatua, ambayo sasa ni tunahitaji kuangalia chini na kuona kama hiyo ni actually-- kama sisi ni kuangalia kwa Kikuu cha Harvard, ni kwamba nini tunaona baada ya sisi kuziondoa muhimu? Katika mfano sisi ni kutumia hapa, Miaka daima tarakimu nne. Lakini unaweza kuwa na kutumia mfano ambapo wewe ni hifadhi kamusi ya maneno. 

Na hivyo badala ya kuwa kuyatumia 10 kwa eneo yangu, unaweza kuwa na 26. Moja kwa kila barua ya alfabeti. Na kuna baadhi ya maneno kama popo, ambayo ni subset ya kundi, kwa mfano. Na hivyo hata kama wewe kupata Mwisho wa ufunguo na wewe kuangalia chini, wewe wanaweza kuona nini wewe ni kuangalia kwa. 

Hivyo daima kuwa traverse njia nzima na kisha kama ungekuwa na uwezo mafanikio traverse njia nzima, kuangalia chini na kufanya uthibitisho moja ya mwisho. Ni kwamba kile mimi nina kuangalia kwa? Naam, mimi kuangalia chini baada ya kuanza juu na kwenda 1636. Mimi kuangalia chini. Mimi naona Harvard. Kwa hiyo, ndiyo, mimi wamefanikiwa. Nini kama nini mimi kuangalia kwa si katika trie, ingawa. Nini kama mimi nina kuangalia kwa Princeton, ambayo ilianzishwa mwaka 1746. Na hivyo inakuwa muhimu yangu 1746 navigate kupitia trie. Naam, mimi kuanza katika mizizi. Na nafasi ya kwanza nataka kwa inakwenda chini 1 njia. Naweza kufanya nini? Ndiyo ninaweza. 

Naweza kwenda chini njia 7 kutoka huko? Naam, naweza. Ambayo ipo pia. Lakini siwezi kwenda chini 4 njia kutoka hapa? Hiyo ni kama kuuliza swali, wanaweza Mimi kuendelea chini kwamba mraba kidogo kwamba nimepata yalionyesha katika njano? Kuna kitu huko. Kulia. 

Kuna njia hakuna mbele chini 4 njia. Kama Princeton alikuwa katika trie hii, kwamba 4 ingekuwa akalipa kwa ajili yetu tayari. Na hivyo katika hatua hii tumekuwa kufikiwa mwisho wafu. Hatuwezi kwenda yoyote zaidi. Na hivyo tunaweza kusema, kipekee, hakuna. Princeton haipo katika trie hii. 

Basi nini hii yote ina maana gani? Kulia. Kuna mengi kinachoendelea hapa. Kuna kuyatumia kila mahali. Na, kama unaweza kuona tu kutoka mchoro, kuna mengi ya nodes kwamba ni aina ya kuruka karibu. Lakini taarifa kila wakati sisi alitaka kuangalia kama kuna jambo katika trie, sisi tu alikuwa na kufanya 4 hatua. 

Kila wakati sisi alitaka kuingiza kitu katika trie, tuna kufanya 4 hatua, pengine mallocing baadhi ya mambo njiani. Lakini kama tuliona wakati sisi kuingizwa DARTMOUTH katika trie, wakati mwingine baadhi ya njia huenda tayari kuwa na akalipa kwa ajili yetu. Na hivyo kama trie yetu anapata kubwa na kubwa zaidi, tuna kufanya kazi chini kila wakati kuingiza vitu vipya kwa sababu tumekuwa tayari kujengwa mengi ya kati matawi njiani. Kama sisi milele tu na kuangalia 4 mambo, 4 ni mara kwa mara. Sisi kwa kweli ni aina ya inakaribia mara kwa mara wakati insertion na mara kwa mara wakati Luke. Tradeoff, bila shaka, ikiwa ni kwamba trie hii, kama pengine unaweza kusema, ni kubwa. Kila moja ya nodes hizi unachukua nafasi kubwa mno. 

Lakini hiyo ni tradeoff. Kama tunataka kweli haraka kuingizwa, kufutwa kweli haraka, na chaguo-kweli haraka, inabidi una mengi ya data wanaruka kote. Tuna kutenga mengi ya nafasi na kumbukumbu kwa kuwa muundo wa data kuwepo. 

Na hivyo ndiyo tradeoff. Lakini inaonekana kama sisi anaweza kuwa kupatikana. Tunaweza wamegundua kwamba takatifu grail wa miundo data na kuingizwa haraka, kufutwa, na Luke. Na labda hii itakuwa muundo sahihi data kutumia kwa maelezo chochote sisi ni kujaribu duka. Mimi nina Doug Lloyd, hii ni cs50.