KEVIN SCHMID: Понякога, когато изграждането на програма, може да искате да използвате по- структура на данните, известен като речник. Речник карти ключове, които са обикновено струни, до стойности, цели числа, символа, указател към някакъв обект, каквото си искаме. Това е точно като обикновените речници че картата думи чрез определения. 

Речници ни предоставите Възможност за съхраняване на информация свързани с нещо и го гледам по-късно. И така, как ние всъщност приложи речник в, да речем, C код, който ние можем да използвате в една от нашите програми? Е, има много начини, по които бихме могли да приложат речник. 

От една страна, бихме могли да използваме масив, който ние динамично повторно размер или бихме могли да използвате свързан списък, хеш таблица или двоичен дърво. Но каквото и да изберете, ние трябва да бъдат съпричастни на ефективността и представяне на изпълнението. Ние трябва да мислим за използвания алгоритъм да вмъкнете и погледнете нагоре елементи в нашата структура данни. 

За сега, нека да приемем, че ние искате да използвате низове като ключове. Нека поговорим за една възможност, структурата на данните нарича Trie. Така че тук е визуално представяне на Trie. 

Тъй като на снимката подсказва, а Trie е с дървовидна структура на данните с възли, свързани заедно. Виждаме, че има ясно корен възел с някои връзки, простиращи се други възли. Но какво означава всеки възел се състои от? Ако приемем, че ние сме съхранение на ключове само с буквени знаци, и ние не се грижи за капитализация, тук е определение на възел, който ще са достатъчни. 

Един обект, чийто тип е структурата възел има две части нарича данни и деца. Ние сме лявата част на данни като коментар да бъдат заменени от компонент декларация, когато структурата на възел е включено в програма C. Част на данни възел може да бъде Булева стойност да се посочи дали или не възел представлява завършване на речник ключ или тя може да бъде низ представлява определението на дума в речника. 

Ние ще използваме усмивка на лицето да посочи когато данните се намира в един възел. Има 26 елементи в този деца масив, един форум на буква от азбуката. Ще видим значението на това скоро. 

Нека да погледнем по-отблизо на корен възел в нашата схема, която няма данни свързани с нея, както е посочено от отсъствие на усмихнато се изправи в порция данни. Стрелките, простиращи се от части на децата масиви представляват не-възел указатели към други възли. Например, стрелката, простираща се от вторият елемент на деца представлява буквата B в основен речник. И в по-голямата схема ние го надпишете с B. 

Имайте предвид, че в по-голямата схема, когато изготвя указател към друг възел, тя Няма значение, когато стрелката отговаря, че друг възел. Нашата проба Trie речник съдържа две думи, че и мащабиране. Да минеш през един пример за погледна данни за ключ. 

Да предположим, че ние искахме да се запознаете с съответстваща стойност за ключов баня. Ще започнем нашия поглед нагоре В основата възел. След това ние ще направим първата буква от нашата ключ, B, и намерите съответния място в нашия деца масив. Забележете, че има точно 26 точки в масива, една за всяка буква от азбуката. И ние ще имаме петната представляват букви от азбуката в ред. 

Ние ще разгледаме втория индекса тогава, един индекс, за Б. Като цяло, ако има някои азбуката C ние може да се определи съответното място в деца масив, използвайки изчисление по този начин. Ние би могъл да използва по-голям деца масив, ако искахме да предложим поглед нагоре на ключове с по-широк диапазон от символи, като цялата Настроите ASCII характер. 

В този случай, на показалеца в нашата детска масив в Индекс на един не е нищожна. Така че ние ще продължим да търсим до ключ баня. Ако някога сме се сблъска с нулев указател на правилното място при децата масив, докато ние се премества възлите, тогава ние ще трябва да се каже, че ние Не можах да намеря нищо за този ключ. 

Сега, ние ще вземем второто писмо на Основният ни, A, и да продължи след указатели по този начин, докато ние стигнете до края на нашия ключ. Ако стигнете до края на ключа, без да удря всички задънени улици, нулеви указатели, какъвто е случаят тук, тогава можем само Трябва да проверя още едно нещо. Дали това действително ключ в речника? 

Ако е така, ние трябва да се намери стойност, както е усмивка икона лице в нашата диаграма, където думата завършва. Ако има нещо друго, съхранява с данните, а след това можем да го върнат. Например, ключовата зоологическата градина не е в речник, въпреки че бихме могли да имаме достигнала края на този ключов, без изобщо да удря нулев указател, докато ние превъртите през TRIE. 

Ако се опитаме да погледнем нагоре ключовата баня, второ да индексира масив миналата възлова точка, съответстваща на буквата Н, би са заемали нулев указател. Така баня не е в речника. И така Trie е уникален с това, ключовете никога не са изрично съхранява в структурата на данните. Така че как можем да вмъкнете нещо в Trie? 

