[Музички] Даг LLOYD: Значи ние сме во чекор поблизу и поблиску дека светиот грал на податоци структури, оној што ние може да се вметне во, избришете од, и се погледне нагоре во постојан време. Право. Тоа е вид на целта. Ние сакаме да бидеме во можност да се направи работи многу, многу брзо. 

Дали сме се најдов тука кога ние зборуваме за се обидува? Па, ајде да ги разгледаме. Па видовме неколку различни структури на податоци кои се справи со мапирање на т.н. парови клучните вредност, мапирање некои парче на податоци на некое друго парче на податоци за да знаеме каде да ја најдат информации во структурата. 

Така и за низа, на пример, Клучот е индексот на елементот или низа локација 0 или 1 низа и така натаму. А вредноста е на податоци која постои на тоа место. Значи она што се чува во низа 0? Она што се чува во низа 1 наспроти само 0 и 1, кој ќе биде на клучеви. 

Со хаш табелата е вид на истата идеја. Со хаш табелата, ние имаме овој хаш функција која генерира хаш кодови. Значи клучот е кодот хаш на податоците. И вредноста, особено ние разговаравме за врзувањето во видеото на хаш маси, е дека поврзана листа на податоци дека хашови на онаа hashCode. Право. Што е со поинаков пристап овој метод, иако? Што во врска со метод каде што Клучот е загарантирана да биде уникатен, за разлика од хаш табелата, каде што можевме заокружи со две парчиња на податоци го имаат истото hashCode. И тогаш ние треба да се справи со кои од било љубопитство или повеќе врзувањето по можност да го надминете овој проблем. 

Па сега можеме да гарантираме дека нашите клучни ќе биде уникатен. И што ако е нашата вредност само нешто што е лесно како вистински и лажни, кој ни кажува дали или не дека дел од информациите постои во структурата? Рационален број би можел да биде едноставно како малку. Реално тоа е веројатно бајт почесто од малку. Но, тоа е многу помал од чување можеби стринг 50-карактер, на пример. 

Толку обиди, слични на хаш маси, кои се комбинираат низи и поврзани листа, обиди се комбинираат низи, структури, како и совети заедно за да се сместат податоци во интересен начин кој е прилично различен од нешто што сум го видел досега. Сега ние ги користиме податоците како патоказ да се движите оваа податочна структура. И ако можеме да ги следат Патоказот, ако можеме да следете ги податоците од почеток до крај, ние ќе знае дали тие податоци постојат во Trie. 

И ако ние не може да се следи на картата од што значи да се стави крај на сите, податоците не може да постои. Повторно, тука се и клучеви гарантирано да биде уникатна. И така за разлика од хаш табелата, ние никогаш нема да мора да се справи со судири тука. И не постојат две делови на податоци имаат иста карта освен ако тие податоци се идентични. 

Ако ние внесете Јован, тогаш бараме Јован. Тоа е две идентични парчиња податоци, право, ние сме во потрага преку. Но во спротивно, било две парчиња на податоци гарантира да имаат уникатни патоказите Преку оваа структура на податоци. И ние ќе треба да ги разгледаме во визуелна од ова во само еден миг. 

Ние ќе направите доколку се обидете да се создаде една нова структура на податоци, мапирање на следните клучни вредност парови. Во овој случај, ние нема да ги користат нешто толку едноставно како рационален број. Ние, всушност, ќе се сместат на стрингот. И таа низа ќе да биде името на еден универзитет. 

И клучот ќе биде година кога тој универзитет е основана. Сите години за универзитетите се ќе биде четири цифри. И така ќе ги користат овие четири бројки движите низ оваа податочна структура. И ќе видиме, повторно, како ние сторат тоа во само една секунда. 

