[Musiikkia] DOUG Lloyd: Eli olemme inching lähemmäksi ja lähempänä että pyhä Graal tiedot rakenteet, yksi voimme lisätä osaksi, poistaa, ja etsiä jatkuvassa aikaa. Oikea. Se tavallaan maalia. Haluamme pystyä tekemään asiat hyvin, hyvin nopeasti. 

Onko löysimme sen täällä, kun puhumme yrittää? No, katsotaanpa katsomaan. Joten olemme nähneet useita eri tietorakenteiden jotka käsittelevät kartoitus ns avainarvopareja, kartoitus joitakin osa tiedoista joihinkin muihin osa tiedoista jotta tiedämme mistä löytää tiedot rakenteessa. 

Joten array, esimerkiksi, avain on osa indeksi tai joukko sijainti 0 tai array 1 ja niin edelleen. Ja arvo on tiedot että on kyseisessä paikassa. Niin mitä on tallennettu array 0? Mitä tallennetaan array 1 vs. vain 0 ja 1, mikä olisi avaimet. 

Jossa tiiviste on tavallaan saman ajatuksen. Jossa tiiviste, meillä on tämä hash toiminto, joka luo hash koodeja. Joten avain on hash tietojen. Ja arvo, erityisesti puhuimme ketjuttamalla in video hash taulukoita, on että linkitetty lista tietojen että tiivistyy että hashcode. Oikea. Entä toinen lähestymistapa tämä menetelmä, vaikka? Entä menetelmä, jossa avain on taatusti ainutlaatuinen, toisin tiiviste, jossa voisimme päätyä kaksi kappaletta tietojen jolla on sama hashcode. Ja meidän on käsiteltävä että joko hyvää tai enemmän edullisesti ketjuttamalla korjata tämä ongelma. 

Joten nyt voimme taata että avain on ainutlaatuinen. Ja mitä jos meidän arvo oli vain jotain yhtä helppoa kuten oikean ja väärän, joka kertoo meille, tai ei, että tieto olemassa rakenne? Boolen voisi olla niinkin yksinkertainen kuin hieman. Realistisesti se on luultavasti tavu todennäköisemmin kuin vähän. Mutta se on paljon pienempi kuin tallentamiseen ehkä 50-merkkijonon, esimerkiksi. 

Joten yrittää, samanlainen hash taulukot, jotka yhdistävät taulukot ja linkitetty lista, yrittää yhdistää taulukot, rakenteet, ja osoittimet yhdessä tietojen tallentaminen mielenkiintoinen tavalla, joka on melko erilainen mitä olemme nähneet tähän mennessä. Nyt käytämme tietojen tiekartta navigoida tietojen rakenne. Ja jos me voimme seurata tiekartan, jos voimme seurata tietoja alusta loppuun, käymme onko että tiedot olemassa trie. 

Ja jos emme voi seurata karttaa alkaen eli lopettaa ollenkaan, tietoja ei voi olla olemassa. Jälleen, avaimet tässä on taatusti ainutlaatuinen. Ja niin toisin hajautustaulun, emme koskaan on käsiteltävä törmäyksiä täällä. Eikä kaksi kappaletta tietojen on täsmälleen sama tiekartan ellei tämä tieto on sama. 

Jos lisäämme John, sitten etsimme John. Se on kaksi samanlaista kappaletta tiedot, oikea, me etsimme kautta. Mutta muuten kaikki kaksi kappaletta tietoa taatusti on ainutlaatuinen etenemissuunnitelmat tällä tietorakennetta. Ja aiomme katsomaan visuaalinen tästä vain hetken. 

Teemme tämän yrittämällä Luo uusi tietorakenne, kartoitus seuraavat keskeiset arvoparit. Tässä tapauksessa emme aio käyttää jotain niin yksinkertaista kuin Boolen. Me itse asiassa tallentaa merkkijonon. Ja että merkkijono on menossa olla nimi yliopisto. 

Ja avain tulee olemaan vuosi kun että yliopisto perustettiin. Kaikki vuotta yliopistoille tulevat olemaan neljä numeroa. Ja niin me käyttää näitä neljä numeroa selata näitä tietoja rakenteen. Ja näemme, jälleen, miten teemme sen vain toinen. 

