[Zenelejátszási] DOUG LLOYD: Szóval mi már araszolnak közelebb és közelebb a szent grál adatok struktúrák, az egyik, hogy mi lehet beszúrni be, törölni, és felnéz konstans idõ alatt. Jobb. Ez a fajta a cél. Azt akarjuk, hogy képes megtenni dolgok nagyon, nagyon gyorsan. 

Már megtaláltuk itt, amikor beszélünk megpróbálja? Nos, vessünk egy pillantást. Így már látott több adatstruktúrát hogy kezelni a feltérképezése úgynevezett kulcsértékpárok, feltérképezése néhány adat hogy néhány más adatot így tudjuk, hogy hol találja információ a szerkezetben. 

Tehát tömb, például a kulcs az elem indexe vagy tömb helyen 0 vagy tömb 1, és így tovább. És az értéket az adatok hogy a megadott helyen található. Tehát mi a array 0? Mi a array 1 szemben mindössze 0 és 1, ami a kulcsokat. 

A hash tábla, hogy ez fajta ugyanezt a gondolatot. A hash tábla, itt van ez a hash funkciót, amely létrehozza hash kódok. Tehát a kulcs a hash kódot az adatok. És az értéket, különösen beszélgettünk láncolással A videó hash táblák, az, hogy a kapcsolt adatok listája hogy hash e hashcode. Jobb. Mi a helyzet más megközelítést ez a módszer, bár? Mi a helyzet a módszer, ahol a kulcs garantáltan egyedi, ellentétben a hash tábla, ahol sikerült végén két adat amelyek azonos hashcode. És akkor azt kell kezelni hogy akár tapintás vagy több lehetőleg láncolt kijavítani a problémát. 

Szóval most tudjuk garantálni hogy mi a legfontosabb egyedi lesz. És mi van, ha a mi érték volt csak valami olyan egyszerű, igaz és hamis, hogy azt mondja, hogy vagy sem, hogy a darab információk létezik a szerkezet? Egy logikai lehet olyan egyszerű, mint egy kicsit. Reálisan ez talán egy byte valószínűbb, mint egy kicsit. De ez sokkal kisebb, mint tárolására talán egy 50-karakterlánc, például. 

Így próbál, hasonló hash táblák, amelyek ötvözik a tömbök és láncolt lista, próbálkozás kombinálni tömbök, struktúrák, és a mutatók együtt tárolni az adatokat Érdekes módon, hogy az eléggé különbözik az bármi, amit eddig láttunk. Most használd az adatokat egy ütemtervet navigálni az adatok szerkezetét. És ha tudjuk követni Az ütemterv, ha tudjuk kövesse az adatokat elejétől a végéig, akkor tudom, hogy az adatokat létezik a Trie. 

És ha nem tudjuk követni a térképen re jelenti, hogy vessen véget minden, az adatok nem léteznek. Ismét a kulcsok itt vannak garantáltan egyedi. És annyira nem egy hash tábla, soha nem fogjuk kell foglalkozni ütközések itt. És nem két adat pontosan ugyanazt a menetrendet kivéve, ha ezek az adatok azonosak. 

Ha betesszük John, majd keresünk John. Ez két egyforma darab adatok, igaz, mi keresünk keresztül. De egyébként, bármilyen két darab adat Garantált, hogy egyedülálló menetrendek ezen keresztül adatszerkezet. És megyünk megnézzük vizuális ennek csak egy pillanatra. 

Majd ezt azzal, hogy megpróbálja hozzon létre egy új adatszerkezetet, feltérképezése a következő kulcsfontosságú érték párokat. Ebben az esetben nem fogunk használni valami olyan egyszerű, mint egy logikai. Igazából tárolja a húr. És ez a karakterlánc fog legyen a neve egy egyetem. 

És a legfontosabb lesz az év amikor az egyetemi-ben alakult. Minden évben az egyetemek lesznek négy számjegy. És így fogjuk használni a négy számjegyek eligazodni az adatok szerkezetét. És majd meglátjuk, megint, hogyan teszünk, hogy egy pillanat. 

