[Přehrávání hudby] DOUG LLOYD: Takže jsme byli blíží se a blíž, že svatý grál dat struktury, ten, který můžeme vložit do, odstranit z, a dívat se v konstantním čase. Správně. To je něco jako cíle. Chceme být schopni dělat věci velmi, velmi rychle. 

Už jsme ho našli tady, když mluvíme o pokusech? Dobře, pojďme se podívat. Takže jsme viděli několik různé datové struktury že zvládnout mapování tzv párů klíč-hodnota, mapování nějakou část dat na nějakou jinou část dat takže víme, kde najít Informace ve struktuře. 

Takže pro pole, například, Klíčem k úspěchu je index prvek nebo pole Poloha 0 nebo 1 pole, a tak dále. A je hodnota údaje že v daném umístění existuje. Takže to, co je uloženo v poli 0? To, co je uložen v matici 1 ve srovnání s právě 0 a 1, což by bylo klíče. 

S hash tabulky je to druh ze stejné myšlenky. S hash tabulky, máme tuto hash funkce, která generuje hash kódy. Takže klíč je hash kód dat. A hodnota, zejména jsme si povídali o řetězení ve videu na stoly mřížky, je to, že spojená seznam údajů, že hash k tomuto hashCode. Správně. Co jiného přístupu Tato metoda, i když? Jak je to způsob, kde Klíčem je zaručeno, že je jedinečný, na rozdíl od tabulky hash, kde bychom mohli skončit s dvěma kusy dat které mají stejnou hodnotu hash. A pak máme co do činění s že buď snímání nebo více přednostně řetězení vyřešit tento problém. 

Takže teď můžeme zaručit že náš klíč bude jedinečná. A co když naše hodnota byla prostě něco tak snadné jako true a false, která nám říká, zda či ne, že část informace existuje ve struktuře? Booleovská může být stejně jednoduché jako trochu. Reálně je to asi byte s větší pravděpodobností než trochu. Ale to je mnohem menší, než uložení možná 50-řetězec znaků, například. 

Takže pokusech, podobně jako hash tabulky, které kombinují pole a spojový seznam, snaží kombinovat pole, struktury, a ukazatele společně ukládat data v zajímavý způsob, jak to je docela odlišný od cokoliv, co jsme dosud viděli. Nyní budeme používat data jako cestovní mapa navigovat tuto strukturu dat. A pokud můžeme sledovat Cestovní mapa, pokud můžeme následovat data z začátku až do konce, budeme vědět, zda těchto dat existují v trie. 

A když nemůžeme sledovat mapu což znamená, ze do konce vůbec, data nemůže existovat. Opět platí, že zde jsou klíče zaručena jedinečnost. A tak na rozdíl od stolu mřížky, budeme nikdy budou muset vypořádat s kolizemi zde. A žádné dva kusy dat mají přesně stejný plán ledaže, že údaje jsou totožné. 

Pokud vložíme John, pak hledáme pro Johna. To je dvě identické kusy Údaje, vpravo, díváme skrz. Ale jinak, jakákoliv dva kusy dat jsou zaručeno, že mají jedinečné plány prostřednictvím této datové struktury. A budeme se podívat na vizuální to za chvíli. 

Uděláme to, že se snaží vytvořit novou datovou strukturu, mapování tyto dvojice hodnoty klíče. V tomto případě, nebudeme používat něco tak jednoduchého, jako Boolean. Vlastně jsme uloží řetězec. A to řetězec se chystá být název vysoké školy. 

A klíč bude rok kdy byla založena, že vysokoškolské. Všechny roky pro vysoké školy se bude čtyři číslice. A tak budeme používat ty čtyři číslic procházet této datové struktury. A uvidíme, opět, jak uděláme, že v jen sekundu. 

