[MUSIC PLAYING] DOUG LLOYD: Beləliklə, biz yaxın inching olduğunuz və yaxın veri müqəddəs grail biz əlavə edə bilərsiniz strukturları bir daxil silmek və yuxarı baxmaq daimi vaxt. Right. Ki, məqsəd sort var. Biz bunu etmək istəyirəm şeyi çox, çox tez. 

Biz burada zaman gördük biz çalışır bəhs edirik? Yaxşı, bir nəzər salaq. Beləliklə, biz bir neçə gördüm müxtəlif məlumat strukturları ki, birdən idarə əsas dəyər cüt qondarma, məlumatların bəzi parça Xəritəçəkmə məlumatların bəzi digər parça belə ki, biz tapmaq üçün harada strukturunda məlumat. 

Belə ki array üçün, məsələn, əsas element index və ya array var yeri 0 və ya array 1 və s. Və dəyəri data ki, yeri var. Belə ki, serialın 0 nə saxlanılır? Nə yalnız qarşı array 1 saxlanılır 0 və 1, düymələri olacaq. 

Bir hash masa ilə bu Eyni fikir sort. Bir hash masa ilə, bu hash var hash kodları yaradır fəaliyyət göstərir. Belə ki, əsas məlumatların hash kodu. Və dəyəri, xüsusilə biz zəncirləmə haqqında danışdı hash masalar video, məlumatların ki, bağlı siyahısı ki hashcode üçün hashes. Right. Başqa yanaşma haqqında nə bu üsul olsa? Bir üsul haqqında nə olduğu əsas, unikal olması təmin edilir bir hash masa, biz bilər fərqli məlumatların iki ədəd ilə başa Eyni hashcode olan. Və sonra biz ilə məşğul ki, ya probing və ya daha çox üstünlük problemi həll etmək chaining. 

Belə ki, indi biz təmin edə bilər ki, əsas unikal olacaq. Və dəyəri nə idi asan kimi yalnız bir şey olub bizə deyir ki, doğru və yalan məlumat və ya deyil ki, parça tərkibində mövcuddur? A Boolean bir az kimi sadə ola bilər. Real yəqin ki, bir bir az daha çox ehtimal byte. Amma bu çox kiçik 50 xarakter string bəlkə saxlanılması, misal üçün. 

Çalışır, belə ki, masalar hash oxşar, olan birləşdirmək seriallarda və bağlı siyahısı, çalışır Diziler birləşdirmək, strukturları və göstəricilər birlikdə veri ki, bir maraqlı yol olduqca müxtəlif Biz bu günə qədər gördüm bir şey. İndi biz bir yol xəritəsi kimi data istifadə Bu data strukturu naviqasiya. Və biz təqib edə bilər, əgər yol xəritəsi, biz əgər məlumat edin başından sonuna qədər alacağıq ki, data olub-olmadığını bilmək trie mövcuddur. 

Və biz xəritəsi edin bilməz, əgər bütün son, yəni ki, məlumat mövcud deyil. Yenə düymələri burada Unikal olması təmin. Belə bir hash masa fərqli olaraq, biz heç vaxt lazımdır Burada toqquşma ilə məşğul olmalıdır. Və məlumatların heç bir iki ədəd eyni yol xəritəsi var halda ki, data eynidir. 

Biz John, sonra daxil olarsa biz John üçün axtarış. Ki, iki eyni ədəd var data, sağ, biz vasitəsilə baxırıq. Lakin başqa, hər hansı bir məlumatların iki ədəd var unikal yol xəritələri üçün zəmanət Bu data strukturu vasitəsilə. Və biz nəzər olacaq yalnız bir anda bu vizual. 

Biz çalışırıq bu edəcəyik yeni data strukturu yaratmaq, aşağıdakı əsas dəyər cüt Xəritəçəkmə. Bu halda, biz istifadə etmək fikrində deyilik boolean kimi sadə bir şey. Biz, həqiqətən, simli saxlamaq olacaq. Və string gedir bir universitetin adı. 

