[Speel van musiek] DOUG LLOYD: So het ons stapsgewijze nader en nader die heilige graal van data strukture, een wat ons kan voeg in, verwyder uit, en kyk op in konstante tyd. Reg. Dit is soort van die doel te bereik. Ons wil in staat wees om te doen dinge baie, baie vinnig. 

Het ons hier wanneer dit gevind ons praat oor drieë? Wel, laat ons neem 'n blik. So het ons 'n paar gesien verskillende data strukture wat hanteer die kartering van sogenaamde sleutel waarde pare kartering 'n stuk van data aan 'n ander stuk data sodat ons weet waar om te vind inligting in die struktuur. 

So vir skikking, byvoorbeeld, die sleutel is die element indeks of array plek 0 of 1 verskeidenheid en so aan. En die waarde is die data wat bestaan ​​op die plek. So, wat gestoor word in die rigting 0? Wat is gestoor in verskeidenheid 1 versus net 0 en 1, wat sou wees die sleutels. 

Met 'n hash tafel is dit soort van dieselfde idee. Met 'n hash tafel, ons het hierdie hash funksie wat hash kodes genereer. So het die sleutel is om die hash-kode van die data. En die waarde, veral Ons het gepraat oor chaining in die video op hash tabelle, is dat gekoppel lys van data dat hashes om daardie hashcode. Reg. Wat van 'n ander benadering hierdie metode, hoewel? Wat van 'n metode waar die sleutel is gewaarborg om uniek te wees, Anders as 'n hash tafel, waar ons kon eindig met twee stukke data met dieselfde hashcode. En dan het ons te make met wat deur óf indringende of meer verkieslik chaining om daardie probleem op te los. 

So nou kan ons waarborg dat ons sleutel uniek wees. En wat as ons waarde was net iets so maklik as ware en valse wat ons vertel of of daardie stukkie inligting bestaan ​​in die struktuur? A Boole kan so eenvoudig soos 'n bietjie wees. Realisties is dit waarskynlik 'n byte meer geneig as 'n bietjie. Maar dit is 'n baie kleiner as stoor miskien 'n 50-karakter string, byvoorbeeld. 

So drieë, soortgelyk aan tafels hash, wat kombineer skikkings en geskakelde lys, drieë kombineer skikkings, strukture en wenke saam om data te stoor in 'n interessante manier wat mooi anders enigiets wat ons tot dusver gesien het. Nou gebruik ons ​​die data as 'n draaiboek hierdie data struktuur navigeer. En as ons kan volg die draaiboek, as ons kan volg die data van begin tot einde, sal ons weet of dat die data bestaan ​​in die Trie. 

En as ons nie kan volg die kaart van betekenis aan die einde nie, die data kan nie bestaan ​​nie. Weereens, die sleutels hier is gewaarborg om uniek te wees. En so in teenstelling met 'hash tafel, sal ons nooit te doen het met botsings hier. En geen twee stukke data presies dieselfde draaiboek tensy daardie data is identies. 

As ons voeg John, dan Ons soek John. Dit is twee identiese stukke data, reg, ons is op soek deur. Maar andersins, enige twee stukke data is gewaarborg om unieke padkaarte het deur middel van hierdie data-struktuur. En ons gaan om 'n blik op te neem 'n visuele van hierdie in net 'n oomblik. 

Ons sal dit doen deur te probeer om skep 'n nuwe data struktuur, kartering van die volgende sleutel waarde pare. In hierdie geval, is ons nie gaan gebruik iets so eenvoudig soos 'n Boole. Ons sal eintlik die string te stoor. En dat string gaan wees die naam van 'n universiteit. 

En die sleutel gaan die jaar wees wanneer daardie universiteit gestig. Alle jaar vir universiteite gaan vier syfers. En so sal ons die vier syfers te gebruik opgevolg deur hierdie data struktuur. En ons sal sien, weer, hoe ons dit doen in net 'n sekonde. 