Lopussa polun, näemme nimi Yliopiston joka vastaa avaimeen, nämä neljä numeroa. Perusajatuksena trie on meillä keskeinen reitti. Joten ajattele sitä kuin puu. Ja tämä on samanlainen oikeinkirjoitus ja käsite puuhun. Yleensä kun ajattelemme Puut todellisessa maailmassa, heillä juuri, joka on vuonna maahan ja ne kasvavat ylöspäin ja he ovat oksat ja heillä on lehtiä. Ja pohjimmiltaan ajatus trie on täsmälleen sama, paitsi että juuri on ankkuroitu jossain taivaalla. Ja lehdet ovat alareunassa. 

Joten se on tavallaan kuin ottaa puu ja vain kääntämällä se ylösalaisin. Mutta on vielä oksat. Ja ne olisi meidän polkuja, ne on meidän yhteydet juuresta lehtiä. Tässä tapauksessa nämä polkuja, ne oksat leimataan numeroa, jotka kertovat meille mihin suuntaan mennä, missä olemme. 

Jos näemme 0, menemme tämän haara, jos näemme 1, menemme tämän haara, ja niin ja niin edelleen. No, mitä tämä tarkoittaa? No, se tarkoittaa, että jokaisessa liitoskohtaan ja jokainen solmu keski ja jokainen haara, on 10 mahdollista paikkoja, että voimme mennä. Joten on 10 osoittimia alkaen kaikissa paikoissa. 

Ja tämä on, jos yrittää saada hieman uhkaava joku kuka ei ole paljon kokemus tietotekniikassa ennen. Mutta yrittää ovat oikeastaan ​​aika mahtava. Ja jos sinulla on mahdollisuus työskennellä heidän kanssaan ja olet valmis kaivaa sisään ja kokeilla niitä, he oikeastaan ​​aika mielenkiintoinen tietorakenteita työskennellä. Jos haluamme lisätä elementin osaksi trie, kaikki meidän täytyy tehdä on rakentaa oikea polku juuresta lehtiä. Tässä mitä jokainen askel pitkin Muuten voisi näyttää. Aiomme määritellä uusia tietoja rakenne uusi solmu nimeltään trie. 

Ja sisältä että tiedot rakenne on kaksi kappaletta. Aiomme säilyttää nimi yliopiston. Ja aiomme säilyttää joukko osoittimia muihin solmuihin samantyyppisiä. Joten, jälleen, tämä on tällaista on käsite kaikkialla olemme, me 10 mahdollista paikkoja voimme mennä. Jos näemme 0, menemme alas tämä osa. Jos näemme 1, tämä haara, ja niin edelleen ja niin edelleen ja niin edelleen. Jos sanomme 9, menemme alas tämä osa. Joten jokaisessa liitoskohtaan, voimme mennä 10 mahdollista paikkaa. Joten jokainen solmu on sisällettävä 10 osoittimia muihin solmuihin, 10 muut solmut. 

Ja tiedot me tallentamiseen on vain yliopiston nimi. Joten rakentaa trie. Katsotaanpa lisätä pari kohteita meidän trie. Joten huipulla, tämä on meidän root solmu. Tämä on luultavasti olemaan jotain aiot globaalisti julistaa. Ja olet menossa globaalisti säilyttää osoitin tähän solmuun aina. 

Aiot sanoa, juuri vastaa, ja olet menossa malloc itse trie solmu. Ja olet koskaan koskettaa juuri uudelleen. Joka kerta haluat aloittaa navigoinnin kautta, asetat toinen osoitin sama juuri, kuten trav, joka on esimerkki I käyttää monet minun videoita täällä pinot ja jonot ja linkit ja niin edelleen. 

Voit asettaa toinen osoitin kehotti trav varten kulkea. Ja käytät Trav navigoida kautta tietorakennetta. Joten miten tämä voisi näyttää. Joten nyt, mitä ei solmu näyttää? No, aivan kuten tiedot rakenne ilmoitus ilmoitettu, meillä on merkkijono, joka tässä tapauksessa on tyhjä. Täällä ei ole mitään. 

Ja joukko 10 osoittimia. Ja juuri nyt, me vain on 1 solmu tässä trien. Ei mitään muuta se. Joten kaikki 10 niistä viitteitä kohta null. Sitähän punaisella. 