Və əsas il olacaq universitet təsis edildiyi. Ali Bütün il dörd rəqəm olacaq. Və belə ki, biz bu dörd rəqəm istifadə edəcəyik Bu data strukturu vasitəsilə gedin. Və biz yenə görəcəksiniz, necə biz yalnız ikinci bunu. 

Yolun sonunda, biz adını görəcəksiniz uyğundur universitetin ki əsas, bu dörd rəqəm. bir trie əsas ideyası biz mərkəzi marşrut var. Belə ki, bir ağac kimi bu barədə düşünürəm. Bu yazım oxşar və ağaca anlayışı. Ümumiyyətlə, biz haqqında düşünmək zaman real dünyada ağaclar, onlar bir kök torpaq və onlar yuxarı inkişaf və onlar filial və onlar yarpaqları var. Və əsasən fikir bir trie, tam eyni deyil ki, kök anchored edir istisna olmaqla, Göy yerdə. Və yarpaqları altındakı var. 

Belə ki, bir ağac alaraq kimi növ var və yalnız altüst Flipping. Amma yenə də filialları var. Və bu bizim yollar olacaq, o bizim əlaqələri olacaq yarpaqları kök. Bu halda, o yolları, o filialları bizə rəqəm ilə etiketli olunur hansı yolla biz burada getmək. 

Biz bir 0 görürsünüzsə, biz bu sahədə enmək, Biz bir 1 görürsünüzsə, biz bu sahədə enmək, və s və s. Bəli, bu nə deməkdir? Yaxşı ki, o deməkdir ki, hər qovşağında nöqtədə və hər node orta və hər filialı, Mümkün 10 var biz getmək bilər yerlərdə. Belə ki, 10 göstəricilərinə var hər yerdən. 

Çalışır bir əldə edə bilərsiniz və bu kimsə üçün qorxuducu az kim bir çox yoxdur əvvəl kompüter təcrübəsi. Amma çalışır həqiqətən olduqca zəhmli edir. Və varsa onlarla işləmək imkanı və qazmaq-in istediğiniz və onlarla təcrübə, Onlar, həqiqətən, olduqca maraqlı deyilik data strukturları ilə işləmək üçün. Biz bir element əlavə etmək istəyirsinizsə, trie daxil bütün biz nə etmək lazımdır doğru yol qurmaq yarpaq kök. Burada nə hər bir addım birlikdə var yol kimi görünə bilər. Biz yeni məlumatlar müəyyən olacaq yeni node üçün struktur bir trie çağırıb. 

Və məlumatların daxili quruluşu iki ədəd var. Biz saxlamaq olacaq bir universitetin adı. Və biz saxlamaq olacaq göstəricilər bir sıra eyni tipli digər qovşaqlarının. Belə ki, daha, bu ki, sort deyil Hər yerdə anlayışının biz 10 mümkün var biz getmək bilər yerlərdə. Biz bir 0 görürsünüzsə, bu filialı enmək. Biz 1 görürsünüzsə, bu sahədə, və s və s və s. Biz 9 demək olarsa, bu filialı enmək. Hər qovşağında nöqtədə So 10 mümkün yerlərdə bilərsiniz. Belə ki, hər node 10 göstəricilərinə ehtiva edir 10 qovşaqlarının digər qovşaqlarının, üçün. 

Və biz saxlanılması edirik məlumatdır universitetin yalnız adı. Belə ki, bir trie inşa edək. Bir neçə daxil edək Bizim trie daxil maddələr. , Çox üst So bu, bizim kök node edir. Bu yəqin ki, bir şey olacaq Siz elan Qlobal olacaq. Və saxlamaq Qlobal olacaq həmişə bu node bir göstərici. 