Na konci dráhy, uvidíme jméno univerzity, která odpovídá k tlačítku, tyto čtyři číslice. Základní myšlenkou trie je máme centrální trasu. Takže myslíte, že o tom jako strom. A toto je podobné v hláskování a v pojetí k stromu. Obecně platí, když si myslíme, že o stromy v reálném světě, mají kořen, který je v pozemní a rostou vzhůru a oni mají pobočky a mají listy. A v podstatě myšlenka Trie je přesně stejný, s výjimkou, že kořen je ukotven někde na obloze. A listy jsou ve spodní části. 

Takže je to trochu jako s strom a jen překlopení vzhůru nohama. Ale jsou tu ještě pobočky. A ti by se naše cesty, ty budou naše spoje z kořene do listů. V tomto případě, ti, cest, tyto pobočky jsou označeny číslicemi, které vypovídají kudy jít z místa, kde jsme. 

Pokud vidíme 0, půjdeme dolů tohoto odvětví, pokud vidíme 1, půjdeme dolů tohoto odvětví, a tak, a tak dále. No, co to znamená? No, to znamená, že v každém spojovacím místě a každý uzel ve prostřední a každá větev, tam jsou 10 možný míst, které můžeme jít. Takže existuje 10 ukazatelů z každého místa. 

A to je místo, kde se pokusí se dostat trochu zastrašující pro někoho kdo je nemá mnoho zkušenosti v oblasti počítačové vědy před. Ale snaží jsou opravdu dost děsivý. A pokud máte možnost pracovat s nimi a jste ochotni kopat-in a experimentovat s nimi, jsou opravdu docela zajímavé datové struktury pro práci s. Chceme-li vložit prvek do trie, vše, co potřebujete udělat, je vytvořit správnou cestu z kořene do listu. Tady je to, co na každém kroku podél způsob, jak by mohla vypadat. Budeme definovat nové údaje struktura pro nový uzel nazývaný trie. 

A uvnitř těchto údajů Struktura existují dva kusy. Chystáme se ukládat jméno univerzity. A budeme uchovávat pole ukazatelů do jiných uzlů stejného typu. Takže, znovu, je to, že druh z koncepce všude my jsme, jsme na 10 možný místa můžeme jít. Pokud vidíme 0, půjdeme dolů toto odvětví. Pokud budeme vidět 1, toto odvětví, a tak dále, a tak dále a tak dále. Říkáme-li, 9, půjdeme dolů toto odvětví. Takže v každém spojovacím místě, můžeme jít 10 možných míst. Každý uzel tak musí obsahovat 10 ukazatele do jiných uzlů, do 10 ostatních uzlů. 

A data, my je ukládání jen název univerzity. Takže pojďme postavit trie. Pojďme vložit pár předmětů do našich trie. Takže na samém vrcholu, to je náš kořen. Toto je pravděpodobně bude něco budete globálně prohlašují. A vy budete globálně udržení ukazatel na tento uzel vždy. 

Budeš říkat, kořen rovná, a vy jste bude malloc sami trie uzel. A vy nikdy dotknout kořen znovu. Pokaždé, když budete chtít zahájit procházení, můžete nastavit další ukazatele rovnající se kořen, jako je například trav, což je příklad I použití v mnoha mých videí tady na komíny a fronty a odkaz seznamy, a tak dále. 

Můžete nastavit jinou ukazatel volal trav umožňujícím průchod. A používáte trav k navigaci přes datové struktury. Tak uvidíme, jak to může vypadat. Takže teď, co dělá uzel vypadá? No, stejně jako naše data Prohlášení struktura je uvedeno, Máme řetězec, který v tomto případě je prázdný. Tady nic není. 

A pole 10 ukazatelů. A právě teď, my jen má 1 uzel v tomto trie. Na tom není nic jiného v něm. Takže všechno 10 z těch, ukazatele bod na hodnotu null. To je to, co červená indikuje. 

Pojďme vložte řetězec Harvard. Pojďme vložte univerzita Harvard do této trie, který byla založena v roce 1636. Chceme použít klíč, 1.636, nám říct, kde jsme bude ukládat Harvard v trie. Nyní, jak by to uděláme? 

