[Prehrávanie hudby] DOUG LLOYD: Takže sme boli blíži sa a bližšie, že svätý grál dát štruktúry, ten, ktorý môžeme vložiť do, odstrániť z, a pozerať sa v konštantnom čase. Správne. To je niečo ako ciele. Chceme byť schopní robiť veci veľmi, veľmi rýchlo. 

Už sme ho našli tu, keď hovoríme o pokusoch? Dobre, poďme sa pozrieť. Takže sme videli niekoľko rôzne dátové štruktúry že zvládnuť mapovanie tzv párov kľúč-hodnota, mapovanie nejakú časť dát na nejakú inú časť dát takže vieme, kde nájsť Informácie v štruktúre. 

Takže pre pole, napríklad, Kľúčom k úspechu je index prvok alebo pole Poloha 0 alebo 1 pole, a tak ďalej. A je hodnota údaje že v danom umiestnení existuje. Takže to, čo je uložené v poli 0? To, čo je uložený v matici 1 v porovnaní s práve 0 a 1, čo by bolo kľúča. 

S hash tabuľky je to druh z rovnakej myšlienky. S hash tabuľky, máme túto hash funkcia, ktorá generuje hash kódy. Takže kľúč je hash kód dát. A hodnota, najmä sme sa rozprávali o reťazenie vo videu na stoly mriežky, je to, že spojená zoznam údajov, že hash k tomuto hashCode. Správne. Čo iného prístupu Táto metóda, aj keď? Ako je to spôsob, kde Kľúčom je zaručené, že je jedinečný, na rozdiel od tabuľky hash, kde by sme mohli skončiť s dvoma kusmi dát ktoré majú rovnakú hodnotu hash. A potom máme čo do činenia s že buď snímania alebo viac prednostne reťazenie vyriešiť tento problém. 

Takže teraz môžeme zaručiť že náš kľúč bude jedinečná. A čo keď naša hodnota bola proste niečo tak jednoduché ako true a false, ktorá nám hovorí, či či nie, že časť informácie existuje v štruktúre? Boolovská môže byť rovnako jednoduché ako trochu. Reálne je to asi byte s väčšou pravdepodobnosťou ako trochu. Ale to je oveľa menšie, než uloženie možná 50-reťazec znakov, napríklad. 

Takže pokusoch, podobne ako hash tabuľky, ktoré kombinujú polia a spájať zoznam, snaží kombinovať polia, štruktúry, a ukazovatele spoločne ukladať dáta v zaujímavý spôsob, ako to je celkom odlišný od čokoľvek, čo sme doteraz videli. Teraz budeme používať dáta ako cestovná mapa navigovať túto štruktúru dát. A ak môžeme sledovať Cestovná mapa, ak môžeme nasledovať dáta z začiatku až do konca, budeme vedieť, či týchto dát existujú v trie. 

A keď nemôžeme sledovať mapu čo znamená, ze do konca vôbec, dáta nemôže existovať. Opäť platí, že tu sú kľúče zaručená jedinečnosť. A tak na rozdiel od stola mriežky, budeme nikdy budú musieť vysporiadať s kolíziami tu. A žiadne dva kusy dát majú presne rovnaký plán ibaže, že údaje sú totožné. 

Ak vložíme John, potom hľadáme pre Johna. To je dve identické kusy Údaje, vpravo, pozeráme skrz. Ale inak, akákoľvek dva kusy dát sú zaručené, že majú jedinečné plány prostredníctvom tejto dátovej štruktúry. A budeme sa pozrieť na vizuálne to za chvíľu. 

Urobíme to, že sa snaží vytvoriť novú dátovú štruktúru, mapovanie tieto dvojice hodnoty kľúča. V tomto prípade, nebudeme používať niečo tak jednoduchého, ako Boolean. Vlastne sme uloží reťazec. A to reťazec sa chystá byť názov vysokej školy. 

A kľúč bude rok kedy bola založená, že vysokoškolské. Všetky roky pre vysoké školy sa bude štyri číslice. A tak budeme používať tie štyri číslice prechádzať tejto dátové štruktúry. A uvidíme, opäť, ako urobíme, že v len sekundu. 

