[Muziek] DOUG LLOYD: Dus we hebben tippen dichterbij en dichter die heilige graal van data structuren, die we kunnen invoegen in, verwijderen uit en kijk omhoog in constante tijd. Rechts. Dat is een soort van het doel. We willen in staat zijn om te doen dingen heel, heel snel. 

Hebben we hier toen het gevonden we praten over pogingen? Nou, laten we eens een kijkje nemen. Daarom hebben we een aantal gezien verschillende datastructuren dat omgaan met het in kaart brengen van de zogenaamde sleutelwaarde paren, in kaart brengen van een stukje data sommige andere stuk van de gegevens zodat we weten waar te vinden informatie in de structuur. 

Dus voor array, bijvoorbeeld de sleutel is het element index of matrix location 0 of matrix 1 enzovoort. En de waarde van de data dat bestaat op die locatie. Dus wat is opgeslagen in serie 0? Wat wordt opgeslagen in reeks 1 versus net 0 en 1, die zou de sleutels. 

Met een hash table is het soort van hetzelfde idee. Met een hash tafel, hebben we dit hash functie die hash codes genereert. Dus de sleutel is de hash-code van de data. En de waarde, met name spraken we over chaining in de video op hashtabellen, is dat gelinkte lijst van gegevens dat hashes van die hash-code. Rechts. Wat over een andere aanpak Deze methode, hoewel? Wat te denken van een methode waarbij de toets wordt gegarandeerd uniek, in tegenstelling tot een hash tafel, waar we konden eindigen met twee gegevens met dezelfde hashcode. En dan hebben we te maken met die door een of meer indringende bij voorkeur chaining om dat probleem op te lossen. 

Dus nu kunnen we garanderen dat onze belangrijkste uniek zal zijn. En wat als onze waarde was gewoon iets wat zo makkelijk als ware en valse die ons vertelt of of niet dat stukje informatie bestaat in de constructie? Een Booleaanse kan zo simpel zijn als een beetje te zijn. Realistisch is het waarschijnlijk een byte meer kans dan een beetje. Maar dat is een stuk kleiner dan opslaan misschien een 50-tekenreeks, bijvoorbeeld. 

Dus probeert, vergelijkbaar met tabellen hash, die samen arrays en gelinkte lijst, probeert combineren arrays structuren en pointers samen om gegevens in een interessante manier die behoorlijk verschillend van alles wat we tot nu toe gezien. Nu gebruiken we de gegevens als een routekaart deze gegevensstructuur te navigeren. En als we kunnen volgen de roadmap, als we kunnen Volg de gegevens van begin tot eind, zullen we weten of deze data bestaan ​​in de trie. 

En als we niet kunnen volgen de kaart van betekenis te eindigen bij alle, de gegevens niet bestaan. Ook hier zijn de sleutels gegarandeerd uniek. En dus in tegenstelling tot een hash-tabel, zullen we nooit te behandelen botsingen here. En geen twee stukken van de gegevens precies dezelfde roadmap tenzij die data identiek. 

Als we voegen John, dan we op zoek naar John. Dat zijn twee identieke stukken data, rechts, zijn we op zoek door. Maar anders, elke twee stukken gegevens gegarandeerd unieke roadmaps hebben door deze gegevensstructuur. En we gaan om een ​​kijkje te nemen een visuele van deze in slechts een moment. 

We zullen dit doen door te proberen maak een nieuwe datastructuur, in kaart brengen van de volgende belangrijke waarde paren. In dit geval, we gaan niet te gebruiken iets eenvoudigs als een Boolean. We zullen eigenlijk de snaar slaan. En die string gaat is de naam van een universiteit. 

En de sleutel is naar het jaar toen die universiteit werd gesticht. Al jaren voor de universiteiten zullen worden vier cijfers. En dus zullen we die vier cijfers gebruiken navigeren door deze data structuur. En we zullen zien, nogmaals, hoe wij dat doen in slechts een seconde. 

Aan het einde van het pad, zullen we de naam te zien van de universiteit die overeenkomt deze sleutel, die vier cijfers. Het basisidee achter een trie is wij een centrale route. Zo denken als een boom. En dit is vergelijkbaar in de spelling en qua concept met een boom. Over het algemeen wanneer we denken over bomen in de echte wereld, hebben ze een wortel die in het grond en ze omhoog te laten groeien en ze hebben vestigingen en ze hebben bladeren. En eigenlijk het idee een trie is precies hetzelfde, behalve dat wortel wordt verankerd ergens in de lucht. De bladeren staan ​​onderaan. 