Siz demək olacaq kök bərabərdir, və istəyirik Özünüz trie node malloc gedir. Və heç vaxt olacaq daha kök toxunmaq. Siz istədiyiniz hər dəfə gezinmek başlamaq, Başqa bir göstərici müəyyən Belə trav kimi, kök bərabər, olan nümunə var Mənim Videonun çox istifadə burada çıxarıcı borular və kuyrukları və link siyahıları və s. 

Başqa bir göstərici müəyyən traversal üçün Trav çağırıb. Və naviqasiya Trav istifadə data strukturu vasitəsilə. Belə ki, bu ola bilər necə edək. Belə ki, indi, nə bir node kimi görünür? Bəli, yalnız bizim data kimi strukturu bəyannamə, göstərilən biz bir simli var olan bu halda boş. Burada bir şey yoxdur. 

10 göstəricilər bir sıra. Və indi, biz yalnız bu trie 1 node var. Bu başqa bir şey yoxdur. Belə ki, o bütün 10 point göstəricilərinə null. Ki, qırmızı göstərir budur. 

Nin simli Harvard daxil edək. Nin University daxil edək Bu trie daxil Harvard olan il 1636-ci ildə yaradılmışdır. Biz düyməsindən istifadə etmək istəyirsinizsə, 1636, biz olduğunuz bizə trie Harvard saxlamaq üçün gedir. İndi ki, necə ola bilər? 

Bu kimi bir şey ola bilər. Biz kök başlamaq. Və biz getmək bilər ki, bu 10 yerləri var. kök yalnız hər hansı bir kimi trie digər node. Biz burada getmək bilər 10 yerlər var. 

Harada biz yəqin ki, istəyirəm əsas 1636 əgər getmək? Həqiqətən iki variantları var. Right. Biz əsas inşa edə bilərsiniz sol və sağ 6 ilə başlamaq üçün. Yoxsa biz açarı qurmaq bilər soldan sağa və 1 ilə başlayın. 

Bu yəqin ki, daha çox bir insan kimi intuitiv alacağıq anlamaq yalnız soldan sağa gedin. Və mən əlavə etmək istəyirsinizsə, Bu trie daxil Harvard, Mən yəqin ki, başlamaq istəyirəm kök başlayaraq, mənim 10 variantları axtarır mənə qarşısında və söyləyərək I 1 yol aşağı getmək istəyirəm. OLDU. 

İndi 1 yol hazırda null edir. Belə ki, yol aşağı davam etmək istəyirsinizsə, trie bu element əlavə etmək üçün, Mən 1 var, yeni node malloc var orada qeyd və sonra getmək üçün yaxşı deyiləm. 

Belə ki, əsasən am point mən duran alıram ağac və ya kök trie və 10 filialı var. Lakin hər bir filial bir qarşısında qapısı. Right. Heç bir şey yoxdur, çünki başqa var. No təhlükəsiz keçid. Ki, heç bir şey yoxdur o deməkdir ki, o istənilən filialına aşağı. Mən bina başlamaq istəyirsinizsə bir şey, mən qapısı çıxarmaq istəyirik. Mən qapısı aradan qaldırılması üçün istədiyiniz 1 nömrəli qarşısında. Mən ki, aşağı gəzmək istəyirəm. Mən qurmaq istəyirik Mənim üçün başqa bir yer getmək üçün. 

Və mən burada etdik nə var. Belə ki, 1 artıq bal null üçün. Mən indi burada enmək təhlükəsiz bildirib etdik. Başqa bir node inşa edilmişdir. Mən ki, node almaq zaman, mən etmək üçün başqa bir qərar var. Harada buradan getmək üçün gedirəm? 

Bəli, mən artıq 1 aşağı getdi etdik. Belə ki, indi mən yəqin ki, 6 aşağı getmək istəyirəm. Right. Yenə mən seçə bilərsiniz 10 yerlərdə var. Belə ki, indi sayı 6 gedək. Belə ki, qapısı sil 6 nömrəli qarşısında. Mən orada gəzmək. Mən başqa bir node qurmaq. Mən bir qovşaq nöqtəsi əldə etdik. 