Na konci dráhy, uvidíme meno univerzity, ktorá zodpovedá k tlačidlu, tieto štyri číslice. Základnou myšlienkou trie je máme centrálne trasu. Takže myslíte, že o tom ako strom. A toto je podobné v hláskovanie a v poňatí k stromu. Všeobecne platí, keď si myslíme, že o stromy v reálnom svete, majú koreň, ktorý je v pozemné a rastú nahor a oni majú pobočky a majú listy. A v podstate myšlienka Trie je presne rovnaký, s výnimkou, že koreň je ukotvený niekde na oblohe. A listy sú v spodnej časti. 

Takže je to trochu ako s strom a len preklopeniu hore nohami. Ale sú tu ešte pobočky. A tí by sa naše cesty, tie budú naše spoje z koreňa do listov. V tomto prípade, tí, ciest, tieto pobočky sú označené číslicami, ktoré vypovedajú kadiaľ ísť z miesta, kde sme. 

Ak vidíme 0, pôjdeme dole tohto odvetvia, ak vidíme 1, pôjdeme dole tohto odvetvia, a tak, a tak ďalej. No, čo to znamená? No, to znamená, že v každom spojovacom mieste a každý uzol vo prostrednej a každá vetva, tam sú 10 možný miest, ktoré môžeme ísť. Takže existuje 10 ukazovateľov z každého miesta. 

A to je miesto, kde sa pokúsi sa dostať trochu zastrašujúce pre niekoho kto ich nemá veľa skúsenosti v oblasti počítačovej vedy pred. Ale snaží sú naozaj dosť desivý. A ak máte možnosť pracovať s nimi a ste ochotní kopať-in a experimentovať s nimi, sú naozaj celkom zaujímavé dátové štruktúry pre prácu s. Ak chceme vložiť prvok do trie, všetko, čo potrebujete urobiť, je vytvoriť správnu cestu z koreňa do listu. Tu je to, čo na každom kroku pozdĺž spôsob, ako by mohla vyzerať. Budeme definovať nové údaje štruktúra pre nový uzol nazývaný trie. 

A vo vnútri týchto údajov Štruktúra existujú dva kusy. Chystáme sa ukladať meno univerzity. A budeme uchovávať poľa ukazovateľov do iných uzlov rovnakého typu. Takže, znovu, je to, že druh z koncepcie všade my sme, sme na 10 možný miesta môžeme ísť. Ak vidíme 0, pôjdeme dole toto odvetvie. Ak budeme vidieť 1, toto odvetvie, a tak ďalej, a tak ďalej a tak ďalej. Ak hovoríme, 9, pôjdeme dole toto odvetvie. Takže v každom spojovacom mieste, môžeme ísť 10 možných miest. Každý uzol tak musí obsahovať 10 ukazovatele do iných uzlov, do 10 ostatných uzlov. 

A dáta, my ich ukladanie len názov univerzity. Takže poďme postaviť trie. Poďme vložiť pár predmetov do našich trie. Takže na samom vrchole, to je náš koreň. Toto je pravdepodobne bude niečo budete globálne vyhlasujú. A vy budete globálne udržanie ukazovateľ na tento uzol vždy. 

Budeš hovoriť, koreň rovná, a vy ste bude malloc sami trie uzol. A vy nikdy dotknúť koreň znova. Zakaždým, keď budete chcieť prehliada, môžete nastaviť ďalšie ukazovatele rovnajúcu sa koreň, ako je napríklad tráv, čo je príklad I použitie v mnohých mojich videí tu na komíny a fronty a odkaz zoznamy, a tak ďalej. 

Môžete nastaviť inú ukazovateľ volal tráv umožňujúcim priechod. A používate tráv k navigácii cez dátové štruktúry. Tak uvidíme, ako to môže vyzerať. Takže teraz, čo robí uzol vyzerá? No, rovnako ako naše dáta Vyhlásenie štruktúra je uvedené, Máme reťazec, ktorý v tomto prípade je prázdny. Tu nič nie je. 

A pole 10 ukazovateľov. A práve teraz, my len má 1 uzol v tomto trie. Na tom nie je nič iné v ňom. Takže všetko 10 z tých, ukazovatele bod na hodnotu null. To je to, čo červená indikuje. 

Poďme vložte reťazec Harvard. Poďme vložte univerzita Harvard do tejto trie, ktorý bola založená v roku 1636. Chceme použiť kľúč, 1.636, nám povedať, kde sme bude ukladať Harvard v trie. Teraz, ako by to urobíme? 