Dus het is net zoiets als het nemen van een boom en gewoon flipping het ondersteboven. Maar er zijn nog takken. En die zouden onze wegen, die zullen onze verbindingen van de wortel naar de bladeren. In dit geval, die paden, die takken zijn gelabeld met cijfers die ons vertellen welke weg te gaan van waar we zijn. 

Als we een 0, gaan we naar beneden deze tak, als we een 1, gaan we naar beneden deze tak, enzovoort, enzovoort. Nou ja, wat betekent dit? Nou, dat betekent dat op elk knooppunt en elk knooppunt in het middelste en elke tak, Er zijn 10 mogelijke plaatsen die we kunnen gaan. Zo zijn er 10 pointers vanaf elke locatie. 

En dit is waar probeert een kan krijgen beetje intimiderend voor iemand wie heeft niet veel ervaring in de informatica voor. Maar probeert zijn echt pretty awesome. En als je de kans om te werken met hen en u bent bereid om te graven in bent en experimenteren met hen, ze zijn echt heel interessant datastructuren te werken. Als we willen een element in te voegen in de Trie, alles wat we moeten doen is het bouwen van de juiste pad van de wortel naar het blad. Hier is wat elke stap langs de weg eruit zou kunnen zien. We gaan een nieuwe gegevens te definiëren structuur een nieuwe node een trie. 

En de binnenkant van die gegevens structuur zijn er twee stukken. We gaan naar de winkel de naam van een universiteit. En we gaan slaan een array van pointers met andere knooppunten van hetzelfde type. Dus, nogmaals, dit is dat soort van begrip overal wij zijn, wij bij 10 mogelijk plaatsen waar we kunnen gaan. Als we een 0, gaan we naar beneden deze tak. Als we een 1, deze tak, en zo voort en zo voort en zo verder. Als we zeggen 9, gaan we naar beneden deze tak. Dus op elk knooppunt, we kunnen gaan 10 mogelijke plaatsen. Dus elk knooppunt moet 10 pointers bevat met andere knooppunten, met 10 andere knooppunten. 

En de gegevens die wij opslaan is alleen de naam van de universiteit. Dus laten we bouwen aan een trie. Laten we voegen een paar items in onze trie. Dus op de top, dit is onze root node. Dit is waarschijnlijk iets te zijn je gaat verklaren wereldwijd. En je gaat om wereldwijd te behouden een pointer naar dit knooppunt altijd. 

Je gaat zeggen, wortel gelijk, en je bent gaat jezelf malloc trie node. En je nooit wortel aan te raken. Elke keer dat u wilt start het navigeren door, u een andere pointer ingesteld gelijk aan wortel, zoals trav, die het voorbeeld I gebruiken in veel van mijn video's hier op stapels en wachtrijen en lijsten enzovoort. 

U stelt een andere pointer riep trav voor traversal. En je trav gebruiken om te navigeren door de gegevensstructuur. Dus laten we zien hoe dit eruit zou kunnen zien. Dus nu, wat doet een knooppunt eruit? Nou, net zoals onze gegevens structuur verklaring aangegeven, We hebben een string, die in dit geval is leeg. Er is hier niets. 

En een array van 10 pointers. En op dit moment, maar we hebben 1 knooppunt in dit trie. Er is niets anders in. Dus al 10 van die pointers punt op null. Dat is wat de rode geeft. 

Laten plaatst de string Harvard. Laten we steek de Universiteit van Harvard in deze trie, die werd opgericht in het jaar 1636. We willen de sleutel te gebruiken, 1636, om ons te vertellen waar we zijn gaat slaan Harvard in de Trie. Nu, hoe kunnen we dat doen? 

Het zou er ongeveer zo uitzien. We beginnen bij de wortel. En we hebben deze 10 plaatsen waar we kunnen gaan. De wortel is net als elke ander knooppunt van de trie. Er zijn 10 plaatsen waar we kunnen gaan vanaf hier. 

