KEVIN SCHMID: Bəzən, bina bir proqram, siz istifadə etmək istədiyiniz bilər bir bir lüğət kimi tanınan data strukturu. Olan A lüğət xəritələr açarları, adətən strings, dəyərlərə, ints, chars, bir obyekt bir göstərici, biz istədiyiniz hər hansı. Bu yalnız adi lüğətlərin kimi anlayışlar vasitəsilə xəritəsi sözləri. 

Lüğətlər ilə bizi təmin məlumat saxlamaq üçün qabiliyyəti bir şey ilə bağlı və sonra bu qədər baxmaq. Belə ki, necə biz, həqiqətən, həyata yoxdur bir C kodu, demək, lüğət ki, biz bizim proqramları bir istifadə? Yaxşı, yolları bir çox var ki, biz bir lüğət həyata bilər. 

Bir üçün, biz bir sıra istifadə edə bilər ki, biz dinamik yenidən ölçüsü və ya bir istifadə edə bilər bağlı siyahı, hash table və ya bir ikili ağac. Amma biz seçə nə olursa olsun, biz olmalıdır səmərəliliyinin zehinli və həyata keçirilməsi performans. Biz istifadə alqoritmi haqqında düşünməlidir daxil edin və daxil maddələr axtarmaq üçün Bizim data strukturu. 

Indi üçün, ki biz fərz edək düymələri kimi strings istifadə etmək istəyirik. Biri mümkünlüyü haqqında danışmaq edək, məlumat strukturu bir trie çağırıb. Belə ki, burada bir vizual nümayəndəliyi var trie. 

Şəkil, bir Trie təklif kimi bir ağac data strukturu qovşaqlarının birlikdə bağlı. Biz kök aydın var ki, bax bəzi links uzanan ilə node digər qovşaqlarının. Amma hər node nə ibarətdir? Biz düymələri saxlanılması edirik ki, güman əgər yalnız əlifba simvol, və biz kapitallaşma haqqında qayğı yoxdur, Burada bir node bir tərif ki, kifayət edər. 

Kimin növü bir obyekt struct edir node iki hissədən ibarətdir məlumat və uşaqlar çağırıb. Biz şərh olaraq data iştirak tərk etdik bir komponenti ilə əvəz olunacaq struct node zaman bəyannamə C proqram daxil. Bir node data hissəsi ola bilər Göstərir Boolean dəyər və ya deyil node başa təmsil Bir lüğət düyməsi və ya bir ola bilər müəyyən təmsil string Lüğətə bir söz. 

Biz göstərmək üçün bir smiley face istifadə edəcəyik məlumat node mövcud olduqda. 26 elementləri var bizim uşaqlar array, bir index əlifba xarakter başına. Biz əhəmiyyətini görəcəksiniz tezliklə bu. 

Nin kök node yaxından nəzər almaq edək bizim sxemdə, heç bir məlumat var tərəfindən göstərilən kimi, bu ilə bağlı the smiley üz olmaması data hissəsi. Hissələri uzanan okları uşaqlar array qeyri-node təmsil digər qovşaqlarının göstəricilərinə. Məsələn, arrow uzanan uşaqların ikinci element məktub B təmsil bir lüğət əsas. Və böyük diaqram biz B. ilə etiket 

, Böyük diaqram Qeyd edək ki, zaman biz başqa node bir göstərici çəkmək, bu Fərq etməz olduğu arrowhead digər node görüşüb. Bizim nümunə lüğət trie şey iki söz, və zoom. Nin bir misal vasitəsilə gəzmək edək bir düyməsi üçün məlumatın axtarır. 

Biz baxmaq istəyirdi Güman edilən əsas vanna üçün dəyər müvafiq. Biz göz başlamaq lazımdır kök node. Sonra bizim ilk məktub almaq lazımdır , əsas B, və müvafiq tapmaq bizim uşaqlar array spot. Tam 26 ləkələr var ki, görürsünüz serialın, hər bir hərf üçün bir əlifba. Və biz ləkələr təmsil lazımdır üçün əlifbasının hərfləri. 

