>> KEVIN SCHMID: Soms, als het bouwen van een programma, wilt u misschien gebruik maken van een
gegevensstructuur bekend als een woordenboek.
Een woordenboek kaarten sleutels, die meestal strings, waarden, ints,
chars, een pointer naar een object, wat we willen.
Het is net als gewone woordenboeken die kaart woorden door definities.
>> Woordenboeken geven ons de vermogen om informatie op te slaan
geassocieerd met iets en kijk het later.
Dus hoe kunnen we daadwerkelijk implementeren van een woordenboek in bijvoorbeeld C code die we kunnen
gebruiken in een van onze programma's?
Nou, er zijn een heleboel manieren waarop konden we een woordenboek te implementeren.
>> Voor een, konden we een array dat we dynamisch re-size of we konden gebruiken
gelinkte lijst, hash table of een binaire boom.
Maar wat we ook kiezen, moeten we rekening te houden met de efficiëntie en
prestaties van de uitvoering.
We moeten nadenken over de gebruikte algoritme in te voegen en kijk omhoog artikelen in
onze gegevensstructuur.
>> Voor nu, laten we aannemen dat we willen strings gebruiken als sleutels.
Laten we praten over een mogelijkheid, een gegevensstructuur genoemd trie.
Dus hier is een visuele weergave een trie.
>> Zoals de foto doet vermoeden, een Trie is een boom datastructuur met
knooppunten met elkaar verbonden.
We zien dat er duidelijk een wortel knooppunt met een aantal links uit te breiden tot
andere knooppunten.
Maar wat betekent elk knooppunt uit?
Als we aannemen dat we het opslaan van sleutels met alleen letters, en
we geven niet om kapitalisatie, Hier is een definitie van een knooppunt dat
voldoende.
>> Een object waarvan het type struct knooppunt bestaat uit twee delen
riep gegevens en kinderen.
We hebben de gegevens deel verliet als een commentaar te vervangen door een component
verklaring als struct knooppunt opgenomen in een C programma.
De gegevens onderdeel van een knooppunt misschien een Booleaanse waarde die aangeeft of
niet het knooppunt vertegenwoordigt de voltooiing van een woordenboek sleutel of het misschien een
tekenreeks die de definitie van een woord in het woordenboek.
>> We zullen een smiley gebruiken om aan te geven wanneer gegevens aanwezig is in een knooppunt.
Er zijn 26 elementen in ons kinderen array, een index
per alfabetisch teken.
We zullen de betekenis te zien van deze binnenkort.
>> Laten we een kijkje van de wortel in ons diagram, waarin geen data
gekoppeld, zoals aangegeven door de afwezigheid van de smiley in de
datadeel.
De pijlen uitstrekt uit delen van de kinderen reeks vertegenwoordigen niet-knooppunt
verwijzingen naar andere knooppunten.
Bijvoorbeeld, de pijl zich vanaf het tweede element van kinderen
de letter B in een woordenboek sleutel.
En in de grotere diagram we bestempelen het met een B.
>> Merk op dat in de grotere diagram, wanneer we trek een pointer naar een ander knooppunt, het
maakt niet uit waar de pijlpunt ontmoet dat andere knooppunt.
Onze steekproef woordenboek trie bevat twee woorden, die en zoom.
Laten we lopen door een voorbeeld van het opzoeken van gegevens voor een toets.
>> Stel dat we wilden te zoeken van de overeenkomstige waarde voor de sleutel bad.
We beginnen onze blik omhoog bij de root node.
Dan zullen we de eerste letter van onze nemen sleutel, B, en vind het bijbehorende
spot in onze kinderen array.
Merk op dat er precies 26 plekken in de array, een voor elke letter van
het alfabet.
En we moeten de plekken vertegenwoordigen de letters van het alfabet in orde.
>> We kijken naar de tweede index vervolgens, index een, B. algemeen, als we
hebben een aantal alfabetisch teken C we zou de corresponderende vlek bepalen
in de kinderen array met behulp van een berekening als deze.
We konden gebruiken een grotere kinderen matrix als we wilden kijken uit bieden
sleutels met een bredere reeks tekens bijvoorbeeld de totale
ASCII tekenset.
>> In dit geval de aanwijzer in onze kinderen bij matrix in
index een is niet nul.
Dus we blijven zoeken de sleutel bad.
Als we ooit een null pointer aangetroffen op de juiste plek in de kinderen
matrix terwijl we doorkruist de knooppunten, dan moeten we dat we zeggen
kon niets voor die toets te vinden.
>> Nu gaan we de tweede letter van nemen onze belangrijkste, A, en volgt u
pointers dit totdat we tot het einde van onze belangrijkste.
Als we het van de toets bereiken zonder raken van doodlopende wegen, null pointers,
zoals hier het geval is, dan alleen wij moeten nog een ding controleren.
Is deze sleutel echt in het woordenboek?
>> Als dat zo is, moeten we een waarde te vinden, ook een smiley icoon in ons diagram waar
het woord eindigt.
Als er iets anders opgeslagen met de gegevens, dan kunnen we het terug.
Bijvoorbeeld, de sleutel dierentuin niet in de woordenboek, ook al konden we hebben
aan het einde van deze sleutel zonder ooit raken van een null pointer, terwijl we
doorloopt de Trie.
>> Als we probeerde om de sleutel bad, de voorlaatste node-array-index,
overeenkomt met de letter H, zouden een null pointer hebben gehouden.
Dus bad is niet in het woordenboek.
En dus een Trie is uniek omdat de sleutels worden nooit expliciet opgeslagen in
de gegevensstructuur.
Dus hoe kunnen we iets te voegen een trie?
>> Laten we steek de sleutel dierentuin in onze trie.
Vergeet niet dat een smiley op een knooppunt overeenkomen code in een simpele
Booleaanse waarde aan dat de dierentuin geven in het woordenboek of het kan
verantwoordelijk voor meer informatie we willen associëren met de sleutel dierentuin,
zoals de definitie van de woord of iets anders.
In sommige opzichten, het proces in te voegen iets in een Trie is vergelijkbaar
het opzoeken van iets in een Trie.
>> We beginnen opnieuw met de wortel, volgende aanwijzingen gevonden volgens
de letters van onze belangrijkste.
Gelukkig waren we in staat om aanwijzingen te volgen de hele weg tot we bereikt
het einde van de toets.
Aangezien dierentuin is een voorvoegsel van het woord zoom, die lid is van de
woordenboek, hoeven we niet te toewijzen nieuwe knooppunten.
>> We kunnen het knooppunt aanpassen om aan te geven dat het pad tekens die tot
het vertegenwoordigt een sleutel in ons woordenboek.
Nu, laten we proberen het plaatsen van de sleutel BATH in de Trie.
We beginnen bij de wortel knooppunt en volg de aanwijzingen weer.
Maar in deze situatie, we dode raken eindigen voordat we in staat om het te krijgen
van de toets.
Nu, we moeten een aantal nieuwe toe te wijzen knooppunten moet een nieuwe toewijzen
knooppunt voor elke resterende brief van onze belangrijkste.
>> In dit geval, we hoeven alleen maar op een nieuw knooppunt toe te wijzen.
Dan zullen we nodig hebben om de H-index maken verwijzen naar deze nieuwe knooppunt.
Nogmaals, we het knooppunt wijzigen om geven aan dat de pad karakters
waardoor het vertegenwoordigt een sleutel in ons woordenboek.
Laten we redeneren over de asymptotische complexiteit van procedures voor deze
twee operaties.
>> We merken dat in beide gevallen het aantal van stappen ons algoritme namen was
evenredig aan het aantal letters in het sleutelwoord.
Dat klopt.
Wanneer u een woord opzoeken in een trie je hoeft alleen maar om door te herhalen
de letters een voor een, totdat u bereiken het einde van het woord of
raakte een doodlopende straat in de Trie.
>> En wanneer u een sleutel in te voegen waarde paar in een trie met behulp van de
procedure hebben we besproken, het ergste geval zal u toewijzing van een nieuw knooppunt
voor elke letter.
En we zullen dat de toewijzing ervan uitgaan is een constante tijd operatie.
Als we aannemen dat de sleutellengte begrensd door een vaste constante, zowel
inbrengen en kijk omhoog constant zijn tijd gedurende een Trie.
>> Als we niet deze veronderstelling maken dat de sleutellengte wordt begrensd door een vaste
constant, dan inbrengen en kijk omhoog, in het ergste geval worden lineair in de
lengte van de sleutel.
Merk op dat het aantal items opgeslagen in de Trie heeft geen invloed op de look-up
of insertie tijd.
Het is alleen beïnvloed door de lengte van de sleutel.
>> Daarentegen ingangen toevoegen van bijvoorbeeld een hash table neiging om
toekomstige opzoeken langzamer.
Hoewel dit klinkt misschien aantrekkelijk op het eerste, we in gedachten moeten houden dat een
gunstige asymptotische complexiteit niet betekent dat in de praktijk de data
structuur noodzakelijkerwijs onbesproken.
We moeten ook van mening dat voor het opslaan van een woord in een Trie we nodig hebben, in het ergste
geval een aantal knooppunten proportionele de lengte van het woord zelf.
>> Tries neiging om veel ruimte te gebruiken.
Dat is in tegenstelling tot een hash tabel, waar we moeten maar een nieuw knooppunt aan
slaan een aantal belangrijke waarde paar.
Nu, opnieuw in theorie, grote ruimte verbruik lijkt niet als een grote
omgaan, zeker gezien het feit dat de moderne computers hebben gigabyte en
gigabyte geheugen.
Maar het blijkt dat we nog steeds zorgen te maken over het geheugengebruik en
organisatie omwille van prestaties, aangezien moderne computers
over regelingen voor onder de kap te versnellen toegang tot het geheugen.
>> Maar deze mechanismen werken het beste wanneer geheugen toegangen worden gemaakt in compact
regio's of gebieden.
En de knooppunten van een Trie kon wonen overal in die hoop.
Maar dit zijn trade-offs dat we moeten overwegen.
>> Vergeet niet dat, bij het kiezen van een data structuur voor een bepaalde taak, we
moeten denken over wat voor soort de activiteiten van de datastructuur moet
ondersteuning en hoeveel de prestaties elk van deze
operaties is belangrijk voor ons.
Deze operaties kunnen zelfs verder reiken dan alleen
basic uitstraling en inbrengen.
Stel dat we wilden implementeren van een soort van auto-complete functionaliteit, veel
zoals Google zoekmachine doet.
Dat wil zeggen, het geven van de sleutels en mogelijke waarden
hebben een bepaalde prefix.
>> Een Trie is uitermate handig voor deze bewerking.
Het is eenvoudig om door te herhalen de Trie voor elk teken van
het voorvoegsel.
Net als een opzoeken operatie, we konden pointers volgen
teken voor teken.
Dan, als we aankomen aan het einde van de prefix, konden we doorlopen de
resterende deel van de gegevensstructuur omdat een van de toetsen buiten
dit punt hebben de prefix.
>> Het is ook gemakkelijk om deze lijst te zien in alfabetische volgorde, omdat de
elementen van de kinderen reeks staan ​​op alfabetische volgorde.
Dus hopelijk zult overwegen geven probeert te proberen.
Ik ben Kevin Schmid, en dit is CS50.
>> Ah, dit is het begin van de daling.
Het spijt me.
Sorry.
>> Strike vier.
Ik ben weg.
Sorry.
Sorry voor het maken van de persoon die heeft te bewerken deze gek.
>> Sorry.
Sorry.
>> LUIDSPREKER 1: Goed gedaan.
Dat was echt goed gedaan.