Yenə 10 seçim var Mən getmək bilər harada. Mən 1-dən 6-hərəkət etdik. Belə ki, indi mən yəqin ki, 3 getmək istəyirəm. 3, heç bir yerdə mən getmək bilər var. Belə ki, yol açmaq lazımdır və özümü yeni bir yer yaratmaq. Və sonra mən getmək istəyirəm 3 olan? Mən aşağı 6 getmək istəyirəm. 

Və yenə, mən idi bunu yol açmaq. Belə ki, indi yaratmaq daxil mənim düyməsini istifadə etdiyiniz qovşaqlarının bu trie qurmaq başlamaq və. Mən kök açılmış etdik. Mən 1636-cı aşağı getdi etdik. İndi altındakı deyiləm orada node. Və edə bilər ekranda görürük. 

Bu sarı qeyd edir. Hal-hazırda am harada. Mənim əsas edilir. Mən əsas hər mövqe canı etdik. Belə ki, hər hansı bir daha getmək bilməz. Bu nöqtədə, bütün Mən həqiqətən OK, demək nə etmək lazımdır. Bu cür axtarır kimi torpaq aşağı, Siz nəzərdə tutan edirsinizsə Özünüz yolun bu növ kimi müxtəlif əlaqələri ilə. Sort aşağı və sort axtarır yerdə Harvard rəsm sprey. Yəni bu adı var. Bu yerdə nə bilirik. Biz kök başlamaq və biz aşağı getmək əgər 1 və sonra 6 və sonra 3 və sonra 6 Biz harada var? Yaxşı aşağı baxmaq əgər və biz sonra, Harvard görmək biz Harvard olduğunu bilirik yolu əsasında 1636-ci ildə yaradılmışdır bu data strukturu həyata edirik. Belə ki, inşallah sadə idi. Biz daha iki insertions nə olacaq. Və ümid edirəm ki, kömək lazımdır çox bu iki dəfə daha çox işlər. 

İndi bir universitet daxil edək. Bu trie daxil Yale daxil edək. Yale 1701-ci ildə yaradılmışdır. Belə ki, biz başlamaq lazımdır kök, biz həmişə nə kimi. Və biz bir traversal göstərici seçin. Biz vasitəsilə hərəkət etmək üçün istifadə olacaq. biz istədiyiniz ilk şey Bunu 1 yoluna getmək edir. Yəni bizim əsas ilk rəqəmli var. Xoşbəxtlikdən, baxmayaraq ki, biz deyil hər hansı bir iş bu dəfə var. 1 yol artıq təmizləndi. Mən əvvəllər mən bunu ili 1636-da Harvard daxil edilib. Belə ki, təhlükəsiz hərəkət edə bilər 1 aşağı və yalnız orada getmək. 1 aşağı hərəkət edə bilər. 

İndi baxmayaraq ki, mən 7 getmək istəyirəm. Mən 6 yol təmizlənib. Mən təhlükəsiz bilirik 6 yol aşağı davam etdirilir. Amma 7 yoluna davam etmək lazımdır. Belə ki, nə mən nə etmək lazımdır? Bəli, yalnız əvvəl kimi, yalnız lazımdır qapısı təmizləmək üçün yol həyata almaq, 7 yolundan yeni node qurmaq. Məhz bu kimi. 

Belə ki, indi 1 və sonra 7 hərəkət etdik. İndi qeyd mən sort edirəm bu yeni şöbəsi var. Right. 16 başqa hər şey , Mən qayğı yoxdur. Mən 16 bir şey bunu deyiləm. Mən 17 stuff edirəm. 

Belə ki, indi 17-dən, mən var sort burada yeni yolları etmek. növbəti rəqəmli mənim əsas 0. Mən aydın yerdə əldə edə bilməz. Mən yalnız bu node inşa edilmişdir. Belə ki, mən heç bir var bilirəm irəli buradan yolları. Mən bir özüm etmək lazımdır. 