Waar doen we waarschijnlijk willen te gaan als de sleutel is 1636? Er is echt twee opties. Rechts. We kunnen de sleutel uit te bouwen rechts naar links en begin met 6. Of we kunnen de sleutel uit te bouwen links naar rechts en beginnen 1. 

Het is waarschijnlijk meer intuïtief als een menselijk wezen te begrijpen we zullen Ga gewoon links naar rechts. En dus als ik wilt invoegen Harvard in deze trie, Ik wil waarschijnlijk om te beginnen door te beginnen bij de wortel, kijken naar mijn 10 opties voor me, en zeggen Ik wil gaan op de 1 pad. OK. 

Nu, 1 pad is momenteel nul. Dus als ik wil om verder te gaan onderaan die weg dit element te voegen in de trie, Ik moet een nieuw knooppunt malloc, hebben 1 wijzen daar, en dan ben ik goed om te gaan. 

Dus ik eigenlijk ben op een punt waar ik sta aan de wortel van de boom of het trie en er zijn 10 vestigingen. Maar elke tak heeft een poort aan de voorkant ervan. Rechts. Want er is niets anders is er. Geen veilige doorgang. Dat betekent dat er niets neer een van deze takken. Als ik wil om te gaan bouwen iets, ik wil de poort te verwijderen. Ik wil naar de gate te verwijderen tegenover nummer 1. En ik wil lopen dat. En ik wil bouwen een andere plek voor mij om te gaan. 

En dat is wat ik hier heb gedaan. Dus 1 niet meer wijst op null. Ik heb gezegd dat het veilig is om hier beneden te gaan nu. Ik bouwde een ander knooppunt. En toen ik naar dat knooppunt, ik nog een beslissing te maken. Waar ga ik heen? 

Nou, ik heb nu al beneden de 1 gegaan. Dus nu wil ik waarschijnlijk naar beneden gaan de 6. Rechts. Nogmaals, ik heb 10 locaties ik kan kiezen. Dus laten we nu naar beneden nummer 6. Dus ik duidelijk de poort tegenover nummer 6. En ik loop daar beneden. En ik bouwen een ander knooppunt. En ik heb een ander knooppunt bereikt. 

Nogmaals, ik heb 10 keuzes want waar ik kan gaan. Ik ben verhuisd 1-6. Dus nu wil ik waarschijnlijk naar 3. 3, er is nergens ik kan gaan. Dus ik moet de weg vrij en bouwen mezelf een nieuwe ruimte. En vervolgens van 3, waar wil ik heen? Ik wil naar beneden 6 gaan. 

En, nogmaals, ik moest de weg vrij om het te doen. Dus nu heb ik mijn sleutel gebruikt om in te voegen creëren knooppunten en start deze trie bouwen. Ik ben begonnen bij de wortel. Ik heb naar beneden 1636 gegaan. En nu ben ik op de bodem daar op dat knooppunt. En je zou kunnen Zie het op uw scherm. 

Het is geel gemarkeerd. Dat is waar ik nu ben. Mijn sleutel wordt gedaan. Ik heb elke positie in mijn sleutel uitgeput. Dus ik kan niet verder gaan. Dus op dit punt, alles wat ik echt nodig om te doen is te zeggen, OK. Het is net zoiets als kijken naar de grond, als je mikt jezelf als dit soort pad met verschillende verbindingen. Soort van naar beneden te kijken en het soort verfspuiten Harvard op de grond. Dat is de naam van deze. Weet dat is wat er op deze locatie. Als we beginnen bij de wortel en we gaan 1 en vervolgens 6 en dan 3 en 6, waar zijn we? Nou als we naar beneden kijken en we zien Harvard, dan we weten dat Harvard was opgericht in 1636 op basis van de weg we de uitvoering van dit datastructuur. Dus dat was hopelijk eenvoudig. We gaan nog twee toevoegingen doen. En hopelijk zal helpen om zie dit gedaan tweemaal meer. 

