[Мусиц плаиинг] Даг Ллоид: Тако смо корак по корак ближе и ближе да свети грал података структуре, који можемо убацити у, брисање из, и погледај у сталном време. Jel tako. То је врста циља. Желимо да будемо у стању да уради ствари врло брзо. 

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

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

Са хасх табели је врста исте идеје. Са хеш табели, имамо ову хасх функција која генерише хасх кодове. Дакле, кључ је тараба код података. А вредност, посебно причали смо о цхаининг у споту за хеш табелама, је да линкед лист података да хасхес том хасхЦоде. Jel tako. Шта је са другом приступу овај метод, ипак? Шта је метод где Кључ је гарантовано да буду јединствени, за разлику од хасх табеле, где смо могли завршити са два комада података има исти хасхЦоде. И онда морамо да се баве да је било сондирање или више пожељно цхаининг да поправимо тај проблем. 

Тако да сада можемо гарантовати да ће наш кључни бити јединствена. А шта ако је наша вредност била само нешто тако лако као истинито и лажно да нам каже да ли или не да податак постоји у структури? Боолеан може бити тако једноставно као мало. Реално то је вероватно бите чешће него мало. Али то је много мањи од складиштење можда низ од 50 карактера, на пример. 

Тако покушаја, слично хасх табеле, који комбинују низови и повезане листе, покушава комбинују низова, структура и показивачи заједно за складиштење података у занимљив начин на који је прилично разликује од шта смо до сада видели. Сада користимо податке као путоказ навигацију ову структуру података. А ако можемо да пратимо мапа пута, ако можемо прати податке из почетка до краја, ми ћемо знам да ли тих података постоје у Трие. 

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

Ако убаците Јохн, онда трагамо за Јовану. То су два идентична комада података, десно, гледамо кроз. Иначе, било два комада података су гарантовано да имају јединствене мапе пута кроз ову структуру података. И ми ћемо да погледамо визуелна ово за тренутак. 

Ми ћемо учинити тако што покушава да створити нову структуру података, мапирање следеће кључне вредности парова. У том случају, нећемо користити нешто тако једноставно као Боолеан. Ми ћемо заправо сачувате стринг. И то ће се низ бити име универзитета. 

А кључ ће бити година када је основан тај универзитет. Све година за универзитете ће бити четири цифре. И тако ћемо користити те четири цифре до кретање кроз ову структуру података. И видећемо, опет, како ми то радимо за секунд. 

На крају пута, видећемо име универзитета који одговара том кључу, та четири цифре. Основна идеја иза Трие је имамо централни пут. Дакле, размислите о томе као дрво. И то је слично у правопису и концепта до дрвету. Генерално, када размишљамо о дрвеће у стварном свету, имају корен који је у приземље и они расту увис и они имају филијале и имају лишће. И у основи идеја трие је потпуно исти, осим што корен усидрена негде на небу. И листови су на дну. 

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

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

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

И унутар тих података Структура постоје два комада. Идемо чувања резултата назив универзитета. И ми ћемо да сачувате низ показивача то другим чворовима истог типа. Дакле, опет, ово је та врста од концепта свуда смо, на 10 могуће места можемо да идемо. Ако видимо 0, идемо доле ову грану. Ако видимо 1, ова грана, и тако даље и тако даље и тако даље. Ако кажемо 9, идемо доле ову грану. Дакле, у сваком тренутку чвор, можемо да идемо 10 могућих места. Дакле, сваки чвор мора да садржи 10 савете другим чворовима, до 10 осталих чворова. 

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

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

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

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

Хајде да убаците низ Харвард. Хајде да убаците Универзитет Харварду у овом Трие, која је основана у 1636 години. Желимо да користите тастер, 1636, да нам кажеш где смо да чувате на Харварду у Трие. Сада, како би ми то радимо? 

То може да изгледа отприлике овако. Почињемо у корену. И ми имамо тих 10 места можемо да идемо. Корен је као било који други чвор Трие. Постоји 10 места можемо да идемо одавде. 

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