Belə ki, yeni node malloc və orada 0 nöqtə var. Və sonra bir dəfə daha, mən malloc bir yeni node və orada bir nöqtə var. Yenə Mən düyməsi, 1701 canı etdik. Beləliklə, mən aşağı baxmaq və mən Yale boya sprey. Yəni, bu node adı var. 

Və indi mən heç Yale görmek lazımdır bu trie, mən kök başlamaq, Mən 1701-aşağı getmək və aşağı baxmaq. Mən Yale sprey görürsünüzsə sonra ortalığa boyalı Mən Yale bu trie mövcuddur bilirik. Daha bir nə edək. Bu daxil Dartmouth daxil edək 1769-ci ildə təsis edilib trie. 

Daha kök başlamaq. Mənim əsas mənim ilk rəqəmli 1. Mən təhlükəsiz ki, yolunu aşağı hərəkət edə bilər. Artıq mövcuddur. Mənim əsas növbəti rəqəmli 7. Mən təhlükəsiz ki, yolunu aşağı hərəkət edə bilər. Bu həmçinin mövcuddur. 

Növbəti 6. Burada, Hal-hazırda am yerdən ki, orta node var sarı, 6 Hal-hazırda off kilidlənib. Hesab edirəm ki, yol aşağı getmək istəyirsinizsə, Mən özüm qurmaq lazımdır. Belə ki, yeni node malloc lazımdır və orada 6 nöqtə var. Və sonra, yenə, mən deyiləm Burada yeni yolları alovlu. 

Belə ki, yeni node malloc ki, belə İndi o node yol sayı 9 olan və Mən 1769 səyahət və mən aşağı baxmaq əgər. Heç bir şey Hal-hazırda yoxdur orada boyalı sprey. Mən Dartmouth yaza bilərsiniz. Mən daxil etdik Trie daxil DARTMOUTH. 

Belə ki, daxil deyil trie daxil şeylər. İndi biz şey üçün axtarış etmək istəyirəm. Necə ki, biz trie şey üçün axtarış edirsiniz? Bəli, bu, olduqca çox eyni fikirdir. İndi biz yalnız əsas rəqəm istifadə biz kök getmək bilər görmek üçün biz trie getmək istədiyiniz üçün. 

Biz sonra, hər hansı bir anda bir ölü son edib ki, element mövcud deyil bilər ki, bilirik və ya başqa yol olardı artıq təmizlənib. Biz bütün yol etmək əgər sonunda, bütün biz nə etmək lazımdır aşağı baxmaq və əgər görmək biz aradığınız element. Bu, uğur deyil. Bu deyil, uğursuz. 

Belə ki, üçün axtarış imkan Bu trie Harvard. Biz kök başlamaq. Və yenə biz olacaq bir traversal pointer yaratmaq bizim üçün hərəkət etmək üçün. Kök biz bilirik ki, biz getmək lazımdır ilk yer, 1 biz bunu edə bilər? Bəli, biz bilərsiniz. Əgər təhlükəsiz mövcuddur. Biz orada getmək bilər. 

İndi biz getmək lazımdır növbəti yer 6. 6 yolu buradan varmı? Bəli, bu yoxdur. Biz 6 yol aşağı bilərsiniz. Və biz burada son. 

Biz burada 3 yol aşağı getmək olar? Bəli, bu çıxır kimi, Bəli, çox var. Və biz burada 6 yolda əldə edə bilərsiniz? Bəli, biz bilərsiniz. 

Biz kifayət qədər cavab yoxdur hələ sual. Bir daha hələ var İndi addım, Biz aşağı baxmaq lazımdır və ki, həqiqətən görmek biz Harvard arıyorsanız, ki, biz əsas girinc sonra biz nə tapmaq? Məsələn, biz burada istifadə etdiyiniz, il həmişə dörd rəqəm var. Amma nümunə harada istifadə edilə bilər Siz sözləri lüğət saxlanılması olunur. 