Mohlo by to vyzerať nejako takto. Začneme pri koreni. A máme týchto 10 miest, môžeme ísť. Koreň je rovnako ako akýkoľvek iný uzol trie. K dispozícii je 10 miest, môžeme prejsť od tady. 

Kam pravdepodobne chceme kam ísť, ak je kľúč 1636? Je to naozaj dve možnosti. Správne. Môžeme vytvoriť kľúč od sprava doľava a začať s 6. Alebo by sme mohli postaviť kľúč zľava doprava a začať s 1. 

Je to pravdepodobne viac intuitívne ako ľudská bytosť porozumieť budeme Stačí ísť zľava doprava. A tak, keď chcem vložiť Harvard do tejto trie, Asi Chcem začať tým, že začína pri koreni, pri pohľade na mojej 10 možností predo mnou, a povedal Chcem ísť dole 1 cestu. OK. 

Teraz, 1 cesta je v súčasnej dobe null. Takže ak chcem pokračovať touto cestou vložiť tento prvok do trie, Musím malloc nový uzol, má 1 bod tam, a potom som dobré ísť. 

Takže som v podstate som v a miesto, kde stojím pri koreni stromu alebo pod Trie a tam sú 10 pobočiek. Ale každá vetva má brána pred ním. Správne. Vzhľadom k tomu, nič iné tam. No bezpečný priechod. To znamená, že nie je nič sa niektorý z týchto vetiev. Ak chcem začať stavať niečo, chcem odstrániť bránu. Chcem odstrániť bránu Pred číslo 1. A ja chcem ísť dole, že. A ja chcem stavať ďalšie miesto pre mňa ísť. 

A to je to, čo som tu urobil. Takže 1 už poukazuje na hodnotu null. Povedal som, že to je bezpečné ísť dole teraz tu. Postavil som iného uzla. A keď som sa dostať do tohto uzla, I majú ďalšie rozhodnutie urobiť. Kam mám ísť odtiaľto? 

No, ja som už preč dolu 1. Takže teraz pravdepodobne chcieť ísť dole 6. Správne. Opäť platí, že mám 10 miest si môžem vybrať. Takže poďme teraz ísť dole číslo 6. Tak som vyčistiť bránu Pred číslo 6. A idem tam dole. A ja vybudovať ďalšie uzol. A ja som dosiahol ďalšieho spojovací bod. 

Opäť platí, že mám 10 možností Pre kam môžem ísť. Som sa presťahoval od 1 do 6. Takže teraz pravdepodobne chcieť ísť na 3. 3, nie je kam môžem ísť. Takže mám vyčistiť cestu a vybudovať sám nový priestor. A potom sa z 3, kam chcem ísť? Chcem ísť dole 6. 

A opäť som musel uvoľniť cestu, ako to urobiť. Takže teraz Použil som svoj kľúč k vloženie vytvoreniu uzly a začať budovať tento trie. Začal som pri koreni. Ja som išiel dole 1636. A teraz som na dne tam v danom uzle. A vy ste mali byť schopní vidieť na obrazovke. 

Je zvýraznená žltou farbou. To je miesto, kde v súčasnej dobe som ja. Môj kľúč je hotovo. Ja som vyčerpal všetky pozície vo svojom kľúči. Takže nemôžem ísť ďalej. Takže v tomto bode, všetko, čo som naozaj potrebujete urobiť, je povedať, OK. Je to trochu ako pozerať sa dole na zem, ak ste si predstavovať Chcete sa tento druh cesty s rôznymi typmi pripojenia. Druh pozerať sa dole a druh sprej maľovanie Harvarde na zemi. To je názov tohto. Vedzte, že to, čo je na tomto mieste. Ak začneme pri koreni a ideme dole 1 a potom na 6 a potom 3 a potom 6, Kde sme? No, ak sa pozrieme dolu a vidíme Harvard, potom vieme, že Harvard bol založená v roku 1636 na základe spôsobu, akým budeme vykonávanie tohto dátovú štruktúru. Tak to bol snáď jednoduchá. Chystáme sa urobiť dve ďalšie inzercie. A dúfajme, že to pomôže, aby vidieť toto urobil ešte dvakrát. 