Végén az út, fogjuk látni a nevét Az egyetem, amely megfelel a kulcshoz, a négy számjegy. Az alapgondolata egy Trie az, hogy van egy központi útvonalat. Így gondolok rá, mint egy fa. És ez hasonlóképpen helyesírási és a koncepció, hogy egy fa. Általában, ha belegondolunk fák a valós világban, van egy gyökér ez a talaj és nőnek felfelé és ágak és nekik van a levelek. És alapvetően azt az elképzelést, egy Trie pontosan ugyanaz, kivéve, hogy a root egybehangzik Valahol az égen. És a levelek alján. 

Szóval ez olyan, mint egy fa figyelembe és csak essek fejjel lefelé. De még mindig vannak ágak. És azok lennének a mi utak, azok lesznek a kapcsolatok a gyökér a levelek. Ebben az esetben, az említett utak, azok az ágazatok, címkével vannak számjegy ez nekünk merre kell menni, ahol vagyunk. 

Ha látunk egy 0, lemegyünk az ág, ha látunk egy 1, lemegyünk az ág, és így és így tovább. Nos, mit jelent ez? Nos, ez azt jelenti, hogy minden csomópontjában és minden csomópont a középső és minden ág, van 10 lehetséges helyen, hogy mi lehet menni. Tehát van 10 mutató minden helyen. 

És ez az, ahol megpróbálja kaphat kicsit ijesztő, hogy valaki aki nem sok tapasztalat számítástechnika előtt. De igyekszik tényleg elég félelmetes. És ha megvan az esélye, hogy működjön együtt velük és te hajlandó ásni-ben és kísérletezni velük, ők tényleg elég érdekes adatstruktúrák dolgozni. Ha azt akarjuk, hogy helyezzen be egy elemet a Trie, csak annyit kell tennie A építeni a helyes utat a gyökér a levél. Itt van, amit minden lépése során ahogy nézhet. Fogunk meg egy új adatok szerkezetet egy új csomópont úgynevezett Trie. 

És aztán az adatok szerkezete van két darab. Megyünk tárolni Íme egy egyetem. És fogunk tárolni egy sor mutató más csomópontokhoz az azonos típusú. Szóval, megint ez az a fajta A koncepció mindenhol vagyunk, mi a 10 lehetséges helyek mehetünk. Ha látunk egy 0, megyünk le az ág. Ha látunk egy 1, ez az ág, és így tovább, és így tovább, és így tovább. Ha azt mondjuk, 9, megyünk le az ág. Tehát minden csomópontjában, mehetünk 10 lehetséges helyeket. Tehát minden csomópont tartalmaznia 10 mutató más csomópontokhoz, hogy 10 másik csomópont. 

És az adatokat mi tárolására is csak a neve az egyetem. Így építsük fel a Trie. Nézzük be egy pár A tételek a mi Trie. Tehát az egyik legfontosabb, ez a mi gyökér csomópont. Ez valószínűleg lesz valami fogsz globálisan hirdetjük. És te fogsz globálisan fenntartása egy mutató, ez a csomópont mindig. 

Meg fogsz mondani, gyökér egyenlő, és te fog malloc magát Trie csomópontot. És te soha nem fog megérinteni újra gyökeret eresszen. Minden alkalommal, amikor akar a navigáció elindítása révén, beállított egy másik mutatót egyenlő gyökér, mint a trav, amely a példában azt Használja sok videóm itt a halmok és a sorban állás és linklisták és így tovább. 

Te meg egy másik mutatót nevű trav a bejárás. És akkor használja trav navigálni keresztül az adatszerkezet. Nézzük, hogyan nézhet ki. Tehát most, hogy mi nem egy csomópont kinézni? Nos, épp úgy, ahogy adatok szerkezete megjelölt nyilatkozatban, van egy szöveg, amely ebben az esetben üres. Nincs itt semmi. 

És egy sor 10 mutató. És most, mi csak Van 1 csomópont ebben Trie. Semmi mást benne. Tehát mind a 10 ilyen mutatók pont null. Ez az, amit a piros jelzi. 