Aan die einde van die pad, ons sal die naam te sien van die universiteit wat ooreenstem dat die sleutel, die vier syfers. Die basiese idee agter 'n Trie is ons 'n sentrale roete. So dink oor dit soos 'n boom. En dit is soortgelyk in spelling en in die konsep om 'n boom. Algemeen wanneer ons dink oor bome in die werklike wêreld, hulle het 'n wortel wat in die grond en hulle opwaartse groei en hulle het takke en hulle het die blare. En basies die idee van 'n Trie is presies dieselfde, behalwe dat die wortel geanker iewers in die lug. En die blare is aan die onderkant. 

So dit is soort van soos die neem van 'n boom en net daarby dit onderstebo. Maar daar is nog takke. En dié sal wees om ons paaie, diegene sal wees om ons verbindings uit die wortel van die blare. In hierdie geval, die paaie, daardie takke gemerk met syfers wat ons vertel watter pad om te gaan van waar ons is. 

As ons sien 'n 0, sal ons aftrek hierdie tak, as ons sien 'n 1, sal ons aftrek hierdie tak, en so en so aan. Wel, wat beteken dit? Wel, dit beteken dat by elke kruising punt en elke node in die middel en elke loot, daar is 10 moontlike plekke wat ons kan gaan. So is daar 10 wenke uit elke plek. 

En dit is waar drieë n kan kry bietjie intimiderend vir iemand wie is nie 'n baie ervaring in rekenaarwetenskap voor. Maar drieë is regtig mooi awesome. En as jy die kans om te werk met hulle en jy bereid is om te grawe in-is en eksperimenteer met hulle, hulle is regtig baie interessant data strukture te werk. As ons wil hê om 'n element te voeg in die Trie, al wat ons nodig het om te doen is die bou van die korrekte pad uit die wortel van die blaar. Hier is wat elke stap langs die pad lyk. Ons gaan 'n nuwe data definieer struktuur vir 'n nuwe node genoem Trie. 

En binnekant van die data struktuur is daar twee stukke. Ons gaan na die winkel naam van 'n universiteit. En ons gaan om te slaan 'n verskeidenheid van wenke na ander nodes van dieselfde soort. So, weer, dit is dat die soort van die konsep van oral ons is, het ons by 10 moontlike plekke wat ons kan gaan. As ons sien 'n 0, sal ons aftrek hierdie tak. As ons sien 'n 1, die tak, en so aan en so aan en so aan. As ons sê 9, sal ons aftrek hierdie tak. So by elke kruising punt, ons kan gaan 10 moontlike plekke. So elke node het 10 wenke bevat na ander nodes, tot 10 ander nodes. 

En die data wat ons stoor is net die naam van die universiteit. So laat bou 'n Trie. Kom ons voeg 'n paar van items in ons Trie. So op die heel boonste, dit is ons wortel node. Dit is waarskynlik gaan om iets te wees jy gaan om te verklaar wêreldwyd. En jy gaan globaal handhaaf 'n verwysing na hierdie node altyd. 

Jy gaan om te sê, wortel gelyk, en jy is gaan jouself malloc Trie knoop. En jy gaan nooit om weer wortel raak. Elke keer as jy wil begin opgevolg deur, jy 'n ander wyser stel gelyk aan die wortel, soos trav, wat is die voorbeeld wat ek gebruik in baie van my video's hier op stapels en toue en 'n skakel lyste en so aan. 

Jy stel 'n ander wyser genoem trav vir traversal. En jy trav gebruik om te navigeer deur die data-struktuur. So laat ons sien hoe dit kan lyk. So nou, wat nie 'n knoop lyk? Wel, net soos ons data struktuur verklaring aangedui, ons het 'n string, wat in hierdie geval is leeg. Daar is niks hier. 

En 'n verskeidenheid van 10 wenke. En nou, ons net het 1 node in hierdie Trie. Daar is niks anders in dit. So al 10 van die wysers punt om null. Dit is wat die rooi dui. 

Kom ons plaas die string Harvard. Kom ons plaas die Universiteit van Harvard in hierdie Trie, wat is gestig in die jaar 1636. Ons wil die sleutel te gebruik, 1636, om ons te vertel waar ons gaan om te slaan Harvard in die Trie. Nou, hoe kan ons dit doen? 