Teraz sa poďme vložiť inú univerzitu. Poďme vložiť Yale do tejto trie. Yale bol založený v roku 1701. Takže začneme u koreň, ako sme vždy robiť. A my sme nastavili ukazovateľ traversal. Budeme používať, ktoré pre pohyb. Prvá vec, ktorú chceme urobiť, je ísť dole na 1 cestu. To je prvá číslica z našich kľúčových. Našťastie, aj keď, my nie musieť robiť žiadnu prácu tentoraz. 1 Cesta už bola vymazaná. Vymazané som to už skôr, keď som bola vložením Harvarde v roku 1636. Takže môžem bezpečne presunúť nadol 1 a jednoducho ísť tam. Ak sa môže pohybovať dole 1. 

A teraz, keď chcem ísť až 7. Vymazané som, ako na 6. Viem, že môžem bezpečne pokračujte po chodníku 6. Ale musím pokračovať na ceste 7. Takže to, čo musím urobiť? No, rovnako ako predtým, len potrebujem zrušte bránu, dostať sa z cesty, a vytvoriť nový uzol z cesty 7. Podobne ako tento. 

Takže teraz som sa presťahoval 1 a potom 7. A teraz si všimnúť, že som nejako z o tejto novej subbranch. Správne. Všetko ostatné od 16 , Ja sa nestarám o. Nerobím 16 nič. Robím 17 veci. 

Takže teraz od 17. dňa, musím druh objavenie nových ciest tu. Ďalšie číslica môj kľúč je 0. Jasne som nemôže dostať kamkoľvek. Len som postavil tento uzol. Takže viem, že to nie je cesty vpred odtiaľ. Takže som musel urobiť jednu sám. 

Tak som malloc nový uzol a majú tam bod 0. A potom ešte raz, som malloc Nový uzol a majú tam jeden bod. Opäť platí, že som vyčerpal svoj kľúč, 1701. Tak som sa dole a ja sprej maľovať Yale. To je meno tohto uzla. 

A tak teraz, keď som niekedy potrebovať zistiť, či Yale je v tomto trie, začnem pri koreni, Idem dole 1701, a pozerať sa dole. A keď vidím Yale sprej maľované na zem a potom Viem, že Yale existuje v tomto trie. Urobme ešte jeden. Poďme do toho vložiť Dartmouth Trie, ktorá bola založená v roku 1769. 

Začnite pri koreni znova. Moja prvá číslica môj kľúč je 1. Môžem bezpečne pohybovať touto cestou. To už existuje. Ďalšie číslica mojej kľúča je 7. Môžem bezpečne pohybovať touto cestou. Existuje tiež. 

Moje ďalšie je 6. Odtiaľ odkiaľ Aj v súčasnej dobe som žlto tam v tom strednom uzla, 6 aktuálne uzamknutý preč. Ak chcem ísť touto cestou, Musím sa postaviť to sám. Takže budem malloc nový uzol a majú 6 bod tam. A potom zase, že som horiace nové chodníky tu. 

Tak som malloc nový uzol, takže z že node-- číslo trasy 9-- a potom teraz ak cestujem 1769, a Pozriem sa dole. Nie je nič, čo v súčasnej dobe nastriekal tam. Dokážem napísať Dartmouth. A ja som vložená Dartmouth do trie. 

Tak to je vkladanie veci do trie. Teraz chceme hľadať veci. Ako môžeme hľadať veci v trie? No, je to celkom veľa rovnaký nápad. Teraz už stačí použiť číslica kľúče aby zistil, či môžeme prejsť od koreňa na miesto, kde chceme ísť v trie. 

Ak sme narazili do slepej uličky na akomkoľvek mieste, potom Vieme, že tento prvok nemôže existuje alebo že cesta by už boli vymazané. Ak budeme robiť to celú cestu do koniec, všetko, čo potrebujete urobiť, je pozerať sa dole a zistiť, či je to prvok hľadáme. Ak je, úspech. Ak to nie je, zlyhať. 

Takže poďme hľadať Harvard v tomto trie. Začneme pri koreni. A opäť, budeme vytvoriť ukazovateľ traversal k tomu naše pohyby pre nás. Z koreňa vieme, že Prvé miesto, musíme ísť, je 1, môžeme urobiť, že? Áno, môžme. Ak sa bezpečne existuje. Môžeme ísť tam. 