Nu, laten we voegen een andere universiteit. Laten we voegen Yale in deze trie. Yale werd opgericht in 1701. Dus we zullen beginnen bij de wortel, zoals we altijd doen. En we zetten een traversal pointer. We gaan gebruiken om door te gaan. Het eerste wat we willen doen is naar beneden de 1 pad. Dat is het eerste cijfer van onze belangrijkste. Gelukkig, hoewel, we doen niet moet elk werk deze keer doen. De 1 pad is al gewist. Ik al eerder toen ik tikte werd het invoegen van Harvard in 1636. Dus ik kan veilig te bewegen down 1 en er gewoon gaan. Als u naar beneden bewegen van de 1. 

Nu, hoewel, ik wil naar 7. Ik maakte de weg vrij om 6. Ik weet dat ik kan veilig ga verder naar beneden de 6 pad. Maar ik moet om verder te gaan op de 7 pad. Dus wat moet ik doen? Nou, net als vroeger, ik moet gewoon naar de gate te wissen, uit de weg, en het opbouwen van een nieuw knooppunt van de 7 pad. Net als dit. 

Dus nu heb ik verhuisd 1 en 7. En nu ziet, ik ben een soort van deze nieuwe subbranch. Rechts. Alles vanaf 16 op, ik niet schelen. Ik ben geen 16 iets te doen. Ik doe 17 spul. 

Dus nu uit op 17, ik moet soort gloed hier nieuwe paden. Het volgende cijfer mijn sleutel is 0. Ik kan natuurlijk niet overal. Ik bouwde dit knooppunt. Dus ik weet dat er geen paden voorwaarts van hier. Dus ik moet er zelf een te maken. 

Dus ik malloc een nieuw knooppunt en hebben 0 punten daar. En dan nog een keer, malloc ik een nieuw knooppunt en hebben een punt daar. Nogmaals, ik heb mijn sleutel, 1701 uitgeput. Dus ik kijk naar beneden en ik spuitlak Yale. Dat is de naam van dit knooppunt. 

En dus nu als ik ooit nodig om te zien of Yale wordt in dit trie, begin ik bij de wortel, Ik ga naar beneden 1701, en kijk naar beneden. En als ik zie Yale spuiten geschilderd op de grond, dan Ik weet Yale bestaat in dit trie. Laten we nog één. Laten we voegen Dartmouth in deze trie, die werd opgericht in 1769. 

Begin bij de wortel weer. Mijn eerste cijfer van mijn sleutel 1. Ik kan gerust naar beneden dat pad. Die al bestaat. Het volgende cijfer van mijn sleutel is 7. Ik kan gerust naar beneden dat pad. Er bestaat ook. 

Mijn volgende is 6. Van hier, van waar ik momenteel ben geel daar in die middelste knooppunt 6 is momenteel geblokkeerd uit. Als ik wil naar beneden te gaan dat pad, Ik moet het zelf op te bouwen. Dus ik zal een nieuw knooppunt malloc en hebben 6 punt daar. En dan, nogmaals, ik ben laaiend nieuwe paden hier. 

Dus ik malloc een nieuw knooppunt zodat vanaf dat node-- pad nummer 9-- en dan nu Als ik reis 1769, en ik kijk naar beneden. Er is niets dit moment Spuit er geschilderd. Ik kan schrijven Dartmouth. En ik heb gestoken Dartmouth in de trie. 

Dus dat is het invoegen dingen in de trie. Nu willen we zoeken naar dingen. Hoe kunnen we zoeken naar dingen in de trie? Nou, het is vrij veel hetzelfde idee. Nu zijn we gewoon gebruik maken van de cijfers van de belangrijkste om te zien of we kunnen navigeren van de wortel waar we willen gaan in de Trie. 

Als we raakte een doodlopende weg op een punt, dan we weten dat dit element niet kan bestaan of anders dat pad zou zijn al gewist. Als we het allemaal de weg naar het einde, alles wat we moeten doen is naar beneden kijken en zien of dat is het element we zoeken. Als het succes. Als het niet, mislukken. 

Dus laten we zoeken naar Harvard in deze trie. We beginnen bij de wortel. En, nogmaals, we gaan maak een traversal pointer om onze bewegingen te doen voor ons. Van de wortel weten we dat de eerste plaats waar we moeten gaan is 1, kunnen we dat doen? Ja, dat kunnen wij. Als Veilig bestaat. We kunnen er terecht. 

Nu, de volgende plaats die we nodig hebben om te gaan is 6. Heeft de 6 pad bestaan ​​van hier? Ja, het doet. We kunnen naar beneden de 6 pad. En we eindigen hier boven. 

