>> 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.
>> Strike čtyři.
Jsem mimo.
Promiňte.
Omlouváme se za osobu, která má-li upravit tento zbláznit.
>> Promiňte.
Promiňte.
>> SPEAKER 1: Výborně.
To bylo opravdu dobře.