Biz, sonra ikinci indeksi baxmaq lazımdır Ümumiyyətlə B. index bir, əgər biz bəzi əlifba xarakter C, biz var müvafiq spot müəyyən edə bilər istifadə uşaqlar array Bu kimi bir hesablanması. Biz böyük uşaqlar istifadə edə bilər biz göz up təklif etmək istəyirdi array əgər simvol daha geniş düymələri, belə bütün, kimi ASCII character set. 

Bu halda, pointer bizim uşaqlar array da index bir null deyil. Beləliklə, biz axtarır davam edəcəyik əsas vanna up. Biz heç bir null göstərici rast varsa uşaq müvafiq spot da array biz qovşaqlarının keçdiyi isə, onda biz biz demək lazımdır ki düyməsi üçün bir şey tapa bilmədi. 

İndi biz ikinci məktub və almaq lazımdır bizim əsas, A, və davam aşağıdakı bu şəkildə göstəricilərinə biz qədər Bizim əsas sonuna çatmaq. Biz olmadan əsas sonuna çatmaq əgər bir ölü bitir dəyən null göstəricilərinə, işin burada kimi, sonra biz yalnız bir şey daha yoxlamaq lazımdır. Bu əsas deyil, həqiqətən, Lüğətə? 

Əgər belədirsə, biz yaxşı, bir dəyər tapmaq lazımdır Bizim diaqram smiley face icon yerləşir sözü bitir. Ilə saxlanılır başqa bir şey varsa məlumat, sonra biz onu qaytara bilər. Məsələn, əsas zoo deyil biz bilər, hətta lüğət, heç bu əsas sona çatdı , bir null göstərici vuruş isə biz trie vasitəsilə təkrarlamaq. 

Biz əsas vanna axtarmaq üçün cəhd Əgər Son node array indeksi ikinci, , məktubu H olardı müvafiq bir null göstərici keçirilib. Belə ki, hamam lüğətdə yoxdur. Və belə bir trie ki, düymələri nadir aydın saxlanılır heç vaxt məlumat strukturu. Belə ki, necə biz bir şey daxil edirsiniz trie daxil? 

Nin əsas daxil edək bizim trie daxil zoo. Xatırla ki, bir node bir smiley face bir sadə kodu uyğun bilər Ki, zoo göstərir Boolean dəyəri Lüğətə və ya bu ola bilər Daha ətraflı məlumat üçün uyğun ki, biz əsas zoo ilə birləşmək arzulayıram, Bu müəyyən kimi söz və ya başqa bir şey. Bəzi yollar, proses daxil trie daxil bir şey benzer bir trie bir şey axtarır. 

Biz, bir daha kök node ilə başlamaq lazımdır aşağıdakı göstəricilər müvafiq Bizim əsas məktublar. Neyse, biz göstəricilərinə əməl edə bildik biz əldə qədər bütün yol əsas sonu. Zoo sözü bir prefiks olduğundan nın üzvü olan zoom, lüğət, biz ehtiyac yoxdur hər hansı bir yeni qovşaqlarının ayırırlar. 

Biz göstərir node dəyişə bilərsiniz ki, aparıcı simvol yol Bu edir bizim lüğət bir əsas təmsil edir. İndi daxil edək trie daxil əsas BATH. Biz kök node başlamaq lazımdır və yenidən göstəricilərinə baxın. Amma bu vəziyyət, bir ölü edib biz əldə edə önce son əsas sonu. İndi biz bir sıra yeni ayırmaq lazımdır qovşaqlarının bir yeni ayırmaq lazımdır hər qalan üçün node Bizim əsas məktubu. 

Bu halda, biz yalnız ehtiyac yeni bir node ayrılması. Sonra H index etmək lazımdır Bu yeni node istinad. Bir daha, biz node dəyişə bilərsiniz göstərir ki, simvol yol ona aparan təmsil bizim lüğət əsas. Nin asimptotik haqqında mülahizə edək Bu üçün prosedurların mürəkkəbliyi iki əməliyyatları. 

Qeyd ki, hər iki halda sayı bizim alqoritm aldı addımlar sayına mütənasib söz məktublar. Bu doğru deyil. Sizə bir söz axtarmaq istədiyiniz zaman trie yalnız vasitəsilə təkrarlamaq lazımdır məktublar bir-bir sizin qədər ya Bu sözün sonunda və ya çatmaq trie bir ölü son edib. 