Teraz, ďalšie miesto, musíme ísť, je 6. Má cesta 6 existovať ďalej? Jo, je to tak. Môžeme ísť po ceste 6. A my sme sa sem. 

Môžeme ísť dole 3 cesty z tu? No, ako to dopadá, áno, že existuje taky. A môžeme dostať na 6 ceste odtiaľto? Áno, môžme. 

Ešte sme sa úplne odpovedal otázka doteraz. Je tu ešte jeden krok, ktorý je teraz musíme sa pozrieť dole a zistiť, či je to actually-- ak hľadáme Harvardu, je to, že Čo sme zistili, keď sme vyčerpať kľúč? V príklade sme pomocou tu, roky sú vždy štyri číslice. Ale tie by mohli byť pomocou na príklad, kde sú ukladanie slovník slov. 

A tak namiesto toho, aby 10 ukazovateľov pre moje umiestnenie, môžete mať 26. Jeden pre každé písmeno abecedy. A tam sú niektoré slová ako netopier, ktorý je podmnožinou dávky, napríklad. A tak aj keď sa dostanete do koniec kľúče a pozerať sa dole, nemusíte vidieť, čo hľadáte. 

Takže budete mať vždy prejsť celú cestu a potom ak ste boli schopní úspešne prechádzať celú cestu, pozerať sa dole a urobiť jednu finálnu potvrdenie. Je to to, čo som hľadal? No, Pozriem sa dolu po spustení hore a ísť 1636. Pozriem sa dolu. Vidím Harvarde. Takže áno, uspel som. Čo či to, čo Hľadám nie je v trie, hoci. Čo keď som hľadal Princeton, ktorá bola založená v roku 1746. A tak sa stáva 1746 môj kľúč prechádzať trie. No, začnem pri koreni. A na prvom mieste chcem sa ide dole na 1 cestu. Môžem to urobiť? Áno môžem. 

Môžem ísť po ceste od 7 tam? Jo, môžem. To existuje taky. Ale môžem ísť dole 4 cesty odtiaľto? To je ako pýtať na otázku, môže Mám postupovať dole, že malý štvorec že som zvýraznené žlto? Nič tam nie je. Správne. 

Neexistuje spôsob, ako vpred dole 4 ceste. Ak Princeton bolo v tejto trie, že 4 by boli vymazané už pre nás. A tak v tomto bode dosiahli sme do slepej uličky. Nemôžeme ísť ďalej. A tak môžeme povedať, definitívne, no. Princeton neexistuje v tomto trie. 

Takže čo to všetko znamená? Správne. Je tu veľa deje. Je tu ukazovatele po celom mieste. A ako môžete vidieť, Len z diagramu, je tu veľa z uzlov, ktoré sú druh lietania okolo. Povšimnime si ale zakaždým, keď sme chceli overiť, či sa niečo v trie, sme mali len, aby 4 ťahy. 

Zakaždým, keď sme chceli vložiť niečo v trie, musíme 4 pohyby, prípadne mallocing nejaké veci pozdĺž cesty. Ale ako sme videli, keď sme vložená Dartmouth do trie, niekedy niektoré z cesty už môže byť zrušené pre nás. A tak ako naše Trie dostane väčšie a väčšie, musíme robiť menej práce zakaždým, vložiť nové veci pretože sme už postavený veľa medziproduktu vetvy pozdĺž cesty. Ak budeme len niekedy sa pozrieť na 4 veci, 4 je len konštantná. Naozaj sme sa trochu blíži konštantný vloženie čas a konštantný čas vyhľadávania. Kompromis, samozrejme, je, že Trie to, ako si asi povedať, je obrovský. Každý z týchto uzlov zaberá veľa miesta. 

Ale to je kompromis. Ak chceme naozaj rýchlo vloženie, naozaj rýchly vymazanie, a naozaj rýchlo vyhľadávania, musíme majú veľké množstvo dát lietajúce okolo. Musíme vyčleniť veľa priestoru a pamäť pre túto štruktúru dát existovať. 

A tak to je kompromis. Ale vyzerá to, že Možno ho našli. Mohli sme zistili, že svätý grál dátových štruktúr s rýchlym zavedením, zmazanie a vyhľadávanie. A možno to bude vhodné dátové štruktúry použiť pre akékoľvek informácie, snažíme sa obchodu. Som Doug Lloyd, to je CS50.