На крајот на патот, ќе видиме името на универзитетот, кој одговара за тој клуч, тие четири цифри. Основната идеја зад Trie е дека имаме една централна рута. Значи мислам за тоа како дрво. А тоа е слично со правопис и во концептот на дрво. Општо земено, кога ќе помислиме дрвја во реалниот свет, тие имаат корен, што е во земјата и тие растат нагоре и тие имаат филијали и тие имаат лисја. И во основа на идејата за на Trie е иста, освен дека коренот е укотвен некаде на небото. А лисјата се на дното. 

Така, тоа е вид на како земање на дрвото и едноставно нервира тоа наопаку. Но се уште има гранки. И оние кои се 'би било патишта, тие ќе бидат во нашите врски од коренот на лисјата. Во овој случај, тие патеки, оние гранки се означени со бројки кои ни кажуваат на кој начин да се оди од каде што сме. 

Ако гледаме 0, ние одиме надолу оваа гранка, ако гледаме 1, ние одиме надолу оваа гранка, и така и така натаму. Па, она што значи тоа? Па, тоа значи дека во секоја крстосница точка и секој јазол во среден и секоја гранка, постојат 10 можни места кои можеме да одиме. Па има 10 совети од секоја локација. 

И ова е местото каде што се обидува да се добие малку застрашувачки за некој кој е нема многу искуство во компјутерската наука порано. Но обиди се навистина прилично страшно. И ако ја имате шанса да работат со нив и ако не сте подготвени да се копа во и да експериментирате со нив, тие се навистина доста интересно структури на податоци за работа со. Ако сакаме да го внесете елемент во Trie, сите ние треба да направите се изгради точната патека од коренот на лист. Тука е она што секој чекор начинот на кој може да изгледа. Ние ќе треба да се дефинира нова податоци структура за нов јазол наречен Trie. 

И во внатрешноста на тие податоци структура постојат две парчиња. Ние ќе треба да се сместат на името на еден универзитет. И ние ќе треба да се сместат низа од покажувачи до други јазли од истиот тип. Значи, повторно, ова е тој вид на концептот на секаде да сме, со почеток во 10 можни места можеме да одиме. Ако гледаме 0, ние одиме надолу оваа гранка. Ако гледаме 1, оваа гранка, и така натаму и така натаму и така натаму. Ако речеме 9, ние одиме надолу оваа гранка. Значи во секој раскрсницата точка, можеме да одиме 10 можни места. Така што секој јазол мора да содржи 10 совети до други јазли, до 10 други јазли. 

И податоците што сте чување е само името на универзитетот. Значи, да се изгради Trie. Ајде да внесете неколку на предмети во нашата Trie. Значи, во самиот врв, ова е нашиот корен јазол. Ова е веројатно нема да биде нешто ви се случува да глобално прогласи. И ви се случува да глобално одржување покажувач на овој јазол секогаш. 

Ви се случува да се каже, Коренот е еднакво, а ти си случува да се Примерок Trie јазол. И никогаш не си оди да се допре корен повторно. Секој пат кога ќе сакате да го почнете со навигацијата низ, ќе се постави уште еден покажувач еднаква на корен, како што се trav, што е примерот, јас се користи во многу од моите видеа овде на Купишта и редици и линк листи и така натаму. 

Ќе се постави уште еден покажувач наречен trav за traversal. И да ги користите за да отидете trav во структурата на податоци. Да видиме како тоа може да изгледа. Па сега, она што чини еден јазол изгледа? Добро, исто како нашите податоци декларација структура е наведено, имаме низа, која во овој случај е празна. Нема ништо тука. 

И низа од 10 покажувачи. И сега, ние само 1 јазол во оваа Trie. Нема ништо друго во неа. Така што сите 10 од нив покажувачи точка на нула. Тоа е она што на црвениот покажува. 

Ајде да внесете стрингот Харвард. Ајде да внесете универзитет на Харвард во оваа Trie, која е основана во 1636 година. Ние сакаме да го користите копчето, 1636 година, за да ни кажете каде сме ќе се сместат Харвард во Trie. Сега, како би можеле да го направите тоа? 

Тоа може да изгледа нешто како ова. Се вклучуваме во коренот. И ние имаме овие 10 места можеме да одиме. Коренот е само како и секој друг јазол на Trie. Има 10 места можеме да одиме од тука. 

