KEVIN SCHMID: Niekedy, pri stavbe Program, možno budete chcieť využiť dátové štruktúry známe ako slovník. Slovník kľúče mapy, ktoré sú zvyčajne reťazca, hodnôt, ints, znaky, ukazovateľ na nejaký predmet, čo chceme. Je to ako obyčajné slovníky že mapa slová cez definícií. 

Slovníky nám poskytujú schopnosť ukladať informácie spojené s niečím a pozrieť sa na to neskôr. Tak ako sme sa vlastne vykonávať slovník, povedzme, C kódu, ktorý môžeme použitie v jednom z našich programov? No, existuje mnoho spôsobov, ako by sme mohli realizovať slovník. 

Pre jedného, ​​mohli by sme použiť pole, ktoré sme dynamicky re-size, alebo môžeme použiť spájať zoznam, hash tabuľka alebo binárny strom. Ale nech si vyberieme, mali by sme dbať na efektivitu a výkon implementácie. Mali by sme premýšľať o použitom algoritme vložiť a vyhľadať položky do naše dátová štruktúra. 

Teraz predpokladajme, že sme chcete používať reťazca ako kľúče. Poďme sa baviť o jednej z možností, dátová štruktúra sa nazýva trie. Tak tu je vizuálna reprezentácia z trie. 

Ako obrázok naznačuje, trie je dátový stromová štruktúra s uzly spojené. Vidíme, že tam je jasne koreň Uzol sa niektoré odkazy sa rozširuje ostatné uzly. Ale to, čo robí každý uzol sa skladá z? Ak budeme predpokladať, že sme ukladanie kľúčov s iba abecedné znaky, a my sa nestaráme o kapitalizácii, Tu je definícia uzla, ktorý bude stačiť. 

Objekt, ktorého typ struct uzol má dve časti volal dát a deti. Nechali sme časť dát ako komentár byť nahradená zložkou Vyhlásenie keď struct uzol je začlenené do programu C. Dátová časť uzla môže byť Logická hodnota označujúci, či alebo Nie je uzol reprezentuje dokončenie zo slovníka kľúče, alebo by to mohlo byť Reťazec predstavujúce definíciu na slová v slovníku. 

Budeme používať smajlíky ukázať , Ak je prítomná dát v uzle. Existuje 26 prvkov v našom deti poľa, jeden index podľa abecedy. Uvidíme význam z toho čoskoro. 

Poďme sa bližšie pozrieť na koreňový uzol v našom diagrame, ktorý nemá žiadne dáta spojené s tým, ako je uvedené absencia smajlíka v Dátová časť. Šípky vyčnievať z častí Deti pole reprezentujú non-uzol odkazy na iné uzly. Napríklad, šípka siahajúce od druhý prvok detí predstavuje písmeno B v slovníku kľúč. A vo väčšom diagrame sme to označenie s B. 

Všimnite si, že v širšom schéme, kedy sme nakresliť ukazovateľ do iného uzla, je Nezáleží na tom, kde sa šípka odpovedá, že iný uzol. Náš vzorka slovník trie obsahuje dve slová, ktorá aj zoom. Poďme sa prejsť príklad vyhľadávanie dát na kľúč. 

Predpokladajme, že sme sa chceli pozrieť do zodpovedajúcu hodnotu kľúča kúpele. Začneme náš pohľad hore na koreňový uzol. Potom budeme mať prvé písmeno nášho kľúč, B, a nájsť zodpovedajúce mieste v našom deti poli. Všimnite si, že tam je presne 26 miest v poli, jeden pre každé písmeno abeceda. A budeme mať škvrny predstavujú písmená abecedy v poradí. 

My sa pozrieme na druhý index potom, index jeden, pre B. Všeobecne platí, že ak by sme nejaké abecedný znak C my by mohla stanoviť zodpovedajúce miesto v detskom poľa pomocou Výpočet takto. Mohli sme použiť väčšie deti pole, ak by sme chceli ponúknuť look up kľúče s širším rozsahu znakov, ako je celé Znaková sada ASCII. 

