KEVIN SCHMID: Někdy, při stavbě Program, možná budete chtít využít datové struktury známé jako slovník. Slovník klíče mapy, které jsou obvykle řetězce, hodnot, ints, znaky, ukazatel na nějaký předmět, co chceme. Je to jako obyčejné slovníky že mapa slova přes definic. 

Slovníky nám poskytují schopnost ukládat informace spojené s něčím a podívat se na to později. Tak jak jsme se vlastně provádět slovník, řekněme, C kódu, který můžeme použití v jednom z našich programů? No, existuje mnoho způsobů, jak bychom mohli realizovat slovník. 

Pro jednoho, mohli bychom použít pole, které jsme dynamicky re-size, nebo můžeme použít spojový seznam, hash tabulka nebo binární strom. Ale ať si vybereme, měli bychom dbát na efektivitu a výkon implementace. Měli bychom přemýšlet o použitém algoritmu vložit a vyhledat položky do naše datová struktura. 

Nyní předpokládejme, že jsme chcete používat řetězce jako klíče. Pojďme se bavit o jedné z možností, datová struktura se nazývá trie. Tak tady je vizuální reprezentace z trie. 

Jak obrázek naznačuje, trie je datový stromová struktura s uzly spojeny. Vidíme, že tam je jasně kořen Uzel se některé odkazy se rozšiřuje ostatní uzly. Ale to, co dělá každý uzel se skládá z? Budeme-li předpokládat, že jsme ukládání klíčů s pouze abecední znaky, a my se nestaráme o kapitalizaci, Zde je definice uzlu, který bude stačit. 

Objekt, jehož typ struct uzel má dvě části volal dat a děti. Nechali jsme část dat jako komentář být nahrazena složkou Prohlášení když struct uzel je začleněny do programu C. Datová část uzlu může být Logická hodnota označující, zda nebo Není uzel reprezentuje dokončení ze slovníku klíče, nebo by to mohlo být Řetězec představující definici na slova ve slovníku. 

Budeme používat smajlíky ukázat , je-li přítomna dat v uzlu. Existuje 26 prvků v našem děti pole, jeden index podle abecedy. Uvidíme význam z toho brzy. 

Pojďme se blíže podívat na kořenový uzel v našem diagramu, který nemá žádná data spojené s tím, jak je uvedeno absence smajlíka v Datová část. Šipky vyčnívat z částí Děti pole reprezentují non-uzel odkazy na jiné uzly. Například, šipka sahající od druhý prvek dětí představuje písmeno B ve slovníku klíč. A ve větším diagramu jsme to označení s B. 

Všimněte si, že v širším schématu, kdy jsme nakreslit ukazatel do jiného uzlu, je Nezáleží na tom, kde se šipka odpovídá, že jiný uzel. Náš vzorek slovník trie obsahuje dvě slova, která i zoom. Pojďme se projít příklad vyhledávání dat na klíč. 

Předpokládejme, že jsme se chtěli podívat do odpovídající hodnotu klíče lázně. Začneme náš pohled vzhůru na kořenový uzel. Pak budeme mít první písmeno našeho klíč, B, a najít odpovídající místě v našem děti poli. Všimněte si, že tam je přesně 26 míst v poli, jeden pro každé písmeno abeceda. A budeme mít skvrny představují písmena abecedy v pořadí. 

My se podíváme na druhý index pak, index jeden, pro B. Obecně platí, že pokud bychom nějaké abecední znak C my by mohla stanovit odpovídající místo v dětském pole pomocí Výpočet takhle. Mohli jsme použít větší děti pole, pokud bychom chtěli nabídnout look up klíče s širším rozsahu znaků, jako je celé Znaková sada ASCII. 

V tomto případě, ukazatel v našem děti pole v index jeden není null. Takže budeme nadále hledat up klíče lázně. Pokud se někdy setkali nulový ukazatel na správném místě, u dětí pole, když jsme se projet uzly, pak budeme muset říci, že jsme nemohl najít nic pro tento klíč. 

Nyní budeme mít druhý dopis náš klíč, a dále po ukazatele tímto způsobem, dokud se dostat se na konec našeho klíče. Pokud se dostanete na konec klíče, aniž by zasáhla všechny slepé uličky, null ukazatele, jako je tomu v tomto případě, pak pouze je nutné zkontrolovat ještě jednu věc. Je to klíč skutečně ve slovníku? 

Pokud ano, měli bychom najít hodnotu, dobře smiley ikona tvář v našem diagramu, kde slovo končí. Pokud tam je něco jiného, ​​ukládají se data, pak se můžeme vrátit. Například, klíč není v zoo slovník, i když jsme mohli mít dosáhl na konci tohoto klíče, aniž by bít nulový ukazatel, zatímco my iterovat trie. 

Pokud jsme se snažili vyhledat klíčové koupel, Druhý index pole loňského uzlu, odpovídající písmeno H, by drželi nulový ukazatel. Takže koupel není ve slovníku. A tak trie je unikátní v tom, že klíče se nikdy výslovně uloženy v datová struktura. Tak jak jsme se vložit něco do trie? 