Mohlo by to vypadat nějak takhle. Začneme u kořene. A máme těchto 10 míst, můžeme jít. Kořen je stejně jako jakýkoli jiný uzel trie. K dispozici je 10 míst, můžeme přejít od tady. 

Kam pravděpodobně chceme kam jít, pokud je klíč 1636? Je to opravdu dvě možnosti. Správně. Můžeme vytvořit klíč od zprava doleva a začít s 6. Nebo bychom mohli postavit klíč zleva doprava a začít s 1. 

Je to pravděpodobně více intuitivní jako lidská bytost porozumět budeme Stačí jít zleva doprava. A tak, když chci vložit Harvard do této trie, Asi Chci začít tím, že začíná u kořene, při pohledu na mé 10 možností přede mnou, a řekl Chci jít dolů 1 cestu. DOBŘE. 

Nyní, 1 cesta je v současné době null. Takže pokud chci pokračovat touto cestou vložit tento prvek do trie, Musím malloc nový uzel, má 1 bod tam, a pak jsem dobré jít. 

Takže jsem v podstatě jsem v a místo, kde stojím u kořene stromu nebo pod Trie a tam jsou 10 poboček. Ale každá větev má brána před ním. Správně. Vzhledem k tomu, nic jiného tam. No bezpečný průchod. To znamená, že není nic se některý z těchto větví. Pokud chci začít stavět něco, chci odstranit bránu. Chci odstranit bránu Před číslo 1. A já chci jít dolů, že. A já chci stavět další místo pro mě jít. 

A to je to, co jsem tady udělal. Takže 1 již poukazuje na hodnotu null. Řekl jsem, že to je bezpečné jít dolů teď tady. Postavil jsem jiného uzlu. A když jsem se dostat do tohoto uzlu, I mají další rozhodnutí učinit. Kam mám jít odsud? 

No, já jsem už pryč dolů 1. Takže teď pravděpodobně chtít jít dolů 6. Správně. Opět platí, že mám 10 míst si mohu vybrat. Takže pojďme teď jít dolů číslo 6. Tak jsem vyčistit bránu Před číslo 6. A jdu tam dole. A já vybudovat další uzel. A já jsem dosáhl dalšího spojovací bod. 

Opět platí, že mám 10 možností Pro kam můžu jít. Jsem se přestěhoval od 1 do 6. Takže teď pravděpodobně chtít jít na 3. 3, není kam můžu jít. Takže mám vyčistit cestu a vybudovat sám nový prostor. A pak se z 3, kam chci jít? Chci jít dolů 6. 

A opět jsem musel uvolnit cestu, jak to udělat. Takže teď Použil jsem svůj klíč k vložení vytvoření uzly a začít budovat tento trie. Začal jsem u kořene. Já jsem šel dolů 1636. A teď jsem na dně tam v daném uzlu. A vy jste měli být schopni vidět na obrazovce. 

Je zvýrazněna žlutě. To je místo, kde v současné době jsem já. Můj klíč je hotovo. Já jsem vyčerpal všechny pozice ve svém klíči. Takže nemohu jít dál. Takže v tomto bodě, všechno, co jsem opravdu potřebujete udělat, je říct, OK. Je to trochu jako dívat se dolů na zem, pokud jste si představovat Chcete se tento druh cesty s různými typy připojení. Druh dívat se dolů a druh sprej malování Harvardu na zemi. To je název tohoto. Vězte, že to, co je na tomto místě. Pokud začneme u kořene a jedeme dolů 1 a poté na 6 a pak 3 a pak 6, kde jsme? No, pokud se podíváme dolů a vidíme Harvard, pak víme, že Harvard byl založena v roce 1636 na základě způsobu, jakým budeme provádění tohoto datovou strukturu. Tak to byl snad jednoduchá. Chystáme se udělat dvě další inzerce. A doufejme, že to pomůže, aby vidět toto udělal ještě dvakrát. 