Dit mag dalk iets soos hierdie. Ons begin by die wortel. En ons het hierdie 10 plekke wat ons kan gaan. Die wortel is net soos enige ander node van die Trie. Daar is 10 plekke wat ons kan gaan van hier af. 

Waar moet ons waarskynlik wil om te gaan as die sleutel is 1636? Daar is regtig twee opsies. Reg. Ons kan die sleutel van die bou regs na links en begin met 6. Of ons kan die sleutel van die bou links na regs en begin met 1. 

Dit is waarskynlik meer intuïtief as 'n mens om ons verstaan ​​sal gaan net links na regs. En so as ek wil voeg Harvard in hierdie Trie, Ek wil waarskynlik om te begin deur te begin by die wortel, op soek na my 10 opsies in die voorkant van my en sê: Ek wil om te gaan die 1 pad. OK. 

Nou, 1 pad is tans null. So as ek wil om voort te gaan neer dat die pad hierdie element voeg in die Trie, Ek het na 'n nuwe node malloc, het 1 wys daar en dan is ek goed om te gaan. 

So ek basies is op 'n punt waar ek staan aan die wortel van die boom of die Trie en daar is 10 takke. Maar elke tak het 'n hek in die voorkant van dit. Reg. Want daar is niks anders daar is. Geen veilige gang. Dit beteken dat daar niks down enige van daardie takke. As ek wil begin bou iets, ek wil die hek te verwyder. Ek wil na die hek te verwyder in die voorkant van nommer 1. En ek wil loop nie. En ek wil bou 'n ander plek vir my om te gaan. 

En dit is wat ek hier gedoen het. So 1 nie meer punte aan null. Ek het gesê dit is veilig om hier af te gaan nou. Ek gebou 'n ander knoop. En toe ek by daardie node, ek het 'n ander besluit te maak. Waar gaan ek om te gaan van hier af? 

Wel, ek het al in die 1 weg. So nou wil ek waarskynlik om af te gaan die 6. Reg. Weereens, ek het 10 plekke wat ek kan kies. So laat gaan nou af nommer 6. So ek duidelik die hek in die voorkant van nommer 6. En ek loop daar. En ek bou 'n ander knoop. En ek het 'n ander punt aansluiting bereik. 

Weereens, ek het 10 keuses want waar ek kan gaan. Ek het verskuif van 1 tot 6. So nou wil ek waarskynlik om te gaan na 3. 3, daar is nêrens ek kan gaan. So ek het die pad te vee en die bou van myself 'n nuwe ruimte. En dan van 3, waar ek wil gaan? Ek wil om te 6 gaan. 

En weer, moes ek duidelik die manier om dit te doen. So nou het ek my sleutel gebruik om te skep voeg nodes en begin om hierdie Trie bou. Ek het begin by die wortel. Ek het af 1636 weg. En nou is ek aan die onderkant daar op daardie knoop. En jy kan in staat wees om sien dit op jou skerm. 

Dit is uitgelig in geel. Dit is waar ek tans is. My sleutel gedoen word. Ek het elke posisie in my sleutel uitgeput is. So ek kan nie verder gaan. So op hierdie punt, al wat ek regtig nodig het om te doen is sê, OK. Dit is soort van soos soek af na die grond, as jy behels jouself as hierdie soort van pad met verskillende verbindings. Soort van kyk af en soort spuit verf Harvard op die grond. Dit is die naam van hierdie. Weet dit is wat by hierdie plek. As ons begin by die wortel en ons het afgekom 1 en dan 6 en dan 3 en dan 6, waar is ons? Wel, as ons kyk neer en ons sien Harvard, dan ons weet dat Harvard was gestig in 1636 op grond van die manier ons die implementering van hierdie data-struktuur. So dit was hopelik eenvoudig. Ons gaan twee invoegings te doen. En hopelik sal dit help om sien dit gedoen twee keer meer. 