Вероватно више је интуитивно као људско биће Ми разумемо да ће Само идите с лева на десно. И тако ако желите да унесете Харварду у овом Трие, Вероватно Желим да почнем почевши у корену, гледајући својих 10 опција испред мене, и говорећи Желим да идем доле 1 пут. ОК. 

Сада, 1 пут је тренутно нула. Дакле, ако желим да наставимо тим путем да убаците овај елемент у Трие, Морам да маллоц нови чвор, имају 1 бод, а онда добро сам да идем. 

Тако да сам у суштини сам на тачка у којој стојим у корену дрвета или на трие и има 10 филијала. Али, свака грана има капија испред њега. Jel tako. Јер нема ничег другог нема. Не сигуран пролаз. То значи да нема ништа било који од тих грана. Ако желим да почнемо да градимо нешто, желим да уклоните капију. Желим да уклоните врата испред број 1. И желим да прошетате то. И желим да изградим друго место за мене да одем. 

И то је оно што сам урадио овде. Дакле, 1 више не указује на нулл. Ја сам рекао да је сигурно да се овде сада. Ја сам изградио још један чвор. И када дођемо до тог чвора, ја још један одлуку. Где ћу да одем одавде? 

Па, ја сам већ отишао низ 1. Тако да сада вероватно желе да иду доле 6. Jel tako. Опет, имам 10 локација могу изабрати. Дакле, идемо сада доле број 6. Тако сам јасно капију испред број 6.. И хода тамо доле. И изградити још један чвор. И ја сам дошао до другог тачка спајања. 

Опет, имам 10 изборе јер тамо где могу да идем. Преселио сам се од 1 до 6. Тако да сада вероватно желе да иду у 3. 3, нигде Могу да одем тамо је. Зато морам да очисти пут и изградити себи нови простор. А онда од 3 где желим да идем? Желим да идем доле 6. 

И, опет, морао сам да утре пут за то. Дакле, сада сам користио кључ за уметање створи чворови и почети да гради ову трие. Почео сам у корену. Ја сам сишао 1636. И сада сам на дну тамо на том чвору. А ти би могао да погледајте га на екрану. 

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

Сада, хајде да убаците други универзитет. Хајде да убаците Иале у овом Трие. Јејл је основан 1701. Тако ћемо почети на корен, као што увек радим. И сет смо Траверсал показивач. Ми ћемо користити да бисте се кретали кроз. Прва ствар коју желите да урадимо је да одемо доле 1 пут. То је прва цифра од наших кључних. Срећом, међутим, не знамо треба да урадите било који посао овај пут. 'Тхе 1 пут већ ситуацију. Ја спашава ситуацију раније када сам је убацивање Харвард у 1636. Тако да безбедно могу да се померим довн 1 и само иди тамо. Ако може да се креће низ 1. 

Сада, међутим, желим да идем у 7. Ја отворио је пут у 6. Знам да могу безбедно наставити низ 6 пут. Али морам да наставите на 7 путу. Дакле, шта треба да урадим? Па, као и раније, само ми треба Да бисте обрисали капију, изаћи на путу, и изгради нови чвор са 7 путу. Баш овакав. 

Дакле, сада сам се преселио 1, а затим 7. И сада приметио, некако сам од на овом новом суббранцх. Jel tako. Све остало од 16 , ја не стало. Ја не радим ништа 16. Ја радим 17 ствари. 

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

Тако сам Маллоц нови чвор и има 0 праву. И онда још једном, ја маллоц нови чвор и имају једном тренутку. Опет, ја сам исцрпљена кључ, 1701. Тако да сам погледа доле и спреј Иале. То је име овог чвора. 

И сада ако икада треба да видимо да ли Иале је у овом Трие, почнем у корену, Ја паднем 1701. године, а гледај доле. И ако видим Иале спреј насликао на земљу, а затим Знам Јејл постоји у овом Трие. Хајде да урадимо још један. Хајде да убаците ДАРТМОУТХ у ово трие, која је основана 1769. године. 

