КЕВИН Шмид: Понекад, када се гради Програм, можда ћете желети да искористе Структура података познат као речнику. Речник мапе кључеви, који су обично ниске, на вредности, интс, слова, показивач на неки објекат, шта год желимо. То је баш као обичне речника Та карта речи кроз дефиницијама. 

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

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

За сада, хајде да претпоставимо да смо желите да користите стрингове као тастери. Хајде да причамо о једној могућности, структура података зове трие. Дакле, овде је визуелни приказ од Трие. 

Као што слика сугерише, трие је структура података дрво са чворови повезани заједно. Ми видимо да постоји јасно корен чвор са неке везе шири на остали чворови. Али шта сваки чвор се састоји од? Ако претпоставимо да смо складиштење кључеве са само алфабетски знаци, и ми не бринемо о капитализацији, Овде је дефиниција чвора који ће бити довољан. 

Објекат чији је тип струцт чвор има два дела зове податке и децу. Ми смо оставили део података као коментар да буде замењена компоненту Декларација кад струцт чвор је инкорпорирана у Ц програму. Део података чвора може бити Булова вредност која означава да ли или Не чвор представља завршетак од речника тастера или то може да буде стринг представља дефиницију једне речи у речнику. 

Ми ћемо користити насмејано лице да укаже Када се подаци присутан у чвор. Постоји 26 елемената у нашем деца низ, један индекс по абецедном карактера. Видећемо значај ово ускоро. 

Хајде да изблиза кореновог чвора у нашем дијаграму, која нема података у вези са њим, као што је приказано Одсуство ликом смајлија део података. Стрелице се протеже од делова деца арраи представљају нон-чвор показивачи на другим чворовима. На пример, стрелица протеже од Други елемент деце представља слово Б у речнику кључу. И у већем дијаграму ми га етикету са Б. 

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

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

Ми ћемо погледати на други индекс тада, индекс један, за Б. У принципу, ако има неки алфабетски знак Ц ми може да одреди одговарајућу место у деце низа коришћењем Калкулација овако. Могли смо користили већу децу Низ ако смо хтели да понудимо Лоок Уп тастера са ширег опсега карактера, као што је целокупном АСЦИИ скуп знакова. 

У овом случају, показивач у нашем низу деце у индекс један није нула. Зато ћемо наставити у потрази до кључног купатилу. Ако се икада срели нулл показивач на одговарајућем месту у деце Низ док смо прешао чворове, онда ћемо морати да кажемо да смо није могао наћи ништа за тај кључ. 

Сада ћемо узети другу писмо наш кључ,, а наставити након показивачи на овај начин док не до краја нашег кључа. Ако до краја без кључа удара било ћорсокаке, нулл показивачи, као што је овде случај, онда само морам да проверим још једну ствар. Да ли је то кључ заправо у речнику? 

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

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

Хајде да ставите кључ Зоолошки врт у нашој трие. Запамтите да насмејано лице на чвору могао одговарају у коду на једноставан Булова вредност која означава да зоо врт је у речнику или је могао одговарају више информација које смо желе да се друже са кључним зоолошком врту, као дефиницију реч или нешто друго. На неки начин, процес за уметање нешто у ТРИЕ је сличан гледајући нешто у трие. 

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

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

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

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

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

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

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

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

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

Запамтите да, када бирате податке структура за одређени задатак, ми треба да размислите о томе шта врсте операције структура података треба да Подршка и колико перформансе сваког од оних који операције нам је битно. Ове операције могу чак превазилазе само основни изглед горе и уметање. Претпоставимо да смо желели да спроведу неку врсту ауто-комплетан функционалност, много као Гоогле претраживач ради. То јест, вратити све кључеве и потенцијално вредности које имају дати префикс. 

Трие је јединствено користан за ову операцију. То је једноставно да вршите итерацију кроз трие за сваки карактер префикс. Баш као потражити операције, смо могли да пратимо савете карактер по карактер. Онда, када смо стигли на крај префикс, могли би поновити кроз преостали део структуре података јер сваки од тастера изнад ова тачка има префикс. 

Такође је лако добити овај унос по абецедном реду од елементи низа деце су поређане по абецедном реду. Дакле, надам се да ћете размотрити давање покушава пробати. Ја сам Кевин Шмид, а то је ЦС50. 

Ах, ово је почетак од пада. Жао ми је. Извините. Извините. Извините. 

Стрике четири. Ја сам напоље. Извините. Извините. Извините. Извини за израду особу која мора да уредите овај полуди. 

Извините. Извините. Извините. Извините. 

ПРЕДСЕДНИК 1: Браво. То је заиста добро урађено.