Katsotaanpa lisätä merkkijono Harvardin. Katsotaanpa lisätä yliopistossa Harvardin tähän trie, joka perustettiin vuonna 1636. Haluamme käyttää avain, 1636, kertoa meille, missä olemme menossa tallentaa Harvardin trien. Nyt, miten voisi me teemme? 

Se saattaa näyttää tältä. Aloitamme juureen. Ja meillä on nämä 10 paikkaa voimme mennä. Juuri on aivan kuten mikä tahansa toisen solmun trie. On 10 paikkaa voimme mennä tästä. 

Minne me luultavasti halua mennä, jos avain on 1636? On oikeastaan ​​kaksi vaihtoehtoa. Oikea. Voimme rakentaa avain oikealta vasemmalle ja aloittaa 6. Tai voisimme rakentaa avain vasemmalta oikealle ja aloittaa 1. 

Se on luultavasti enemmän intuitiivinen ihmisenä ymmärtää me vain mennä vasemmalta oikealle. Joten jos haluan lisätä Harvardin tähän trie, Luultavasti halua aloittaa aloittamalla juureen, katsot minun 10 vaihtoehtoja edessäni, ja sanoi Haluan mennä alas 1 polku. OK. 

Nyt 1 polku on tällä hetkellä tyhjä. Joten jos haluan jatkaa tätä tietä lisätä tämä seikka trie, Minun täytyy malloc uusi solmu, on 1 kohta siellä, ja sitten olen hyvä mennä. 

Olen siis periaatteessa olen at kohta jossa Seison juureen puun tai trie ja on 10 oksat. Mutta jokainen haara on portti sen edessä. Oikea. Koska ei ole mitään muuta siellä. Ei turvallinen kulku. Tämä tarkoittaa, että ei ole mitään alas mitään näistä oksat. Jos haluan alkaa rakentaa jotain, haluan poistaa portille. Haluan poistaa portille edessä numero 1. Ja haluan kävellä että. Ja haluan rakentaa toinen paikka minun mennä. 

Ja se, mitä olen tehnyt täällä. Joten 1 ei enää viittaa null. Olen sanonut se on turvallista mennä tänne nyt. Rakensin toisen solmun. Ja kun saan että solmuun, minä on toinen päätös. Minne olen menossa mennä tästä? 

No, olen jo laskeneet 1. Joten nyt luultavasti halua mennä alas 6. Oikea. Jälleen Olen 10 paikkakunnalla voin valita. Joten nyt mennä alas numero 6. Joten en poista portti edessä numero 6. Ja kävelen siellä. Ja minä rakentaa toisen solmun. Ja olen saavuttanut toisen liitoskohtaan. 

Jälleen Olen 10 valintoja minne voin mennä. Olen siirtynyt 1-6. Joten nyt luultavasti halua mennä 3. 3, missään muualla voin mennä. Olen siis selkeä tapa ja rakentaa itselleni uutta tilaa. Ja sitten 3, mistä haluan mennä? Haluan mennä alas 6. 

Ja taas jouduin selkeä tapa tehdä se. Joten nyt olen käyttänyt avain lisätä luoda solmut ja alkaa rakentaa tätä trie. Olen alkanut juuresta. Olen laskenut 1636. Ja nyt olen alareunassa siellä että solmu. Ja saatat pystyä nähdä sen näytössä. 

Se on korostettu keltaisella. Siellä minä nyt olen. Avaimeni tehdään. Olen loppuun kaikissa asennoissa minun avain. Joten en voi mennä pidemmälle. Joten tässä vaiheessa, en todella tarvitsee vain sanoa, OK. Se on ikään kuin etsivät alas maahan, jos olet envisioning itsesi tällainen polku eri yhteydet. Eräänlainen katselee ja tavallaan spray maalaus Harvardin maahan. Se on nimi tämän. Tiedä se mitä tässä paikassa. Jos me alkavat juuri ja mennään alas 1 ja sitten 6 ja sitten 3 ja sitten 6, missä olemme? No jos katsomme alas ja näemme Harvard, sitten me tiedämme, että Harvardin oli perustettiin vuonna 1636 sen mukaan, kuinka me täytäntöönpanossa tietorakennetta. Joten se oli toivottavasti yksinkertaista. Aiomme tehdä kaksi lisäyksiä. Ja toivottavasti se tulee auttaa katso tämä tapahtuu kahdesti. 