Почните у корену поново. Мој први цифра мог кључа је 1. Ја сигурно могу да се померим тим путем. То већ постоји. Следећи цифра мог кључа је 7. Ја сигурно могу да се померим тим путем. Постоји такође. 

Мој следећи је 6. Одавде, одакле сам тренутно у жутом тамо у тој средини чвора, 6 тренутно закључана искључен. Ако желим да идем тим путем, Морам да га изгради себе. Зато ћу маллоц нови чвор и има 6 праву. А онда, опет, ја сам букти нове стазе овде. 

Тако сам Маллоц нови чвор, тако да од да ноде-- број пут 9-- а сада ако путујем 1769, и погледам доле. Нема ништа тренутно спреј тамо сликао. Могу да напишем Дартмоутх. И ја сам уметнута Дартмоутх у Трие. 

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

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

Дакле, хајде да тражи Харварду у овом Трие. Почињемо у корену. И, опет, идемо у створити Траверсал показивач да радимо свој покрете за нас. Из корена знамо да је Прво место морамо да идемо је 1, можемо то урадити? Да ми можемо. Ако безбедно постоји. Можемо отићи тамо. 

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

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

Нисмо баш одговорио ипак питање. Има још још један корак, који је сада морамо да погледа доле и видим да ли је то стварно-- ако тражимо Харварду, да шта ћемо наћи након што исцрпи кључ? У примеру који користимо овде, Године су увек четири цифре. Али, можда користите пример где Ви складиштење речник речи. 

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

Дакле, увек морате да пролазе цео пут и онда ако сте били у могућности успјешно да пролазе кроз целу стазу, погледај доле и направити једну коначну потврду. Да ли је то оно што тражим? Па, ја гледај доле након почетка на врху и иде 1636. Гледам доле. Видим Харвард. Дакле, да, успео сам. Шта ако оно што тражим није у Трие, мада. Шта ако тражим Принцетон, која је основана 1746. И тако 1746 постаје мој кључ да бисте се кретали кроз Трие. Па, да почнем у корену. И прво место желим да иде доле 1 пут. Могу то да урадим? Да могу. 

Могу ли да идем доле 7 пута од тамо? Да, могу. То постоји превише. Али могу да идем доле 4 пута од овде? То је као да питате питање, могу Да наставим низ тај мали трг да сам истакнут жутом бојом? Тамо нема ничега. Jel tako. 

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

Дакле, шта све ово значи? Jel tako. Много се овде дешава. Има показивачи су посвуда. И, као што можете видети Управо из дијаграма, има много чворова који на неки начин лете около. Али приметити сваки пут смо желели да проверите да ли нешто није у Трие, смо имали само да 4 потезе. 

Сваки пут смо желели да убаците нешто у Трие, морамо да направимо 4 потезе, евентуално маллоцинг неке ствари успут. Али, као што смо видели кад смо убаци Дартмоутх у Трие, Понекад неки путање можда већ одобрење за нас. И тако наш трие постаје све већа и већи, имамо учинити мање посла сваки пут да убаците нове ствари јер смо већ изградила много средњи гране на путу. Ако се само икада морати да погледате 4 ствари, 4 је само константа. Заиста смо некако приближава константа време уметање и константно време ИП адресу. Традеофф, наравно, будући да ово трие, као што вероватно може рећи, је огромна. Сваки од ових чворова заузима пуно простора. 

Али то је компромис. Ако желимо стварно брзо уметање, стварно брзо брисање, и заиста брзо ИП адресу, морамо да има доста података лете около. Морамо да издвоји доста простора и меморија за те структуре података da postoji. 

И то је компромис. Али изгледа да смо Можда су га нашли. Можда смо открили да свети грал структура података са брзим уметања, брисање, и ИП адресу. И можда ће бити одговарајућа структура података користити за све информације покушавамо да продавницу. Ја сам Доуг Ллоид, ово је ЦС50.