KEVIN SCHMID: Joskus, kun rakennus ohjelma, sinun kannattaa käyttää tietojen rakenne tunnetaan sanakirja. Sanakirja kartat avaimet, jotka ovat yleensä jouset, arvoihin, ints, merkkiä, osoitin jonkin esineen, mitä haluamme. Se on aivan kuin tavallinen sanakirjoja että kartta sanansa määritelmiä. 

Sanakirjoja meille kyky tallentaa tietoja liittyy jotain ja etsiä se myöhemmin. Miten siis käytännössä soveltamaan sanakirja vaikkapa C-koodia, että voimme käyttää yksi meidän ohjelmia? No, on olemassa paljon tapoja, jotka voisimme toteuttaa sanakirja. 

Yhden, voisimme käyttää array että me dynaamisesti uudelleen koko tai voisimme käyttää linkitetty lista, tiiviste tai binääripuu. Mutta mitä me valitsemme, meidän pitäisi olla tietoinen tehokkuuden ja suorituskykyä täytäntöönpanoa. Meidän pitäisi ajatella käytetty algoritmi lisätä ja etsiä kohteet meidän tietorakenne. 

Nyt Oletetaan, että meillä haluat käyttää merkkijonojen avaimina. Puhutaanpa yksi mahdollisuus, data rakennetta kutsutaan triellä. Joten tässä on visuaalisesti of trie. 

Kuten kuvasta voi päätellä, triellä on puu datarakennetta solmut liittyvät toisiinsa. Näemme, että siellä on selvästi root solmu joitakin yhteyksiä ulottuu muut solmut. Mutta mitä kukin solmu koostuu? Jos oletamme, että olemme tallentaa avaimet vain kirjaimia ja emme välitä arvo, tässä on määritelmä solmu, joka riittää. 

Objektin, jonka tyyppi on struct solmulla on kaksi osaa nimeltään tietojen ja lapsia. Olemme jättäneet dataosa kommenttina korvataan osa ilmoitusta, jos struct solmu on sisällytetty C-ohjelma. Tieto-osa solmu voi olla Boolean arvo, joka ilmaisee, onko ei solmu edustaa loppuun sanakirjan avaimen tai se voi olla string edustavat määritelmän sanan sanakirjasta. 

Käytämme hymiö kasvot osoittamaan kun data on läsnä solmussa. On 26 elementtejä meidän lasten joukko, yksi indeksi per kirjain. Näemme merkitystä tämän pian. 

Mennään lähemmin juurisolmun meidän kaaviossa, joka ei ole tietoja liittyy siihen, kuten on esitetty Koska hymiö kasvot tieto-osan. Nuolet, jotka ulottuvat osista lapset array edustavat ei-solmun viitteitä muihin solmuihin. Esimerkiksi nuoli ulottuu toinen elementti lasten edustaa kirjain B sanakirjasta näppäintä. Ja suurempi kaaviossa merkitsemme sen B. 

Huomaa, että suurempi kaaviossa, kun piirtää osoittimen toiseen solmuun, se ei ole väliä missä nuolenkärki täyttää, että muut solmu. Meidän näyte sanakirja triestä sisältää kaksi sanaa, jotka ja zoom. Käydään läpi esimerkki etsii tietoja avaimen. 

Oletetaan halusimme etsiä vastaava arvo avaimen kylpy. Aloitamme meidän look up juurisolmusta. Sitten otamme ensimmäisen kirjaimen meidän näppäintä, B, ja löytää vastaava Spot lapsemme array. Huomaa, että on olemassa täsmälleen 26 paikkoja array, yksi kutakin kirjeellä aakkoset. Ja meillä on paikkoja edustavat aakkosten järjestyksessä. 

Me tarkastelemme toisen indeksin sitten indeksi yhdestä, B. Yleensä, jos me on joitakin kirjain C me voisi määrittää vastaavan paikalla lapsissa array laskelma näin. Olisimme voineet käyttää isommille lapsille array jos halusimme tarjota look up näppäimet, joilla on laajempi valikoima merkkejä, kuten koko ASCII-merkistön. 