Каде сме ние веројатно сакате да се оди ако клучот е во 1636 година? Има навистина две опции. Право. Може да се изгради на клучот од десно кон лево и да почне со 6. Или ние може да се изгради на клучот од лево кон десно и да почне со 1. 

Тоа е веројатно повеќе интуитивен како човечко суштество да ги разбираме ќе Само оди лево кон десно. И така, ако сакам да внесете Харвард во оваа Trie, Јас веројатно ќе сакате да започнете со почеток во коренот, гледа во моите 10 опции пред мене и рече: Сакам да одам по патот 1. ВО РЕД. 

Сега, 1 пат е моментално ништовни. Па ако сакам да се продолжи по тој пат да го вметнете овој елемент во Trie, Морам да Примерок нов јазол, 1 укажуваат таму, а потоа јас сум добро да отидевме. 

Па јас во основа сум во точка каде Стојам во коренот на дрвото или Trie и има 10 експозитури. Но секоја гранка има портата пред него. Право. Затоа што нема ништо друго нема. Нема безбедно минување. Тоа значи дека нема ништо одредување на било која од овие гранки. Ако сакам да се започне изградба на нешто, сакам да се отстрани портата. Сакам да се отстрани на портата во предниот дел на број 1. И сакам да одиме по тоа. И јас сакам да се изгради на друго место за да одам. 

И тоа е она што го направив тука. Па 1 веќе не укажува на нула. Сум рече дека е безбедно да одат надолу тука сега. Јас ја направив друг јазол. И кога ќе се дојде до тој јазол, јас имаат уште една одлука. Каде сум јас ќе одам од тука? 

Па, јас сум веќе слезе на 1. Па сега јас најверојатно сакаат да одат надолу по 6. Право. Повторно, имам 10 локации, јас може да се избере. Па ајде сега оди надолу бројот 6. Па јас го исчистите портата во предниот дел на број 6. И јас одам таму. И јас се изгради уште еден јазол. И јас сум стигна до уште една крстосница точка. 

Повторно, имам 10 избори за местото каде што може да оди. Сум се преселил 1-6. Па сега јас веројатно сакаат да одат на 3. 3, нема никаде можам да одам. Па морам да се расчисти патот и јас се изгради нов простор. А потоа од 3, кога сакам да се оди? Сакам да одам надолу 6. 

И, повторно, јас морав да го расчисти патот за да го направи тоа. Па сега јас сум користел мојот клуч за да вметнете создаде јазли и да почне да се изгради оваа Trie. Почнав во коренот. Сум слезе 1636. И сега сум на дното таму на тој јазол. А вие може да биде во можност да го гледате на вашиот екран. 

Тоа е обележана со жолто. Тоа е каде што во моментов сум. Мојот клуч е направено. Сум исцрпени секоја позиција во мојот клуч. Па не може да одат понатаму. Па во овој момент, се што можам навистина треба да направите е да се каже, во ред. Тоа е вид на како да се гледа долу на земјата, ако сте се предвидува себеси како овој вид на патот со различни конекции. Вид на гледајќи надолу и вид на спреј сликарство Харвард на теренот. Тоа е името на оваа. Знам дека е она што е на оваа локација. Ако тргнеме од корен и се спуштаме 1 и потоа 6, а потоа 3, а потоа 6, каде сме ние? Па ако се погледне надолу и можеме да видиме на Харвард, а потоа ние знаеме дека Харвард беше основана во 1636 година врз основа на начинот ние спроведување на оваа податочна структура. Така што се надевам дека беше јасна. Ние ќе треба да се направи уште две инсерции. И се надевам дека тоа ќе ви помогне да се види ова направено два пати повеќе. 