Nou, laat ons voeg 'n ander universiteit. Kom ons voeg Yale in hierdie Trie. Yale is gestig in 1701. So ons sal begin by die wortel, soos ons altyd doen. En ons het 'n traversal wyser. Ons gaan om dit te gebruik om deur te beweeg. Die eerste ding wat ons wil doen is gaan in die 1 pad. Dit is die eerste syfer van ons sleutel. Gelukkig, al is, ons doen nie moet enige werk hierdie keer doen. Die 1 pad is reeds skoongemaak. Ek het voorheen toe ek skoongemaak dit is die inbring Harvard by 1636. So ek kan veilig te beweeg down 1 en net daar te gaan. As kan af beweeg die 1. 

Nou, al is, ek wil gaan na 7. Ek die weg gebaan op 6. Ek weet ek kan veilig voort in die 6 pad. Maar ek moet voortgaan op die pad 7. So, wat moet ek doen? Wel, net soos voorheen, ek moet net om die hek te verwyder, te kry uit die pad, en die bou van 'n nuwe node uit die 7 pad. Net soos hierdie. 

So nou het ek verhuis 1 en dan 7. En nou sien, ek is soort van hierdie nuwe subbranch. Reg. Alles anders uit 16 op, weet ek nie omgee. Ek is nie 16 om iets te doen. Ek doen 17 dinge. 

So, nou van 17 op, ek het om te soort van brand hier nuwe paaie. Die volgende syfer my sleutel is 0. Ek kan duidelik nie oral te kry. Ek het net het hierdie knoop. So ek weet daar is geen paaie vorentoe van hier. So ek het om self een te maak. 

So ek malloc 'n nuwe node en het 0 punt is daar. En dan nog een keer, ek het 'n malloc nuwe knoop en een punt is daar. Weereens, ek het my sleutel, 1701 uitgeput is. So ek kyk af en ek spuitverf Yale. Dit is die naam van hierdie knoop. 

En so nou as ek ooit nodig het om te kyk of Yale is in hierdie Trie, begin ek by die wortel, Ek gaan af 1701, en kyk af. En as ek sien Yale spuit geverf op die grond, dan Ek weet Yale bestaan ​​in hierdie Trie. Kom ons doen 'n meer. Kom ons voeg Dartmouth in hierdie Trie, wat is gestig in 1769. 

Begin by die wortel weer. My eerste syfer van my sleutel is 1. Ek kan veilig beweeg neer dat die pad. Wat reeds bestaan. Die volgende syfer van my sleutel is 7. Ek kan veilig beweeg neer dat die pad. Dit bestaan ​​ook. 

My volgende is 6. Van hier, waar ek tans is geel daar in daardie middel knoop, 6 is tans gesluit het. As ek wil om te gaan dat die pad, Ek het dit self te bou. So ek sal 'n nuwe node malloc en 6 punt is daar. En dan, weer, ek is brandende nuwe paaie hier. 

So ek malloc 'n nuwe node sodat uit dat node-- pad getal 9-- en dan nou As ek reis 1769, en ek kyk af. Daar is niks wat tans spuit daar geverf. Ek kan skryf Dartmouth. En ek het ingevoeg DARTMOUTH in die Trie. 

So dit is die invoeging dinge in die Trie. Nou wil ons om te soek na dinge. Hoe weet ons soek vir dinge in die Trie? Wel, dit is pretty much dieselfde idee. Nou het ons net die gebruik van die syfers van die belangrikste om te sien of ons kan navigeer van die wortel waar ons wil gaan in die Trie. 

As ons druk 'n doodloopstraat by enige punt, dan ons weet dat daardie element nie kan bestaan of anders dat die pad sou reeds skoongemaak. As ons dit al die pad na die einde, al wat ons nodig het om te doen is neersien en kyk of dit is die element wat ons soek. As dit is, sukses. As dit is nie, misluk. 

So laat soek Harvard in hierdie Trie. Ons begin by die wortel. En weer, ons gaan skep 'n traversal wyser ons beweeg vir ons doen. Uit die wortel weet ons dat die eerste plek moet ons gaan, is 1, kan ons dit doen? Ja ons kan. As veilig bestaan. Ons kan daar te gaan. 

Nou, die volgende plek wat ons nodig het om te gaan is 6. Maak die pad 6 bestaan ​​van hier af? Ja, dit doen nie. Ons kan gaan in die 6 pad. En ons eindig hier op. 