Nézzük helyezze a húr Harvard. Helyezzük az Egyetem Harvard ebbe Trie, amely -ben alakult a 1636. Azt szeretnénk használni a kulcsot, 1636, mondja el nekünk, hol vagyunk fog tárolni Harvard a Trie. Most, hogy hogyan lehet ezt tesszük? 

Lehet, hogy valahogy így néz ki. Kezdjük a gyökér. És mi van a 10 helyekre mehetünk. A gyökér van, mint bármely másik csomópont a Trie. Jelenleg 10 helyen tudunk menni innen. 

Hogyan képzeljük érdemes menni, ha a kulcs 1636? Ott tényleg két lehetősége van. Jobb. Mi lehet építeni a kulcsot jobbról balra, és kezdje 6. Vagy tudtuk építeni a kulcsot balról jobbra, és kezdődik 1. 

Ez valószínűleg több intuitív, mint egy emberi lény megérteni mi Csak megy balról jobbra. És így ha szeretné szúrni Harvard ebbe Trie, Azt érdemes kezdeni kiindulva a gyökér, néztem én 10 opciók előttem, és azt mondja: Azt akarom, hogy menjen le a 1 útját. OKÉ. 

Most, 1 ág jelenleg üres. Tehát, ha azt akarom, hogy folytassa ezen az úton beilleszteni ezt az elemet a Trie, Van malloc egy új csomópont, van 1 pont ott, és akkor én vagyok jó menni. 

Szóval én alapvetően vagyok egy pont, ahol állok a gyökér a fa vagy a Trie és van 10 ág. De minden ága van kapu előtt azt. Jobb. Mert nincs más van. Nem biztonságos áthaladását. Ez azt jelenti, hogy nincs semmi le bármely olyan ágakat. Ha azt szeretnénk, hogy kezdjék építeni valamit, azt akarom, hogy távolítsa el a kaput. Azt akarom, hogy távolítsa el a kaput előtt az 1. számú. És azt akarom, hogy sétálni, hogy. És szeretnék építeni Egy másik helyen, hogy menjek. 

És ez az, amit én csináltam itt. Tehát 1 már nem mutat null. Azt mondtam, nyugodtan menjen le itt. Építettem egy másik csomópont. És mikor jut el, hogy node, én Van egy másik döntés. Hol fogok menni innen? 

Nos, én már lement a 1. Szóval most érdemes lemenni a 6. Jobb. Ismét van 10 helyszínen tudok választani. Úgyhogy most megy le a 6. Szóval egyértelmű a kaput előtte 6-os szám. És sétálok oda. És építek egy másik csomópont. És elértem egy másik kapcsolódási pont. 

Ismét én 10 választási hol tudok menni. Már költözött 1-6. Szóval most érdemes menni 3. 3, nincs hová megyek. Szóval van, hogy egyértelmű az utat és építeni magamnak egy új helyet. És akkor a 3, hol akarok menni? Azt akarom, hogy menjen le 6. 

És újra meg kellett egyértelmű az utat megtenni. Szóval most én is használtam a kulcsot, hogy helyezze létre csomópontok és elkezdi építeni ezt a Trie. Elkezdtem a gyökere. Már lement 1636. És most én vagyok az alján ott azon a csomóponton. És akkor lehet, hogy látni a képernyőn. 

Ez sárgával. Ez az, ahol én vagyok jelenleg. Saját kulcs történik. Én már kimerítette minden helyzetben a kulcsot. Így nem tudok tovább menni. Tehát ezen a ponton, minden, amit Tényleg kell tennie, hogy azt mondják, OK. Ez olyan, mint keres le a földre, ha derített fényt egyedül ez a fajta utat a különböző kapcsolatokat. Valahogy úgy nézett le, és egyfajta festékszóró Harvard a földön. Ez a neve ennek. Tudd meg, hogy az, ami ezen a helyen. Ha elkezdjük a gyökere, és lemegyünk 1, majd 6, majd 3, majd 6, hol vagyunk? Nos, ha megnézzük le és látjuk, Harvard, majd Tudjuk, hogy a Harvard volt alapította 1636-ban, annak alapján, ahogy mi végrehajtási adatstruktúrát. Szóval ez volt remélhetőleg egyértelmű. Fogunk csinálni két betoldások. És remélhetőleg ez segíteni fog, hogy lásd ezt el még kétszer. 