Kunnen we naar beneden de 3 weg van hier? Nou, zo blijkt, ja, dat ook bestaat. En we kunnen krijgen op de 6 weg van hier? Ja, dat kunnen wij. 

We hebben niet helemaal beantwoord maar de vraag. Er is nog steeds een meer stap, dat nu we moeten kijken naar beneden en te zien als dat is actually-- als we op zoek bent naar Harvard, is dat wat we vinden nadat we putten de sleutel? In het voorbeeld zijn we hier gebruiken, de jaren zijn altijd vier cijfers. Maar je zou kunnen worden met behulp van het voorbeeld waar u het opslaan van een woordenboek van woorden. 

En dus in plaats van het hebben van 10 pointers voor mijn locatie, moet u 26. Één voor elke letter van het alfabet. En er zijn enkele woorden als vleermuis, die een onderdeel van batch, bijvoorbeeld. En dus zelfs als je naar de einde van de sleutel en je naar beneden kijkt, u misschien niet zien wat je zoekt. 

Zo heb je altijd te doorkruisen het volledige pad en vervolgens als je succesvol in staat het hele pad doorlopen, kijk naar beneden en doe een definitieve bevestiging. Is dat wat ik zoek? Nou, kijk ik naar beneden na het starten boven en gaan 1636. Ik kijk naar beneden. Ik zie Harvard. Dus ja, slaagde ik. Wat als wat ik ben op zoek naar is niet in de Trie, dat wel. Wat als ik ben op zoek naar Princeton, die werd opgericht in 1746. En dus 1746 wordt mijn sleutel om te navigeren door de Trie. Nou, begin ik bij de wortel. En de eerste plaats wil ik om naar beneden gaat de 1 pad. Kan ik het doen? Ja dat kan ik. 

Kan ik naar beneden de 7 pad vanaf daar? Ja ik kan. Dat bestaat ook. Maar kan ik naar beneden de 4 weg van hier? Dat is hetzelfde als de vraag te stellen, kan Ik ga verder bepaald dat pleintje die ik heb geel gemarkeerd? Er is niets daar. Rechts. 

Er is geen weg vooruit naar beneden de 4 pad. Als Princeton was in deze trie, dat 4 zou zijn al vrijgegeven voor ons. En dus op dit punt we hebben een doodlopende weg bereikt. We kunnen elke niet verder gaan. En zo kunnen we zeggen, definitief, nee. Princeton bestaat niet in deze trie. 

Dus wat betekent dit allemaal? Rechts. Er is veel aan de hand. Er is pointers all over the place. En, zoals je kunt zien alleen van het diagram, er is veel van knooppunten die zijn soort vliegen rond. Maar merk elke keer als we wilden te controleren of er iets was in de Trie, we hadden slechts 4 bewegingen te maken. 

Elke keer als we wilden iets te voegen in de Trie, we moeten 4 bewegingen te maken, eventueel mallocing sommige dingen langs de weg. Maar zoals we zagen toen we gestoken Dartmouth in de trie, soms enkele baan misschien al worden gewist voor ons. En zo als onze trie wordt groter en groter, hebben we minder werk elke keer doen om nieuwe dingen te voegen want we hebben al bouwde veel van de tussenliggende takken langs de weg. Als we alleen maar te kijken naar 4 dingen, 4 is gewoon een constante. We echt soort naderen constante tijd invoegen en constante tijd opzoeken. Het nadeel, natuurlijk is dat Dit trie, zoals je kunt waarschijnlijk vertellen, is enorm. Elk van deze knooppunten neemt veel ruimte. 

Maar dat is de afweging. Als we willen echt snel inbrengen, echt snelle verwijdering, en echt snel opzoeken, moeten we hebben veel data rond vliegen. We hebben opzij te zetten een veel ruimte en geheugen voor die datastructuur bestaan. 

En dat is dus de afweging. Maar het lijkt erop dat we misschien hebben gevonden. We zouden hebben gevonden dat heilige graal van datastructuren met snelle insertie, wissen en opzoeken. En misschien is dit zal een geschikte datastructuur te gebruiken voor welke informatie we proberen te slaan. Ik ben Doug Lloyd, dit is CS50.