V tomto prípade, ukazovateľ v našom deti poľa v index jeden nie je null. Takže budeme naďalej hľadať up kľúče kúpele. Ak sa niekedy stretli nulový ukazovateľ na správnom mieste, u detí pole, keď sme sa prejsť uzly, potom budeme musieť povedať, že sme nemohol nájsť nič pre tento kľúč. 

Teraz budeme mať druhý list náš kľúč, a ďalej po ukazovatele týmto spôsobom, kým sa dostať sa na koniec nášho kľúče. Ak sa dostanete na koniec kľúča, bez toho, aby zasiahla všetky slepej uličky, null ukazovatele, ako je tomu v tomto prípade, potom iba je nutné skontrolovať ešte jednu vec. Je to kľúč skutočne v slovníku? 

Ak áno, mali by sme nájsť hodnotu, dobre smiley ikona tvár v našom diagrame, kde slovo končí. Ak tam je niečo iné, ukladajú sa dáta, potom sa môžeme vrátiť. Napríklad, kľúč nie je v zoo slovník, aj keď sme mohli mať dosiahol na konci tohto kľúča, bez toho, aby biť nulový ukazovateľ, zatiaľ čo my iterovat trie. 

Ak sme sa snažili vyhľadať kľúčové kúpeľ, Druhý index poľa minulého uzla, zodpovedajúce písmeno H, by držali nulový ukazovateľ. Takže kúpeľ nie je v slovníku. A tak trie je unikátny v tom, že kľúče sa nikdy výslovne uložené v dátová štruktúra. Tak ako sme sa vložiť niečo do trie? 

Poďme vložte kľúč zoo do nášho trie. Pamätajte si, že smajlíky v uzle mohla odpovedať v kóde na jednoduchej Boolovská hodnota, ktorá naznačujú, že zoo je v slovníku, alebo by to mohlo zodpovedajú viac informácií, ktoré sme chcete spojiť s kľúčovým zoo, ako vymedzenie Slovo alebo niečo iné. V niektorých ohľadoch, proces vložiť niečo do trie je podobný hľadá niečo v trie. 

Začneme s koreňový uzol znovu, Nasledujúce ukazovatele zodpovedá listy z našich kľúčových. Našťastie sme boli schopní sledovať ukazovatele celú cestu až sme dorazili do koniec kľúča. Vzhľadom k tomu, zoo je prefix slová zoom, ktorý je členom slovník, nepotrebujeme, aby prideliť žiadne nové uzly. 

Môžeme upraviť uzol čo znamená, že cesta znakov, ktoré vedú k predstavuje kľúč v našom slovníku. Teraz skúsme vloženie Kľúčovým BATH do trie. Začneme na koreňový uzol a sledovať ukazovatele znova. Ale v tejto situácii, zasiahla sme mŕtvy skončí skôr, než sme schopní sa dostať do koniec kľúča. Teraz budeme musieť prideliť niektoré nové uzly budú musieť prideliť jednu novú uzol pre každý zostávajúci List z nášho kľúča. 

V tomto prípade, my jednoducho potrebujeme prideliť jeden nový uzol. Potom budeme potrebovať, aby index H odkázanie na nový uzol. Opäť môžeme zmeniť uzol ukazujú, že cesta znakov čo vedie k tomu predstavuje kľúč v našom slovníku. Poďme uvažovať o asymptotickej Komplexnosť našich postupov pre tieto dve operácie. 

Všimli sme si, že v oboch prípadoch číslo z krokov náš algoritmus trvalo bola úmerná počtu Písmená na kľúčové slovo. To je pravda. Ak chcete vyhľadať slovo v trie stačí iterovat listy jeden po druhom, kým buď dostanete na koniec slova, alebo hit slepej uličky v trie. 