Və belə əvəzinə 10 göstəricilərinə malik olan Mənim yeri üçün, 26 ola bilər. Əlifba hər bir hərf üçün bir. Və yarasa kimi bəzi sözlər var, olan məsələn partiyasının alt edir. Və almaq belə olsa əsas sonu və aşağı baxmaq, Siz nə görmək bilər Aradığınız. 

Belə ki, həmişə axır var Bütün yol və sonra Uğurla edə olsaydı bütün yol axır, aşağı baxmaq və bir final təsdiq yoxdur. Mən arıyorum nədir? Bəli, mən başlayaraq sonra aşağı baxmaq üst və 1636 gedir. Mən aşağı baxmaq. Mən Harvard görürük. Belə ki, bəli, mən oldu. Nə nə mən arıyorum baxmayaraq ki, trie deyil. Mən Princeton arıyorum nə varsa, olan 1746-ci ildə yaradılmışdır. Və belə 1746 mənim əsas olur trie gezinmek üçün. Yaxşı, mən kök başlamaq. Mən istəyirəm ilk yer 1 yol aşağı gedir. Mən bunu edə bilər? Bəli, edə bilərsiniz. 

Mən 7 yol aşağı getmək olar? Bəli, mən. Bu çox mövcuddur. Amma buradan 4 yol aşağı getmək olar? Bu bilərsiniz, sual kimi Mən kiçik kvadrat ki, aşağı davam Mən sarı qeyd etdik? Heç bir şey yoxdur. Right. 

Heç bir yol irəli 4 yol aşağı var. Princeton, bu trie idi 4 ki, əgər artıq bizim üçün tip olardı. Və bu nöqtədə biz bir ölü sonunda əldə etdiyiniz. Biz bundan sonra da hər hansı bir getmək bilməz. Və belə ki, biz heç bir qəti demək olar. Princeton bu trie yoxdur. 

Belə ki, bu bütün nə deməkdir? Right. Burada gedən bir çox var. Bütün yer üzərində göstəricilər var. Və kimi görə bilərsiniz yalnız diagram qovşaqlarının bir çox var ki, növ ətrafında uçan olunur. Amma biz istəyirdi hər zaman hiss bir şey trie olub-olmadığını yoxlamaq, biz yalnız 4 hərəkət etmək idi. 

Biz istəyirdi hər dəfə trie bir şey daxil, biz bəlkə, 4 hərəkət etmək lazımdır yol boyunca bəzi məhsulları mallocing. Biz daxil zaman gördük kimi Trie daxil Dartmouth, bəzən yolun bəzi artıq bizim üçün rəsmiləşdirilməyib bilər. Və belə ki, bizim trie olur kimi böyük və böyük, daha az iş hər zaman var yeni şeylər əlavə etmək biz artıq var, çünki aralıq bir çox inşa yol boyunca filialları. Biz yalnız heç baxmaq varsa, 4 şeyi, 4 yalnız daimi deyil. Biz, həqiqətən, cür yaxınlaşan daimi vaxt durub və daimi vaxt Sistemi. tradeoff, əlbəttə, ki, olan bu trie kimi yəqin ki, deyə bilərsiniz böyükdür. Bu qovşaqlarının hər biri kosmik bir çox çəkir. 

Amma ki, tradeoff var. Biz, həqiqətən, sürətli istəyirsinizsə durub, həqiqətən sürətli silinməsi, və həqiqətən sürətli axtarış, biz var bir çox veri ətrafında uçan var. Biz kosmik bir çox kənara var ki, data strukturu üçün yaddaş mövcud. 

Və belə ki, tradeoff var. Lakin biz kimi görünür aşkar ola bilər. Biz gördük bilər data strukturları müqəddəs grail tez durub ilə, silinməsi, və axtarış. Və bəlkə bu olacaq müvafiq data structure nə məlumat üçün istifadə biz mağaza çalışırıq. Mən Doug Lloyd deyiləm, bu CS50 edir.