Pojďme vložte klíč zoo do našeho trie. Pamatujte si, že smajlíky v uzlu mohla odpovídat v kódu na jednoduché Booleovská hodnota, která naznačují, že zoo je ve slovníku, nebo by to mohlo odpovídají více informací, které jsme chcete spojit s klíčovým zoo, jako vymezení Slovo nebo něco jiného. V některých ohledech, proces vložit něco do trie je podobný hledá něco v trie. 

Začneme s kořenový uzel znovu, Následující ukazatele odpovídá dopisy z našich klíčových. Naštěstí jsme byli schopni sledovat ukazatele celou cestu až jsme dorazili do konec klíče. Vzhledem k tomu, zoo je prefix slova zoom, který je členem slovník, nepotřebujeme, aby přidělit žádné nové uzly. 

Můžeme upravit uzel což znamená, že cesta znaků, které vedou k představuje klíč v našem slovníku. Nyní zkusme vložení Klíčovým BATH do trie. Začneme na kořenový uzel a sledovat ukazatele znovu. Ale v této situaci, zasáhla jsme mrtvý skončí dříve, než jsme schopni se dostat do konec klíče. Nyní budeme muset přidělit některé nové uzly budou muset přidělit jednu novou uzel pro každý zbývající Dopis z našeho klíče. 

V tomto případě, my prostě potřebujeme přidělit jeden nový uzel. Potom budeme potřebovat, aby index H odkázání se na tento nový uzel. Opět můžeme změnit uzel ukazují, že cesta znaků což vede k tomu představuje klíč v našem slovníku. Pojďme uvažovat o asymptotické Komplexnost našich postupů pro tyto dvě operace. 

Všimli jsme si, že v obou případech číslo z kroků náš algoritmus trvalo byla úměrná počtu Písmena na klíčové slovo. To je pravda. Chcete-li vyhledat slovo v trie stačí iterovat dopisy jeden po druhém, dokud buď dostanete na konec slova, nebo hit slepé uličky v trie. 

A když budete chtít vložit klíč hodnota dvojice do trie pomocí Postup jsme diskutovali, nejhorší případ bude vám přidělení nového uzlu pro každé písmeno. A budeme předpokládat, že rozdělení je konstantní doba provozu. Takže pokud budeme předpokládat, že délka klíče je ohraničena pevnou konstantou, a to jak vkládání a vyhledat konstantní časové operace pro trie. 

Pokud se nám nepodaří tuto domněnku, že délka klíče je ohraničena pevnou konstantní, pak se po vložení a dívat se, V nejhorším případě, jsou lineární v délka klíče. Všimněte si, že počet položek, uloženo v trie nemá vliv na vzhled nahoru nebo vložení čas. Je to jen vliv délka klíče. 

Naopak, přidávání položek, řekněme, hash tabulky vede k tomu, budoucnost vypadat pomaleji. I když to může znít jako lákavá na první pohled, bychom měli mít na paměti, že příznivé asymptotická složitost není znamená, že v praxi jsou data struktura je nutně nic vytknout. Musíme také vzít v úvahu, že k ukládání slovo v trie potřebujeme, v nejhorším případ, počet uzlů úměrná k délce slova. 

Pokusí mají tendenci používat hodně prostoru. To je na rozdíl od hash tabulky, kde budeme potřebovat pouze jeden nový uzel uložit některé dvojice klíč hodnota. Nyní, opět teoreticky, velký prostor Spotřeba nevypadá jako velký řešit, a to zejména vzhledem k tomu, moderní počítače mají gigabajtů a GB paměti. Ale ukázalo se, že máme stále se starat o využití paměti a organizace v zájmu výkon, protože moderní počítače mají mechanismy v místě pod kapuce urychlit přístup do paměti. 

Ale tyto mechanismy fungují nejlépe, když paměťové přístupy jsou v kompaktním regiony nebo oblasti. A uzly trie mohla pobývat kdekoliv v této hromadě. Ale to jsou kompromisy že musíme vzít v úvahu. 

Pamatujte si, že při výběru dat struktura pro určitý úkol, se by měl přemýšlet o tom, jaké druhy operace datová struktura musí Podpora a kolik výkonu každého z nich operace záleží na nás. Tyto operace mohou dokonce přesahují jen Základní vzhled a vložení. Předpokládejme, že bychom chtěli zavést jakousi automatického dokončování funkcí, hodně jako vyhledávač Google dělá. To znamená, že vrátí všechny klíče a potenciálně hodnoty, které mají danou předponu. 

Trie je jednoznačně užitečná pro tuto operaci. Je to jednoduché iteraci trie pro každý znak prefix. Stejně jako se podívat do provozu, jsme mohli sledovat ukazatele znak po znaku. Pak, když dorazíme na konec prefix, můžeme iterovat Zbývající část datové struktury protože každá z klíčů po Tento bod má předponu. 

Je také snadné získat tento zápis v abecedním pořadí od prvky dětského pole jsou řazeny abecedně. Takže doufejme, že budete uvažovat dávání se snaží vyzkoušet. Já jsem Kevin Schmid, a to je CS50. 

Ach, to je začátek poklesu. Je mi to líto. Promiňte. Promiňte. Promiňte. 

Strike čtyři. Jsem mimo. Promiňte. Promiňte. Promiňte. Omlouváme se za osobu, která má-li upravit tento zbláznit. 

Promiňte. Promiňte. Promiňte. Promiňte. 

SPEAKER 1: Výborně. To bylo opravdu dobře.