Tässä tapauksessa osoitin lapsemme array at indeksi yksi ei ole nolla. Niin me etsimme edelleen ylös-näppäintä kylpyamme. Jos me koskaan kohdannut nollaosoittimen oikeassa paikalla lapsia array kun me kulki solmut, Sitten meidän täytyy sanoa, että me ei löytänyt mitään, että avain. 

Nyt otamme toisen kirjeellä keskeisiä, ja jatka noudattaen viitteitä tällä tavoin, kunnes me päähän keskeisiä. Jos me päähän avaimen ilman lyödä mitään umpikujia, null osoittimia, kuten tässä tapauksessa, niin me vain täytyy tarkistaa yksi asia. Onko tämä avain todella sanakirjassa? 

Jos näin on, meidän pitäisi löytää arvo, hyvin hymiö ilme meidän kaavio, jossa sana päättyy. Jos on jotain muuta tallennetaan tietoa, niin voimme palauttaa sen. Esimerkiksi avain eläintarha ei ole sanakirja, vaikka olisimme voineet lopussa tämän keskeisen ilman koskaan lyömällä nollaosoittimen, kun me kerrata trien läpi. 

Jos yritimme etsiä avain kylpyamme, toiseksi viimeinen solmun taulukkoindeksin, vastaava kirjain H, olisi ovat pitäneet nollaosoittimen. Joten kylpy ei ole sanakirjassa. Ja niin trien on ainutlaatuinen siinä, että avaimet ei koskaan nimenomaisesti tallennetaan tietorakennetta. Miten siis lisätä jotain osaksi triestä? 

Katsotaanpa aseta avain Eläintarha meidän triellä. Muista, että hymiö kasvot solmussa voisi vastaavat koodin yksinkertainen Boolean joka osoittaa, että eläintarha löytyy sanakirjasta tai se voi vastaavat enemmän tietoa, joka meillä haluavat yhdistää avaimen eläintarha, kuten määritelmä sana tai jotain muuta. Jollain tavalla, prosessi lisätä jotain osaksi trien on samanlainen kuin etsii jotain triellä. 

Aloitamme juurisolmu uudelleen, seuraavia viitteitä vastaa kirjaimet keskeisiä. Onneksi pystyimme seuraamaan viitteitä aina kunnes saavuimme avaimen päätä. Koska eläintarha on etuliite sanan zoom, joka on jäsenenä sanakirja, meidän ei tarvitse jakaa uusia solmuja. 

Sitä voidaan muokata solmu osoittaa, että polku merkkiä, joka johtaa se on keskeinen meidän sanakirja. Nyt, kokeile asettaa avain kylvystä triessä. Aloitamme klo juurisolmu ja seuraa viitteitä uudelleen. Mutta tässä tilanteessa, osuimme kuollut päättyä ennen pystymme päästä avaimen päätä. Nyt meidän täytyy jakaa joitakin uusia solmut tarvitse varata yhden uuden solmu jokaisen jäljellä kirjeellä keskeisiä. 

Tässä tapauksessa meidän täytyy vain jakaa yhden uuden solmun. Sitten meidän täytyy tehdä H-indeksi viite tähän uuteen solmuun. Jälleen kerran voimme muuttaa solmun osoittavat, että polku merkkiä mikä se edustaa avain meidän sanakirja. Katsotaanpa päättelemään asymptoottinen monimutkaisuus meidän menettelyt näitä kaksi operaatiota. 

Huomaamme, että molemmissa tapauksissa numero vaiheiden algoritmimme kesti oli verrannollinen määrä kirjaimet avainsanan. Aivan oikein. Kun haluat etsiä sanan triestä sinun tarvitsee vain kerrata kautta kirjaimet yksitellen, kunnes joko päähän sanan tai jemmassa triessä. 