A keď budete chcieť vložiť kľúč hodnota dvojice do trie pomocou Postup sme diskutovali, najhorší prípad bude vám pridelenie nového uzla pre každé písmeno. A budeme predpokladať, že rozdelenie je konštantný čas prevádzky. Takže ak budeme predpokladať, že dĺžka kľúča je ohraničená pevnú konštantou, a to ako vkladanie a vyhľadať konštantný časové operácie pre trie. 

Ak sa nám nepodarí túto domnienku, že dĺžka kľúča je ohraničená pevnú konštantný, potom sa po vložení a pozerať sa, V najhoršom prípade, sú lineárne v dĺžka kľúča. Všimnite si, že počet položiek, uložené v trie nemá vplyv na vzhľad hore alebo vloženie čas. Je to len vplyv dĺžka kľúča. 

Naopak, pridávanie položiek, povedzme, hash tabuľky vedie k tomu, budúcnosť vyzerať pomalšie. Aj keď to môže znieť ako lákavá na prvý pohľad, by sme mali mať na pamäti, že priaznivé Asymptotická zložitosť nie je znamená, že v praxi sú dáta štruktúra je nutne nič vytknúť. Musíme tiež vziať do úvahy, že na ukladanie slovo v trie potrebujeme, v najhoršom prípad, počet uzlov úmerná k dĺžke slova. 

Pokúsi majú tendenciu používať veľa priestoru. To je na rozdiel od hash tabuľky, kde budeme potrebovať iba jeden nový uzol uložiť niektoré dvojice kľúč hodnota. Teraz, opäť teoreticky, veľký priestor Spotreba nevyzerá ako veľký riešiť, a to najmä vzhľadom na to, moderné počítače majú gigabajtov a GB pamäte. Ale ukázalo sa, že máme stále sa starať o využitie pamäte a organizácie v záujme výkon, pretože moderné počítače majú mechanizmy v mieste pod kapucňa urýchliť prístup do pamäte. 

Ale tieto mechanizmy fungujú najlepšie, keď pamäťové prístupy sú v kompaktnom regióny alebo oblasti. A uzly trie mohla zdržiavať kdekoľvek v tejto hromade. Ale to sú kompromisy že musíme vziať do úvahy. 

Pamätajte si, že pri výbere dát štruktúra pre určitú úlohu, sa by mal premýšľať o tom, aké druhy operácie dátová štruktúra musí Podpora a koľko výkonu každého z nich operácie záleží na nás. Tieto operácie môžu dokonca presahujú len Základný vzhľad a vloženie. Predpokladajme, že by sme chceli zaviesť akúsi automatického dokončovania funkcií, veľa ako vyhľadávač Google robí. To znamená, že vráti všetky kľúče a potenciálne hodnoty, ktoré majú danú predponu. 

Trie je jednoznačne užitočná pre túto operáciu. Je to jednoduché iterácii trie pre každý znak prefix. Rovnako ako sa pozrieť do prevádzky, sme mohli sledovať ukazovatele znak po znaku. Potom, keď dorazíme na koniec prefix, môžeme iterovat Zostávajúca časť dátovej štruktúry pretože každá z kľúčov po Tento bod má predponu. 

Je tiež ľahké získať tento zápis v abecednom poradí od prvky detského pole sú radené abecedne. Takže dúfajme, že budete uvažovať dávanie sa snaží vyskúšať. Ja som Kevin Schmid, a to je CS50. 

Ach, to je začiatok poklesu. Je mi to ľúto. Prepáčte. Prepáčte. Prepáčte. 

Strike štyri. Som mimo. Prepáčte. Prepáčte. Prepáčte. Ospravedlňujeme sa za osobu, ktorá ak má upraviť tento zblázniť. 

Prepáčte. Prepáčte. Prepáčte. Prepáčte. 

SPEAKER 1: Výborne. To bolo naozaj dobre.