Сега, ајде да внесете друг универзитет. Ајде да внесете Јеил во оваа Trie. Јеил е основана во 1701. Значи, ние ќе започне во корен, како што секогаш го правам. И ние се постави traversal покажувачот. Ние ќе треба да го користите дека за да ја поминете. Првото нешто што сакаме да направите е да отидете на патот 1. Тоа е првата цифра од нашите клучни. За среќа, иако, ние не треба да се направи некоја работа тоа време. 1 пат веќе е расчистено. Јас го расчисти претходно кога јас беше вметнување Харвард во 1636 година. Па јас безбедно да се движат по 1 и само да одиме таму. Ако може да се движи надолу по 1. 

Сега, сепак, сакам да одам до 7. Јас го отвори патот на 6. Знам јас безбедно продолжи по патот 6. Но, јас треба да се продолжи на патот 7. Значи она што треба да направам? Па, како и порано, јас само треба да го исчистите од портата, се надвор од патот, и да се изгради нов јазол од патот 7. Исто како и оваа. 

Па сега јас сум се пресели 1 и потоа 7. И сега се забележи, јас сум вид на оваа нова subbranch. Право. Сè друго од 16 па натаму, јас не се грижат за. Јас не го правам 16 ништо. Јас го правам 17 нешта. 

Па сега, од 17 на, морам да вид на пожарот нови патеки тука. Следната цифра мојот клуч е 0. Јас очигледно не може да се секаде. Јас само го изградивме овој јазол. Па знам дека нема патеки напред од тука. Па морам да се направи еден себе. 

Па јас Примерок нов јазол и 0 точка таму. А потоа уште еднаш, јас Примерок на нов јазол и да имаат една точка таму. Повторно, јас сум исцрпена мојот клуч, 1701. Па јас се погледне надолу и јас спреј бои Јеил. Тоа е името на овој јазол. 

Па сега ако некогаш треба да се види дали на Јеил е во оваа Trie, почнувам во коренот, Одам долу 1701 година, и се погледне надолу. И ако видам Јеил спреј насликани врз земјата, а потоа Знам Јеил постои во овој Trie. Да направиме уште еден. Ајде да внесете Дартмут во оваа Trie, која беше основана во 1769. 

Започне во коренот повторно. Мојата прва цифра од клучните ми е 1. Јас безбедно да се движат надолу по патот. Што веќе постои. Следната цифра на клучните ми е 7. Јас безбедно да се движат надолу по патот. Таа постои, како и. 

Мојата следна е 6. Од тука, од каде што во моментов сум во жолта таму во тој среден јазол, 6 е во моментов заклучени надвор. Ако сакам да одам по тој пат, Морам да го изгради себе. Па јас ќе Примерок нов јазол и имаат 6 точка таму. А потоа, повторно, јас сум пламнал нови патеки тука. 

Па јас Примерок нов јазол, така што од дека node-- број 9-- патот и тогаш сега ако јас се патува 1769, и јас се погледне надолу. Нема ништо во моментов испишаа таму. Јас можам да пишувам Дартмут. И јас сум вметната Дартмут во Trie. 

Значи тоа е вметнување работите во Trie. Сега сакаме да го бара за нешта. Како ние да пребарување за работи во Trie? Па, тоа е прилично многу исти идеја. Сега ние само користење на бројки на клучните да видиме дали може да се движите од коренот до каде што сакаат да одат во Trie. 

Ако ние хит ќорсокак во кој било момент, а потоа ние знаеме дека тој елемент не може да постои или на друго место тој пат би Веќе е расчистено. Ако ние се направи сето тоа на начин да се На крајот, сите ние треба да направите е да се погледне надолу и да видат дали тоа е елементот што ја барате. Ако е така, успех. Ако тоа не е, не успеваат. 

Значи, да се бара за Харвард во овој Trie. Се вклучуваме во коренот. И, повторно, ние ќе треба да создаде traversal покажувачот да не ни се движи кон нас. Од коренот, ние знаеме дека прво место ние треба да одиме е 1, можеме да го направите тоа? Да ние можеме. Ако безбедно постои. Можеме да одиме таму. 