Nyní se pojďme vložit jinou univerzitu. Pojďme vložit Yale do této trie. Yale byl založen v roce 1701. Takže začneme u kořen, jak jsme vždycky dělat. A my jsme nastavili ukazatel traversal. Budeme používat, které pro pohyb. První věc, kterou chceme udělat, je jít dolů na 1 cestu. To je první číslice z našich klíčových. Naštěstí, i když, my ne muset dělat žádnou práci tentokrát. 1 Cesta již byla smazána. Vymazány jsem to již dříve, když jsem byla vložením Harvardu v roce 1636. Takže můžu bezpečně přesunout dolů 1 a prostě jít tam. Pokud se může pohybovat dolů 1. 

A teď, když chci jít až 7. Vymazány jsem, jak na 6. Vím, že můžu bezpečně pokračujte po pěšině 6. Ale musím pokračovat na cestě 7. Takže to, co musím udělat? No, stejně jako předtím, jen potřebuju zrušte bránu, dostat se z cesty, a vytvořit nový uzel z cesty 7. Stejně jako tento. 

Takže teď jsem se přestěhoval 1 a pak 7. A teď si všimnout, že jsem nějak ze dne o této nové subbranch. Správně. Všechno ostatní od 16 , já se nestarám o. Nedělám 16 nic. Dělám 17 věci. 

Takže teď od 17. dne, musím druh objevení nových cest zde. Další číslice můj klíč je 0. Jasně jsem nemůže dostat kamkoliv. Jen jsem postavil tento uzel. Takže vím, že to není cesty vpřed odtud. Takže jsem musel udělat jednu sám. 

Tak jsem malloc nový uzel a mají tam bod 0. A pak ještě jednou, jsem malloc Nový uzel a mají tam jeden bod. Opět platí, že jsem vyčerpal svůj klíč, 1701. Tak jsem se dolů a já sprej malovat Yale. To je jméno tohoto uzlu. 

A tak teď, když jsem někdy potřebovat zjistit, jestli Yale je v tomto trie, začnu u kořene, Jdu dolů 1701, a dívat se dolů. A když vidím Yale sprej malované na zem a poté Vím, že Yale existuje v tomto trie. Udělejme ještě jeden. Pojďme do toho vložit Dartmouth Trie, která byla založena v roce 1769. 

Začněte u kořene znovu. Moje první číslice můj klíč je 1. Mohu bezpečně pohybovat touto cestou. To již existuje. Další číslice mé klíče je 7. Mohu bezpečně pohybovat touto cestou. Existuje také. 

Mé další je 6. Odtud odkud I v současné době jsem žlutě tam v tom středním uzlu, 6 aktuálně uzamčen pryč. Pokud chci jít touto cestou, Musím se postavit to sám. Takže budu malloc nový uzel a mají 6 bod tam. A pak zase, že jsem hořící nové stezky zde. 

Tak jsem malloc nový uzel, takže z že node-- číslo trasy 9-- a pak nyní pokud cestuji 1769, a Podívám se dolů. Není nic, co v současné době nastříkal tam. Dokážu napsat Dartmouth. A já jsem vložena Dartmouth do trie. 

Tak to je vkládání věci do trie. Nyní chceme hledat věci. Jak můžeme hledat věci v trie? No, je to docela hodně stejný nápad. Teď už stačí použít číslice klíče aby zjistil, jestli můžeme přejít od kořene na místo, kde chceme jít v trie. 

Pokud jsme narazili do slepé uličky na jakémkoli místě, pak Víme, že tento prvek nemůže existuje anebo že cesta by již byly vymazány. Pokud budeme dělat to celou cestu do konec, vše, co potřebujete udělat, je dívat se dolů a zjistit, jestli je to prvek hledáme. Pokud je, úspěch. Pokud to není, selhat. 

Takže pojďme hledat Harvard v tomto trie. Začneme u kořene. A opět, budeme vytvořit ukazatel traversal k tomu naše pohyby pro nás. Z kořene víme, že První místo, musíme jít, je 1, můžeme udělat, že? Ano můžeme. Pokud se bezpečně existuje. Můžeme jít tam. 