Kan ons gaan af in die pad 3 van hier af? Wel, as dit blyk, Ja, wat te bestaan. En ons kan kry op die pad 6 van hier af? Ja ons kan. 

Ons het nie heeltemal beantwoord nog die vraag. Daar is nog een stap, wat nou ons nodig het om te kyk af en sien of dit is actually-- As ons kyk na Harvard, is dat wat ons vind nadat ons die uitlaat van die sleutel? In die voorbeeld is ons hier in met, die jaar is altyd vier syfers. Maar jy kan met behulp van die voorbeeld waar jy stoor 'n woordeboek van woorde. 

En so in plaas van om 10 wenke vir my plek, kan jy 26. Een vir elke letter van die alfabet. En daar is 'n paar woorde soos bat, wat is 'n subset van joernaal, byvoorbeeld. En dus selfs as jy die einde van die sleutel en jy kyk af, jy dalk nie sien wat jy soek. 

So het jy altyd om oor te steek die hele pad en dan as jy suksesvol kan om die hele pad deurkruis, neersien en doen een finale bevestiging. Is dit wat ek soek? Wel, kyk ek af na die begin aan die bokant en gaan 1636. Ek kyk af. Ek sien Harvard. So, ja, daarin geslaag Ek. Wat gebeur as wat ek is op soek na is nie in die Trie, al is. Wat gebeur as ek is op soek na Princeton, wat is gestig in 1746. En so 1746 word my sleutel om te opgevolg deur die Trie. Wel, ek begin by die wortel. En die eerste plek wil ek om af gaan die 1 pad. Kan ek dit doen? Ja ek kan. 

Kan ek gaan af in die pad van daar 7? Ja, ek kan. Wat bestaan ​​ook. Maar ek kan gaan in die 4 pad van hier af? Dit is soos die vraag te vra, kan Ek gaan sit wat min vierkante dat ek in geel uitgelig? Daar is niks. Reg. 

Daar is geen pad vorentoe in die 4 pad. As Princeton was in hierdie Trie, wat 4 sou gewees het reeds skoongemaak vir ons. En so op hierdie punt ons het 'n doodloopstraat bereik. Ons kan nie verder gaan nie. En so kan ons sê, finaal, no. Princeton bestaan ​​nie in hierdie Trie. 

So, wat beteken dit alles? Reg. Daar is 'n baie gaan op hier. Daar is aanduidings oor die hele plek. En, soos jy kan sien net uit die diagram, daar is 'n baie nodes wat is soort van vlieg rond. Maar let elke keer as ons wou kyk of daar iets was in die Trie, ons het net 4 beweeg te maak. 

Elke keer as ons wou iets invoeg in die Trie, ons het tot 4 beweeg te maak, moontlik mallocing paar dinge langs die pad. Maar soos ons gesien het toe ons plaas DARTMOUTH in die Trie, soms 'n paar van die pad dalk reeds skoongemaak vir ons. En so ons Trie kry groter en groter, ons het minder werk elke keer te doen om nuwe dinge te voeg want ons het reeds het 'n groot deel van die intermediêre takke langs die pad. As ons net ooit om te kyk na 4 dinge, 4 is net 'n konstante. Ons is regtig soort van nader konstante tyd invoeging en konstante tyd lookup. Die nadeel, natuurlik, is dat hierdie Trie, soos jy kan waarskynlik sê, is groot. Elkeen van hierdie nodes neem 'n baie ruimte. 

Maar dit is die nadeel. As ons wil regtig vinnig inplanting, regtig vinnig te skrap, en regtig vinnig lookup, moet ons het 'n baie data vlieg rond. Ons het ter syde te stel 'n baie ruimte en geheue vir daardie data struktuur om te bestaan. 

En so dit is die nadeel. Maar dit lyk asof ons kan dit gevind. Ons kon gevind dat heilige graal van data strukture met 'n vinnige inplanting, skrap, en soek. En miskien sal dit wees 'n toepaslike data struktuur te gebruik vir enige inligting ons probeer om die winkel. Ek is Doug Lloyd, dit is cs50.