>> 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.
>> Strike štyri.
Som mimo.
Prepáčte.
Ospravedlňujeme sa za osobu, ktorá ak má upraviť tento zblázniť.
>> Prepáčte.
Prepáčte.
>> SPEAKER 1: Výborne.
To bolo naozaj dobre.