Nyní, další místo, musíme jít, je 6. Má cesta 6 existovat dál? Jo, je to tak. Můžeme jít po cestě 6. A my jsme se sem. 

Můžeme jít dolů 3 cesty z tady? No, jak to dopadá, ano, že existuje taky. A můžeme dostat na 6 cestě odsud? Ano můžeme. 

Ještě jsme se úplně odpověděl otázka dosud. Je tu ještě jeden krok, který je nyní musíme se podívat dolů a zjistit, jestli je to actually-- pokud hledáme Harvardu, je to, že Co jsme zjistili, když jsme vyčerpat klíč? V příkladu jsme pomocí tady, roky jsou vždy čtyři číslice. Ale ty by mohly být pomocí na příklad, kde jsou ukládání slovník slov. 

A tak místo toho, aby 10 ukazatelů pro mé umístění, můžete mít 26. Jeden pro každé písmeno abecedy. A tam jsou některé slova jako netopýr, který je podmnožinou dávky, například. A tak i když se dostanete do konec klíče a dívat se dolů, nemusíte vidět, co hledáte. 

Takže budete mít vždy projít celou cestu a pak pokud jste byli schopni úspěšně procházet celou cestu, dívat se dolů a udělat jednu finální potvrzení. Je to to, co jsem hledal? No, Podívám se dolů po spuštění nahoře a jít 1636. Podívám se dolů. Vidím Harvardu. Takže ano, uspěl jsem. Co jestli to, co Hledám není v trie, ačkoli. Co když jsem hledal Princeton, která byla založena v roce 1746. A tak se stává 1746 můj klíč procházet trie. No, začnu u kořene. A na prvním místě chci se jde dolů na 1 cestu. Mohu to udělat? Ano, mohu. 

Můžu jít po cestě od 7 tam? Jo, můžu. To existuje taky. Ale můžu jít dolů 4 cesty odsud? To je jako ptát na otázku, může Mám postupovat dolů, že malý čtverec že jsem zvýrazněny žlutě? Nic tam není. Správně. 

Neexistuje způsob, jak vpřed dolů 4 cestě. Pokud Princeton bylo v této trie, že 4 by byly vymazány už pro nás. A tak v tomto bodě dosáhli jsme do slepé uličky. Nemůžeme jít dále. A tak můžeme říci, definitivně, no. Princeton neexistuje v tomto trie. 

Takže co to všechno znamená? Správně. Je tu spousta děje. Je tu ukazatele po celém místě. A jak můžete vidět, Jen z diagramu, je tu spousta z uzlů, které jsou druh létání okolo. Povšimněme si ale pokaždé, když jsme chtěli ověřit, zda se něco v trie, jsme měli jen, aby 4 tahy. 

Pokaždé, když jsme chtěli vložit něco v trie, musíme 4 pohyby, případně mallocing nějaké věci podél cesty. Ale jak jsme viděli, když jsme vložena Dartmouth do trie, někdy některé z cesty již může být zrušeno pro nás. A tak jako naše Trie dostane větší a větší, musíme dělat méně práce pokaždé, vložit nové věci protože jsme už postavený hodně meziproduktu větve podél cesty. Pokud budeme jen někdy se podívat na 4 věci, 4 je jen konstantní. Opravdu jsme se trochu blíží konstantní vložení čas a konstantní čas vyhledávání. Kompromis, samozřejmě, je, že Trie to, jak si asi říct, je obrovský. Každý z těchto uzlů zabírá hodně místa. 

Ale to je kompromis. Chceme-li opravdu rychle vložení, opravdu rychlý vymazání, a opravdu rychle vyhledávání, musíme mají velké množství dat létající kolem. Musíme vyčlenit hodně prostoru a paměť pro tuto strukturu dat existovat. 

A tak to je kompromis. Ale vypadá to, že Možná ho našli. Mohli jsme zjistili, že svatý grál datových struktur s rychlým zavedením, smazání a vyhledávání. A možná to bude vhodné datové struktury použít pro jakékoliv informace, snažíme se obchodu. Jsem Doug Lloyd, to je cs50.