Ja kun haluat lisätä avaimen arvopari osaksi trie käyttäen menettelyn keskustelimme, pahimmassa tapauksessa on sinulle jaettaessa uusi solmu jokaista kirjainta. Ja oletamme, että jako on jatkuvasti ajan toimintaa. Jos siis oletetaan, että avaimen pituus on jota rajoittaa kiinteä vakio, sekä sijoittelua ja etsiä ovat vakioita aika operaatioita triellä. 

Jos emme tee tätä oletusta, että avaimen pituus rajoittuu kiinteään vakio, niin sijoittelua ja etsiä, pahimmassa tapauksessa, on lineaarinen avaimen pituus. Huomaa, että kohteiden määrää tallennettu triessä ei vaikuta look up tai asetettiin paikoilleen. Se on vain vaikutti avaimen pituus. 

Sen sijaan lisätään merkintöjä, vaikkapa hash table taipumus tehdä tulevaisuudessa etsiä hitaammin. Vaikka tämä saattaa kuulostaa houkuttelevalta aluksi, meidän pitäisi pitää mielessä, että suotuisa asymptoottinen monimutkaisuus ei tarkoittaa, että käytännössä data rakenne on välttämättä arvostelun yläpuolella. Meidän on myös otettava huomioon, että tallentaa sana triestä tarvitsemme pahimmassa Tällöin solmujen verrannollinen pituuden sana itse. 

Yrittää taipumus käyttää paljon tilaa. Se on toisin kuin hash-taulukko, missä meidän tarvitsee vain yhden uuden solmun tallentaa joitakin keskeisiä arvopari. Nyt, jälleen teoriassa, suuri tila kulutus ei tunnu iso käsitellä, varsinkin kun nykyaikaisen tietokoneissa on gigatavua ja gigatavua muistia. Mutta näyttää siltä, ​​että meillä on vielä murehtia muistin käyttöä ja organisaatio vuoksi suorituskykyä, koska nykyiset tietokoneet käytössä järjestelyjä alle huppu nopeuttaa muistin käyttöön. 

Mutta nämä mekanismit toimivat parhaiten, kun muistin vierailuja tehdään kompakti alueita tai vyöhykkeitä. Ja solmut trien voisi sijaita missä tahansa, että kasaan. Mutta nämä ovat kompromisseja että meidän on pohdittava. 

Muista, että valitessaan tiedot rakenne tiettyjä tehtäviä varten, me pitäisi ajatella siitä, millaisia toiminnan tietorakenne on tukea ja kuinka paljon suorituskykyä kunkin tällaisen toiminnot asioita meille. Nämä toiminnot voivat jopa ulottua vain perus ilme ja paikoilleen. Oletetaan halusimme toteuttaa eräänlainen Auto-kaikki toiminnot, paljon kuten Google-hakukone tekee. Eli palauttaa kaikki avaimet ja mahdollisesti arvot, jotka on annettu etuliite. 

Triestä on ainutlaatuisen käyttökelpoinen tähän operaatioon. Se on yksinkertaista iteroitava triestä kunkin merkin etuliite. Aivan kuten etsiä toimintaa, voisimme seurata viitteitä merkki kerrallaan. Sitten, kun tulemme lopussa etuliite, voisimme kerrata läpi jäljellä oleva osa datarakenteen koska kaikki avaimet yli Tässä vaiheessa on etuliite. 

Se on myös helppo saada tietoja aakkosjärjestyksessä vuodesta osia lasten array ovat aakkosjärjestyksessä. Joten toivottavasti sinun harkita antaminen yrittää yrittää. Olen Kevin Schmid, ja tämä on CS50. 

Ah, tämä on alku lasku. Olen pahoillani. Anteeksi. Anteeksi. Anteeksi. 

Lakko neljä. Minä häivyn. Anteeksi. Anteeksi. Anteeksi. Sorry tehdä henkilö, joka on muokata tätä hulluksi. 

Anteeksi. Anteeksi. Anteeksi. Anteeksi. 

SPEAKER 1: Hyvin tehty. Se oli todella hyvin tehty.