Və əsas daxil etmək üçün istədiyiniz zaman istifadə edərək, bir trie daxil dəyər cüt proseduru biz, ən pis halda müzakirə Siz yeni node ayrılması olacaq hər bir hərf üçün. Və biz ayrılması güman lazımdır bir daimi zaman əməliyyatdır. Biz əsas uzunluğu olduğunu güman belə, əgər sabit sabit, həm də həmsərhəddir durub və baxmaq daimi var trie üçün vaxt əməliyyatları. 

Biz bu ehtimalı yoxdur ki, əgər əsas uzunluğu sabit ilə həmsərhəddir daimi, sonra durub və baxmaq, ən pis halda, xətti olunur əsas uzunluğu. Maddələr sayı saxlanılır ki, görürsünüz trie görünüşünü qədər təsir etmir və ya durub zaman. Bu, yalnız təsir edir əsas uzunluğu. 

Əksinə, demək, entries əlavə, bir hash table etmək niyyətindədir gələcək yavaş baxmaq. Bu ilk cəlbedici görünə bilər baxmayaraq yadda saxlamaq lazımdır ki, bir əlverişli asimptotik mürəkkəbliyi deyil demək ki, təcrübədə data strukturu mütləq tənbeh kənarda. Biz də saxlamaq üçün hesab lazımdır pis biz lazımdır trie, söz halda, qovşaqlarının bir sıra proporsional sözü özü uzunluğu. 

Çalışır yer çox istifadə edirlər. Ki, bir hash masa fərqli var, biz yalnız bir yeni node lazımdır bəzi əsas dəyər cüt saxlamayın. İndi yenə nəzəriyyəsi, böyük kosmik istehlak böyük kimi görünmür xüsusilə nəzərə alsaq, məşğul ki, müasir kompüter gigabayt var və yaddaş gigabayt. Amma biz hələ ki, həyata çevirir yaddaş istifadə və narahat naminə təşkilat performance, çünki müasir kompüter altında yerdə mexanizmləri yaddaş girişi sürətləndirmək üçün başlıq. 

Lakin bu mexanizmlər ən yaxşı zaman iş yaddaş giriş-çıxış kompakt edilir bölgələrdə və ya sahələrdə. Və bir trie qovşaqlarının yaşamaq bilər ki, yığın-yığın yerdə. Amma bu ticarət-off biz hesab etməlidir ki,. 

Bir məlumat seçərkən, Unutmayın ki, müəyyən bir vəzifə üçün strukturu, biz haqqında düşünmək lazımdır nə cür əməliyyatları data strukturu lazımdır dəstək və nə qədər performance o hər bizə əməliyyatları məsələləri. Bu əməliyyatlar hətta may yalnız kənara əsas baxmaq və durub. Biz bir cür tətbiq etmək istəyirdi Güman avtomatik tam funksionallıq çox kimi Google search engine yoxdur. Ki, bütün düymələri qayıtmaq və potensial dəyərlər bir prefiks var. 

A trie benzersiz faydalıdır Bu əməliyyat üçün. Bu vasitəsilə təkrarlamaq üçün sadə var hər bir xarakter üçün trie prefiks. Sadəcə, bir qədər baxmaq əməliyyat kimi biz göstəricilərinə əməl bilər xarakteri ilə xarakter. Sonra, biz sonunda gəldiyi zaman prefiks, biz vasitəsilə təkrarlamaq bilər məlumat strukturunun qalan hissəsi düymələri hər hansı bir kənarda bəri Bu point prefiks var. 

Bu siyahı əldə etmək də asan ildən əlifba sırası ilə uşaqlar array elementləri əlifba sırası ilə sifariş olunur. Belə ki, inşallah hesab edəcəyik verilməsi cəhd çalışır. Mən Kevin Schmid oldum və bu CS50 edir. 

Ah, bu başlanğıcdır azalması. Üzgünüm. Üzr istəyirik. Üzr istəyirik. Üzr istəyirik. 

Dörd vur. Mən deyiləm. Üzr istəyirik. Üzr istəyirik. Üzr istəyirik. Şəxs üçün üzr edən Bu crazy getmək redaktə var. 

Üzr istəyirik. Üzr istəyirik. Üzr istəyirik. Üzr istəyirik. 

HOPARLÖR 1: Maşallah. Bu, həqiqətən yaxşı oldu.