Nyt, aseta toisen yliopiston. Katsotaanpa lisätä Yale tähän trie. Yale perustettiin vuonna 1701. Niin me alkavat root, kuten aina. Ja asetamme läpikulun osoitin. Aiomme käyttää tätä liikkua. Ensimmäinen asia haluamme tehdä, on mennä alas 1 polku. Se on ensimmäinen merkki tärkeimmistä. Onneksi kuitenkin, emme tarvitse tehdä mitään työtä tällä kertaa. 1 polku on jo selvitetty. Poistin sen aiemmin, kun oli lisäämällä Harvardin klo 1636. Joten en voi turvallisesti liikkua alas 1 ja vain mennä sinne. Jos voi liikkua alaspäin 1. 

Nyt kuitenkin haluan mennä 7. Olen avannut tien 6. Tiedän, että voin turvallisesti jatka alas 6 polku. Mutta minun täytyy edetä 7 tiellä. Joten mitä minun pitää tehdä? No, aivan kuten ennen, minun pitää vain tyhjentää portille, saada pois tieltä, ja rakentaa uusi solmun 7 polku. Juuri näin. 

Joten nyt olen siirtynyt 1 ja sitten 7. Ja nyt huomaa, olen tavallaan on tästä uudesta subbranch. Oikea. Kaikki muu 16 on, en välitä. En tee 16 mitään. Teen 17 juttuja. 

Joten nyt alkaen 17, minun täytyy eräänlainen innovaatio täällä. Seuraava numero avaimeni on 0. En selvästikään saa mistään. Olen juuri rakennettu tämän solmun. Tiedän siis, ei ole polut eteenpäin täältä. Joten minun täytyy tehdä sellaisen itse. 

Joten en malloc uusi solmu ja on 0 kohta siellä. Ja sitten vielä kerran, minä malloc uusi solmu ja on yksi piste siellä. Jälleen olen loppuun avaimeni, 1701. Joten katson alas ja minä spray maalata Yale. Se on nimi tämän solmun. 

Ja nyt jos joskus täytyy nähdä, jos Yale on tässä trien, aloitan juuresta, Menen alas 1701, ja katsoa alas. Ja jos näen Yale spray maalattu kiinni maahan, sitten Tiedän Yale olemassa tässä trie. Tehdään yksi. Katsotaanpa lisätä Dartmouth tähän trie, joka perustettiin vuonna 1769. 

Aloita juureen uudelleen. Ensimmäinen numero minun avain on 1. Voin turvallisesti siirtää sille tielle. Joka on jo olemassa. Seuraava numero minun avain on 7. Voin turvallisesti siirtää sille tielle. Se on olemassa myös. 

Seuraava on 6. Sieltä, mistä minä tällä hetkellä olen keltainen tuossa keskellä solmu, 6 on lukittu pois. Jos haluan mennä sille tielle, Minun täytyy rakentaa sen itse. Niin minä malloc uusi solmu ja on 6 kohta siellä. Ja sitten taas, olen paahtava uusia polkuja täällä. 

Joten en malloc uusi solmu niin että että node-- polkumääräinformaation 9-- ja sitten nyt jos matkustan 1769, ja odotan alas. Ei ole mitään tällä hetkellä spray maalattu siellä. Osaan kirjoittaa Dartmouth. Ja olen asetettu Dartmouth osaksi trie. 

Niin, että lisäämällä asiat oikeisiin trie. Nyt haluamme etsiä asioita. Miten etsiä asioita trie? No, se on melko sama ajatus. Nyt vain käyttää numeroa avaimen nähdä, jos voimme navigoida juuresta missä haluamme mennä trie. 

Jos me osuma umpikujaan missään vaiheessa, sitten me tiedämme, että tämä osa ei ole olemassa tai muuta, joka polku olisi on jo selvitetty. Jos teemme sen aina Lopulta kaikki meidän täytyy tehdä on halveksua ja katso jos se on elementti etsimme. Jos se on, menestys. Jos se ei ole, epäonnistua. 

Joten etsi Harvardin tässä trie. Aloitamme juureen. Ja taas me aiomme luoda läpikäynti osoitin teemme liikkuu meille. Juurineen tiedämme, että Ensinnäkin meidän täytyy mennä on 1, voimme tehdä sen? Kyllä me voimme. Jos turvallisesti olemassa. Voimme mennä sinne. 