Сега, следниот место ние треба да одиме е 6. Патот 6 Дали постои од тука? Да, тоа го прави. Можеме да одиме по патот 6. И на крајот ќе заврши тука. 

Можеме да одиме по патот 3 од тука? Па, како што излезе, Да, тоа постои премногу. И може да се добие на патот 6 од тука? Да ние можеме. 

Ние не сме сосема одговори уште на прашањето. Сеуште постои уште еден чекор, кој сега е ние треба да се погледне надолу и види дали тоа е actually-- ако ние сме во потрага по Харвард, е тоа што она што го наоѓаме откако ќе се исцрпат клуч? Во примерот ние користиме овде, на годините се секогаш четири цифри. Но можеби ќе биде со користење на пример, каде што сте складирање речник на зборови. 

И така, наместо да има 10 совети за мојата локација, може да имаат 26. По еден за секоја буква од азбуката. И има некои зборови како лилјак, кој е подмножество на серија, на пример. Па дури и ако се дојде до крајот на копчето и ќе се погледне надолу, што не може да се види она што сте во потрага за. 

Значи секогаш треба да напречни на целиот пат, а потоа ако сте биле во можност успешно за напречни целиот пат, погледне надолу и направи една конечна потврда. Е дека она што јас го барате? Па, јас се погледне надолу по започнувањето на врвот и ќе 1.636. Гледам надолу. Гледам Харвард. Значи, да, ми успеа. Што ако она што го барам не е во Trie, иако. Што ако јас сум во потрага за Принстон, која е основана во 1746 година. И така 1746 станува мојот клуч да се движите низ Trie. Па, јас се почне од корен. И на прво место што сакам да оди по патот 1. Можам да го направам тоа? Да можам. 

Јас можам да одам по патот 7 од таму? Да, можам. Која постои премногу. Но, можам да одат надолу по 4 пат од тука? Тоа е како да го поставува прашањето, може Јас се продолжи по тој малиот плоштад што сум осветлени во жолто? Таму нема ништо. Право. 

Не постои начин да се оди по патот 4. Ако Принстон беше во овој Trie, дека 4 би бил ослободен за нас веќе. И така во овој момент ние сме достигнаа ќорсокак. Ние не можеме да одиме понатаму. И така може да се каже, дефинитивно, не. Принстон не постои во овој Trie. 

Значи она што не сето ова значи? Право. Има многу се случува тука. Има покажувачи сите над местото. И, како што може да се види само од дијаграмот, има голем број на јазли кои се вид на летаат наоколу. Но информации во секое време сакавме да провери дали нешто не е во Trie, ние само требаше да се направат 4 потези. 

Секој пат кога сакавме да внесете нешто во Trie, треба да се направи 4 потези, можеби mallocing некои работи на патот. Но, како што видовме, кога ние вметната Дартмут во Trie, понекогаш и некои од патот веќе може да биде ослободен за нас. И така како што е нашата Trie добива се поголем и поголеми, имаме направи помалку работа во секое време да внесете нови работи бидејќи ние сме веќе изградено многу од средно гранки на патот. Ако ние само некогаш мора да се погледне 4 нешта, 4 е само постојана. Ние навистина се вид на приближување постојана време вметнување и постојана време пребарување. Губитокот, се разбира, е во тоа што оваа Trie, како што веројатно може да се каже, е огромна. Секој еден од овие јазли зазема многу простор. 

Но, тоа е Губитокот. Ако сакаме навистина брзо вметнување, навистина брзо бришење, и навистина брзо пребарување, ние треба да имате голем број на податоци летаат наоколу. Ние треба да се издвои многу простор и меморијата за таа податочна структура да постои. 

И така тоа е Губитокот. Но, изгледа дека ние може да го најде. Ние би можеле да се покажа дека Светиот грал на структури на податоци со брз вметнување, бришење и пребарување. А можеби и ова ќе биде соодветна структура на податоци да се користи за било која информација ние се обидуваме да ги чувате. Јас сум Даг Лојд, ова е CS50.