Most pedig nézzük helyezzen be egy másik egyetemen. Nézzük helyezze Yale ebbe Trie. Yale-ben alakult 1701-ben. Tehát kezdjük meg a gyökér, mint mi mindig. És mi meg bejárás mutatót. Fogunk használni, hogy mozoghat. Az első dolog, amit szeretnénk tennie, hogy menjen le az 1 útját. Ez az első számjegy a mi gombot. Szerencsére azonban, mi nem van, hogy csináljanak valamit ebben az időben. Az 1 útját már törölték. Én tisztázta korábban, amikor volt behelyezése Harvard meg 1636. Szóval lehet biztonságosan mozog csökkentés 1, és csak ott. Ha lefelé mozdul az 1. 

Most azonban szeretnék menni 7. Azt az utat a 6. Tudom, hogy nyugodtan folytassa le a 6 utat. De azt kell, hogy járjon el a 7 útját. Szóval mit kell tennem? Nos, csak úgy, mint korábban, csak kell törölje a kapu, kap az útból, és épít egy új csomópont a 7. utat. Mint ez. 

Szóval most már átkerült 1, majd 7. És most észre, én vagyok a fajta Az ezen az új alcsoport. Jobb. Minden más 16 a, Nem érdekel. Nem csinálok semmit 16. Csinálok 17 cucc. 

Tehát most 17, azt kell fajta lángok új pályák itt. A következő számjegy a kulcsot 0. Én nyilvánvalóan nem kap sehol. Csak építette ezt a csomópontot. Szóval tudom, hogy nincs utak előre innen. Tehát azt kell, hogy egy magam. 

Szóval malloc egy új csomópont és 0 pont ott. És akkor még egyszer, én egy malloc új csomópont és egy ponton van. Megint kimerítette a kulcsom, 1701. Így nézek le, és én festék spray Yale. Ez a neve ennek a csomópontot. 

És így most ha én valaha is kell látni, ha Yale Ebben Trie, elkezdem a gyökér, Lemegyek 1701, és nézz le. És ha látom Yale permetező festett a földre, majd Tudom Yale létezik ezen Trie. Csináljunk még egy. Nézzük helyezze Dartmouth ebbe Trie-ben alapított 1769-ben. 

Kezdjük a gyökér újra. Az első számjegy az én kulcs 1. Én nyugodtan mozog ezen az úton. Amely már létezik. A következő számjegy az én kulcs 7. Én nyugodtan mozog ezen az úton. Ez létezik. 

A következő 6. Innen, ahol jelenleg vagyok sárga ott, abban a középső csomópont, 6 jelenleg zárolva van kapcsolva. Ha akarok menni ezen az úton, Meg kell építeni magam. Úgyhogy malloc egy új csomópont és 6 pont ott. És akkor megint én vagyok ragyogó új pályák itt. 

Szóval malloc egy új csomópont, hogy honnan hogy node-- Menetvonalszám 9-- majd most Ha utazom 1769, és nézek le. Nincs semmi jelenleg spray-festett ott. Tudok Dartmouth. És én már be Dartmouth a Trie. 

Szóval ez behelyezése dolgokat a Trie. Most szeretnénk keresni dolgokat. Hogyan keresni dolgokat a Trie? Nos, ez nagyjából ugyanaz a gondolat. Most már csak használja a számjegyek a kulcs hogy hátha tudunk navigálni a gyökér hogy hová akarunk menni a Trie. 

Ha zsákutcába bármely pontján, majd tudjuk, hogy ez az elem nem létezik vagy pedig, hogy pályától már kitisztult. Ha mi készítjük egészen A végén, csak annyit kell tennie az lenézni és látni, ha ez Az elem keresünk. Ha igen, akkor a siker. Ha nem, nem. 

Úgyhogy keresni Harvard ebben Trie. Kezdjük a gyökér. És megint megyünk hozzon létre egy bejárás mutatót hogy nem a mi mozog a számunkra. A gyökér tudjuk, hogy a Először is meg kell, hogy menjen az 1, tehetünk, hogy? Igen. Ha biztonságosan létezik. Mi lehet ott. 