Нека поставете ключа зоологическа градина в нашата Trie. Не забравяйте, че една усмивка на лицето на възел може да съответства на код за проста Булева стойност да се посочи, че зоологическа градина е в речника или може съответства на допълнителна информация, която ние Иска да се сдружават с ключовата зоологическата градина, както и определянето на дума или нещо друго. В някои отношения, процесът да вмъкнете нещо в Trie е подобен търсите нещо в Trie. 

Ще започнем с корен възел отново, следните насоки, съответстващи буквите от нашите ключови. За щастие, ние бяхме в състояние да следват показалки по целия път, докато стигнахме на края на ключа. Тъй като зоологическата градина е префикс на думата увеличение, което е член на речник, ние не трябва да разпредели нови възли. 

Можем да променя възлова точка показва, че пътя на знаци, водещи до тя представлява ключова в нашия речник. Сега, нека се опитаме да поставите ключов БАНЯ в TRIE. Ще започнем от корен възел и следвайте отново указатели. Но в тази ситуация, ние удари мъртъв края, преди да можем да стигнем до край на ключа. Сега, ние ще трябва да се разпределят някои нови възли ще трябва да отделят един нов възел за всички останали писмо на нашия ключ. 

В този случай, ние просто трябва да се разпредели един нов възел. Тогава ще трябва да се направи индекс H упоменете нов възел. Отново, ние може да промени възел към посочва, че пътят на символи което води до това представлява ключ в нашия речник. Нека да разсъждаваме за асимптотичната сложност на процедурите ни за тях две операции. 

Забелязваме, че и в двата случая броят на стъпки от нашия алгоритъм отне беше пропорционално на броя на буквите в думата. Точно така. Когато искате да търсите дума в Trie просто трябва да превъртите през буквите една по една, докато вие или стигнат до края на думата или удари задънена улица в TRIE. 

А когато искате да вмъкнете ключов стойност чифт в Trie помощта на процедура ние обсъдихме, в най-лошия случай ще ви разпределяне на нов възел за всяка буква. И ние ще приемем, че разпределянето е постоянна работа време. Така че, ако приемем, че дължината на ключа е ограничена от фиксирана постоянно, както вмъкване и погледнете нагоре са постоянни операции за това срок Trie. 

Ако ние не правим това предположение, че дължината на ключа е ограничено с фиксиран константа, след това вкарване и погледнете нагоре, в най-лошия случай, са линейни в дължина на ключа. Обърнете внимание, че броят на елементи, съхранени в TRIE не се отразява на външния вид на или време вмъкване. Това е повлияно само от дължина на ключа. 

За разлика от това, добавяне на записи, да речем, хеш таблицата са склонни да направят бъдещата потърсим по-бавно. Макар че това може да звучи привлекателно на пръв поглед, ние трябва да имаме предвид, че благоприятно асимптотичната сложност не означава, че на практика данните структура е задължително безупречна. Ние също трябва да се счита, че за да съхраните дума в Trie ние трябва в най-лошия случай, редица възли пропорционална на дължината на самата дума. 

Опитва склонни да използват много пространство. Това е в контраст с хеш таблица, където ние само трябва един нов възел към съхранявате някои двойка ключове стойност. Сега, отново на теория, голямо пространство консумация не изглежда като една голяма се справят, особено предвид факта, че съвременната компютри имат гигабайта и гигабайта памет. Но се оказва, че ние все още имаме да се притеснявате за използването на паметта и организация заради производителност, тъй като съвременните компютри разполагат с механизми, съществуващи в рамките на качулка, за да се ускори достъп до паметта. 

Но тези механизми работят най-добре, когато памет достъпи са направени в компактен региони или зони. И възли на Trie може да пребивават навсякъде в тази купчина. Но това са компромиси че трябва да се помисли. 

Не забравяйте, че при избора на данни структура за определена задача, ние трябва да мислим за това, което видове операции структурата на данните трябва да подкрепа и колко изпълнение на всеки от тези оперативни въпроси към нас. Тези операции могат дори простира отвъд просто Основният поглед нагоре и вмъкване. Да предположим, че ние искахме да се приложи един вид на авто-пълна функционалност, много като търсачката Google прави. Това е, върнете всички ключове и потенциално ценности, които има даден префикс. 

A Trie е уникално полезно за тази операция. Това е ясно, за да превъртате през на TRIE за всеки един от героите на префикса. Само като погледнете нагоре операция, бихме могли да следват показалки знак по знак. След това, когато пристигнем в края на префикс, бихме могли да превъртите чрез на останалата част от структурата на данните тъй като всеки от бутоните отвъд тази точка има префикс. 

Това е също така лесно да се получи тази обява по азбучен ред, тъй като елементи на деца масива са подредени по азбучен ред. Така че, да се надяваме, че ще обмисли даване опитва да опитате. Аз съм Кевин Schmid, и това е CS50. 

Ах, това е началото от спада. Съжалявам. Извинете. Извинете. Извинете. 

Ненужното четири. Аз съм вън. Извинете. Извинете. Извинете. Съжалявам за вземане на лицето, което трябва да редактирате тази побърка. 

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

SPEAKER 1: Браво. Това е наистина добре направено.