Nyt, seuraava paikka meidän täytyy mennä on 6. Onko 6 polku olemassa täältä? Joo, se tekee. Voimme mennä alas 6 polku. Ja päädymme täällä. 

Voimmeko mennä alas 3 polku täällä? No, kuten on käynyt ilmi, kyllä, että on olemassa myös. Ja voimme päästä 6 polku täällä? Kyllä me voimme. 

Emme ole aivan vastattu kysymys vielä. Vielä yksi vaihe, joka on nyt meidän on tarkasteltava alas ja onko se actually-- jos etsimme Harvard, että mitä löydämme, kun olemme kata avain? Esimerkissä käytämme täällä, vuodet ovat aina neljä numeroa. Mutta käytössä voi olla esimerkiksi silloin, tallennat sanakirjan sanoja. 

Ja niin sen sijaan, että 10 osoittimia minun paikka, saatat olla 26. Yksi kutakin kirjaimen. Ja joitakin sanoja kuten lepakko, joka on osajoukko erän, esimerkiksi. Ja joten vaikka saat lopussa näppäintä ja näytät alas, et ehkä nähdä, mitä etsit. 

Joten sinulla on aina kulkea koko polku ja sitten jos olisit onnistuneesti pystynyt kulkemaan koko polkua, katso alas ja tee yksi lopullisen vahvistuksen. Sitäkö etsin? No, katson alas käynnistyksen jälkeen huipulla ja menee 1636. Odotan alas. Näen Harvard. Joten, kyllä, onnistuin. Mitä jos, mitä etsin ei ole trien, vaikka. Mitä jos Etsin Princeton, joka on perustettu vuonna 1746. Ja niin 1746 tulee minun avain selata trie. No, aloitan juuresta. Ja ensimmäinen paikka haluan että menee alas 1 polku. Voiko sen tehdä? Kyllä voin. 

Voinko mennä alas 7 polku sieltä? Joo, voin. Joka on olemassa myös. Mutta voin mennä alas 4 polku täällä? Se on kuin kysyisi kysymyksen, voi Olen edetä alas että pienellä aukiolla että olen korostettu keltaisella? Siellä ei ole mitään. Oikea. 

Ei ole tie eteenpäin alas 4 polku. Jos Princeton oli tässä trien, että 4 olisi raivattu meille jo. Ja niin tässä vaiheessa olemme päätynyt umpikujaan. Emme voi mennä pidemmälle. Ja jotta voimme sanoa lopullisesti, ei. Princeton ei ole tässä trie. 

Mitä tämä kaikki tarkoittaa? Oikea. Siellä on paljon täällä. On viitteitä koko paikka. Ja kuten näette vain kaaviosta, siellä on paljon solmuja, että ovat sellaisia ​​lentelee. Mutta huomaa aina halusimme onko jotain oli trien, meillä oli vain tehdä 4 liikkuu. 

Joka kerta halusimme aseta jotain trien, meidän on tehtävä 4 liikkuu, mahdollisesti mallocing joitakin juttuja matkan varrella. Mutta kuten näimme kun lisätään Dartmouth osaksi trie, joskus jotkut polku saattaa olla jo raivattu meille. Ja niin meidän trie saa isompi ja isompi, meillä on tehdä vähemmän työtä joka kerta lisätä uusia asioita koska olemme jo rakennettu paljon väli- oksat matkan varrella. Jos me vain koskaan tarvitse katsoa 4 asioita, 4 on vain vakio. Me todella on sellainen lähestyy vakio kerran asennus ja jatkuva ajan haku. Kompromissi, tietenkin on, että Tämän trie, kuten voitte luultavasti kertoa, on valtava. Jokainen näistä solmuista vie paljon tilaa. 

Mutta se on kompromissi. Jos haluamme todella nopeasti lisäys, todella nopea poisto, ja todella nopea lookup, meidän on on paljon tietoa lentelee. Meidän on varattu paljon tilaa ja muisti, että tietojen rakenne olla olemassa. 

Ja niin se on kompromissi. Mutta se Taisimme ehkä löytänyt sen. Olisimme havainneet, että pyhä Graal tietorakenteiden kanssa nopea lisäys, poistetaan, ja haku. Ja ehkä tämä on asianmukaiset tiedot rakenne käyttää mitä tahansa tietoa yritämme myymälä. Olen Doug Lloyd, tämä on CS50.