Most, a következő helyen kell mennünk 6. Vajon a 6 utat léteznek innen? Ja, igen. Mi lehet lemenni a 6 utat. És mi kerül ide. 

Mehetünk le a 3 utat innen? Nos, mint kiderült, igen, ez létezik is. És tudjuk, hogy a 6 utat innen? Igen. 

Már nem is válaszol A kérdés még. Van még egy további lépés, amely most meg kell nézni le, és hátha ez actually-- ha keresünk Harvard, hogy mit találunk miután kimeríti a kulcs? A példában mi használ itt, Az év mindig négy számjegy. De lehet, hogy példáján, ahol akkor tárolja a szótárban a szavak. 

És így ahelyett, hogy 10 mutató hol vagyok, lehet, hogy 26. Egy minden egyes betűt az ábécé. És van néhány szó, mint a denevér, amely egy részhalmaza szakaszos, például. És így még ha nem kap a a kulcs vége, és úgy nézel le, lehet, hogy nem látni, mi keres. 

Így mindig van, hogy áthalad A teljes elérési utat, majd ha sikeresen tudja bejárására a teljes elérési utat, lenéznek, és tegye végleges megerősítése. Ez az, amit én keresek? Nos, lenézek megkezdése után a tetején, és megy 1636. Nézek le. Látom Harvard. Szóval, igen, sikerült. Mi van, ha az, amit keresek a nem a Trie, mégis. Mi van, ha én keresek Princeton, ben alapított 1746-ban. És így 1746 lesz a kulcsom eligazodni a Trie. Nos, elkezdem a gyökere. És az első helyen akarok hogy lemegy a 1 útját. Tudok csinálni? Igen tudok. 

Mehetek le a 7 utat onnan? Igen, én is. Hogy létezik is. De tudok lemenni a 4 utat innen? Ez olyan, mintha azt kérdezi a kérdést, lehet Én jár le, hogy a kis négyzet hogy már sárga színnel? Nincs ott semmi. Jobb. 

Kizárt, hogy előre le 4 útját. Ha Princeton volt ebben Trie, hogy 4 azt nem törlik a számunkra már. És így ezen a ponton elértük zsákutca. Nem tudunk tovább menni. És így azt mondhatjuk, véglegesen, nem. Princeton nem létezik ebben a Trie. 

Szóval mit is jelent ez? Jobb. Van egy csomó folyik itt. Van mutatókat az egész hely. És, mint látod Csak a rajz, van egy csomó csomópontok van egyfajta repülő körül. De észre minden alkalommal akartuk ellenőrizni, hogy valami volt a Trie, már csak az, hogy a 4. mozog. 

Minden alkalommal, amikor meg akartuk helyezze valamit a Trie, van, hogy a 4 mozog, esetleg mallocing néhány dolgot az út mentén. De mint láttuk, amikor be Dartmouth a Trie, néha néhány utat Lehet, hogy már kitisztult számunkra. És így, mint a mi Trie egyre nagyobb és nagyobb, már kevesebb munka minden alkalommal helyezzen be új dolgokat hiszen már épített egy csomó köztes ágak az út mentén. Ha mindig csak meg kell nézni 4 dolog, 4 egy konstans. Tényleg van ilyen közeleg konstans időt behelyezés és állandó idő keresést. A kompromisszum, természetesen, az, hogy ez Trie, ahogy talán mondani, hatalmas. Mindegyik csomópontok vesz fel egy csomó helyet. 

De ez a kompromisszum. Ha azt akarjuk, nagyon gyors beillesztés, nagyon gyors törlés, és nagyon gyors kereséssel, meg kell Van egy csomó adat repülő körül. Meg kell félretenni egy csomó hely és a memória az adott adatstruktúra létezni. 

És ez az a kompromisszum. De úgy néz ki, mint mi Lehet, hogy megtalálta. Talán azt találták, hogy szent grál adatstruktúrák gyors feltöltés, törlés, és elemzéssel. És talán ez lesz megfelelő adatok szerkezete használható bármilyen információ próbálunk boltban. Én Doug Lloyd, ez CS50.