[REPRODUCCIÓ DE MÚSICA] DOUG LLOYD: Així que hem estat cada vegada més a prop i més a prop que el sant grial de les dades estructures, un que podem inserir en, eliminar de, i mirar cap amunt en temps constant. Dreta. En certa manera és la meta. Volem ser capaços de fer coses molt, molt ràpidament. 

Tenim el trobem aquí quan estem parlant d'intents? Bé, anem a fer una ullada. Així que hem vist diverses diferents estructures de dades que manegen el mapeig de els anomenats parells clau-valor, cartografia d'alguna peça de dades a alguna altra peça de dades així que sabem on trobar la informació en l'estructura. 

Així que per array, per exemple, el clau és l'índex d'element o conjunt ubicació 0 o matriu 1 i així successivament. I el valor de les dades és que hi ha en aquesta ubicació. Així que el que s'emmagatzema en l'array 0? El que s'emmagatzema en la matriu 1 enfront de només 0 i 1, el que seria les tecles. 

Amb una taula hash és espècie de la mateixa idea. Amb una taula hash, tenim aquest hash funció que genera codis hash. Així que la clau és el codi hash de les dades. I el valor, en particular parlem d'encadenament en el vídeo en taules hash, és que la llista enllaçada de dades que hashes a aquest codi hash. Dreta. Què passa amb un altre enfocament aquest mètode, però? Què passa amb un mètode en el qual el clau es garanteix que sigui únic, a diferència d'una taula hash, on podíem acabar amb dues peces de dades que tenen el mateix codi hash. I llavors hem de fer front a que per qualsevol sondeig o més preferentment d'encadenament per arreglar aquest problema. 

Així que ara podem garantir que la nostra clau serà únic. ¿I si el nostre valor era només una cosa tan fàcil com a veritable i fals que ens diu si o no aquesta informació existeix en l'estructura? Booleà podria ser tan simple com una mica. Sent realistes és probablement una byte més probable que una mica. Però això és molt menor que emmagatzemar potser una cadena de 50 caràcters, per exemple. 

Així que intenta, a hashish, taules, que combinen les matrius i llista enllaçada, tries combinen matrius, estructures i punters junts per emmagatzemar dades en una forma interessant que és bastant diferent de qualsevol cosa que haguem vist fins ara. Ara fem servir les dades com un full de ruta per navegar aquesta estructura de dades. I si podem seguir el full de ruta, si podem seguir les dades de principi a fi, anem a saber si aquestes dades existir en el trie. 

I si no podem seguir el mapa del que significa per posar fi a tots, no poden existir les dades. Un cop més, les tecles són aquí garanteix que sigui únic. I així, a diferència d'una taula hash, mai haver de lidiar amb col·lisions aquí. I no hi ha dues peces de dades tenir exactament el mateix full de ruta llevat que les dades són idèntics. 

Si inserim John, llavors busquem Joan. Això és dues peces idèntiques de dades, la dreta, estem mirant a través. Però d'altra banda, cap dues peces de dades són la garantia de tenir fulls de ruta únics a través d'aquesta estructura de dades. I anem a fer una ullada a una imatge visual d'això en un moment. 

Farem això en tractar de crear una nova estructura de dades, la cartografia dels següents parells de valors clau. En aquest cas, nosaltres no farem servir una cosa tan simple com un valor booleà. En realitat anem a emmagatzemar la cadena. I aquesta cadena es va a ser el nom d'una universitat. 

I la clau serà l'any quan es va fundar aquesta universitat. Tots els anys per a les universitats van a ser de quatre dígits. I així utilitzarem aquests quatre dígits a navegar a través d'aquesta estructura de dades. I anem a veure, un cop més, com fem que en tan sols un segon. 

Al final de la ruta, anem a veure el nom de la Universitat que correspon a aquesta tecla, aquests quatre dígits. La idea bàsica darrere d'un trie és que tenim una ruta central. Així que pensar-hi com un arbre. I això és similar a l'ortografia i en concepte a un arbre. Generalment quan pensem en arbres en el món real, tenen una arrel que està en el sòl i creixen cap amunt i tenen sucursals i tenen fulles. I, bàsicament, la idea de 1 trie és exactament el mateix, excepte que l'arrel està ancorat en algun lloc en el cel. I les fulles estan en el fons. 

Així que és una mena de prendre un arbre i acaba de moure d'una tirada a l'inrevés. Però encara hi ha branques. I aquests serien els nostres camins, aquests seran les nostres connexions des de l'arrel fins a les fulles. En aquest cas, aquells camins, aquelles branques s'etiqueten amb els dígits que ens diuen que manera d'anar des d'on estem. 

Si veiem un 0, baixem aquesta branca, si veiem un 1, vam baixar aquesta branca, i així i així successivament. Bé, què vol dir això? Bé, això vol dir que en cada punt d'unió i cada node al mitjana i totes les branques, hi ha 10 possibles llocs que podem anar. Així que hi ha 10 punters de cada lloc. 

I aquí és on tries poden obtenir una mica intimidatori per a algú qui no té una gran quantitat de experiència en ciències de la computació abans. Però intents són realment bastant impressionant. I si vostè té la oportunitat de treballar amb ells i que està disposat a excavar a i experimentar amb ells, són realment molt interessant estructures de dades per treballar. Si volem inserir un element al trie, tot el que ha de fer és construir el camí correcte des de l'arrel a la fulla. Això és el que cada pas al llarg de el camí podria ser similar. Anem a definir un nou dades estructura per a un nou node trucat un trie. 

I dins d'aquestes dades estructura hi ha dues peces. Anem a emmagatzemar el nom d'una universitat. I anem a emmagatzemar una matriu de punters a altres nodes del mateix tipus. Així, de nou, això és que espècie del concepte d'arreu som, a les 10 possibles llocs que podem anar. Si veiem un 0, baixem aquesta branca. Si veiem un 1, aquesta branca, i així successivament i així successivament i així successivament. Si diem 9, baixem aquesta branca. Així que en cada punt d'unió, podem anar 10 llocs possibles. Així que cada node ha de contenir 10 punters a altres nodes, a altres 10 nodes. 

I les dades que estem emmagatzemant és només el nom de la universitat. Així que anem a construir un trie. Anem a inserir un parell d'elements en la nostra trie. Així que a la part superior, aquest és el nostre node arrel. Aquesta és, probablement, serà una cosa vas globalment declari. I vostè va a mantenir globalment un punter a aquest node sempre. 

Vostè dirà, és igual a l'arrel, i ja està va a malloc mateix node trie. I mai vas tocar l'arrel de nou. Cada vegada que vulgui començar a navegar a través de, configura un altre punter igual a l'arrel, com trav, que és l'exemple que utilitzar en moltes de les meves vídeos aquí en piles i cues i llistes d'enllaços i així successivament. 

S'estableix un altre punter anomenada trav de recorregut. I utilitza trav per navegar a través de l'estructura de dades. Així que anem a veure com això podria mirar. Així que ara mateix, el que no un node sembla? Bé, de la mateixa manera que les nostres dades declaració d'estructura indicada, tenim una cadena, que en aquest cas és buida. No hi ha res aquí. 

I un conjunt de 10 indicadors. I en aquest moment, només tenen 1 node en aquest trie. No hi ha res més a ell. Així que tots els 10 dels punta punters a NULL. Això és el que indica el vermell. 

Anem a inserir la cadena de Harvard. Anem a inserir la Universitat de Harvard en aquest trie, que va ser fundada l'any 1636. Volem fer servir la clau, 1636, per dir-nos on som va a emmagatzemar Harvard al trie. Ara, com podem fer això? 

Podria ser alguna cosa com això. Comencem a l'arrel. I tenim aquests 10 llocs que podem anar. L'arrel és igual que qualsevol un altre node del trie. Hi ha 10 llocs que podem anar des d'aquí. 

A on anem, probablement volem per anar si la clau és 1636? No hi ha realment dues opcions. Dreta. Podem construir la clau de dreta a esquerra i començar amb 6. O podríem construir la clau de esquerra a dreta i començar amb 1. 

És probablement més intuïtiu com un ésser humà entendre que va a simplement aneu a l'esquerra a dreta. I pel que si vull inserir Harvard en aquest trie, Probablement Vull començar començant a l'arrel, mirant els meus 10 opcions davant meu, i dient: Jo vull anar pel camí gener. D'ACORD. 

Ara, 1 camí és actualment nul. Així que si vull continuar per aquest camí per inserir aquest element en el trie, He de malloc un nou node, tenen 1 Assenyalo allà, i llavors vull sortir. 

Així que, bàsicament, estic en una punt en el que estic de peu a l'arrel de l'arbre o la trie i hi ha 10 sucursals. Però cada branca té una porta de davant d'ella. Dreta. Perquè no hi ha res més que hi ha. No pas segur. Això vol dir que no hi ha res per qualsevol d'aquestes branques. Si vull començar a construir alguna cosa, vull treure la porta. Vull treure la porta davant del número 1. I vull caminar per això. I jo vull construir un altre lloc per a mi per anar. 

I això és el que he fet aquí. Així que 1 ja no apunta a null. He dit que és segur anar per aquí ara. Jo vaig construir un altre node. I quan arribi a aquest node, I tenir una altra decisió que prendre. On aniré d'aquí? 

Bé, jo ja he passat per l'1. Així que ara, probablement, vull anar per la 6. Dreta. Un cop més, tinc 10 llocs que puc triar. Així que ara anirem cap avall el número 6. Així que puc esborrar la porta davant del número 6. I entro aquí baix. I vaig a construir un altre node. I he arribat a un punt d'unió. 

Un cop més, tinc 10 opcions d'on puc anar. M'he mudat d'1 a 6. Així que ara, probablement, vull anar a la 3. 3, no hi ha cap lloc que puc anar. Així que he de netejar el camí i construir-me un nou espai. I després de 3, per on vull anar? Vull baixar juny. 

I, de nou, vaig haver de aclarir el camí per fer-ho. Així que ara que he fet servir el meu clau per a inserir crear nodes i començar a construir aquest trie. He començat a l'arrel. He anat fins 1636. I ara estic a la part inferior allà en aquell node. I vostè pot ser capaç de veure-ho a la pantalla. 

Ha ressaltat en groc. Aquí és on actualment sóc. El meu clau està fet. He esgotat totes les posicions de la clau. Així que no puc anar més lluny. Així que en aquest punt, tot el que realment heu de fer és dir, a D'acord. És com espècie de mira cap a terra, si estàs imaginant a tu mateix ja que aquest tipus de ruta amb diferents connexions. Ordenar de mirar cap avall i una mena de ruixar pintura de Harvard a terra. Aquest és el nom d'aquesta. Saber que és el que està en aquest lloc. Si comencem a l'arrel i baixem 1 i després 6 i després 3 i després 6, On estem? Bé, si mirem cap avall i veiem Harvard, llavors sabem que Harvard era fundada el 1636 amb seu al camí estem implementant aquesta estructura de dades. Així que era d'esperar senzill. Anem a fer dues insercions més. I és d'esperar que va a ajudar a veure aquest fet dues vegades més. 

Ara, anem a inserir una altra universitat. Anem a inserir Yale en aquest trie. Yale va ser fundada el 1701. Així que anem a començar en el arrel, com sempre ho fem. I ens vam posar un punter recorregut. Farem servir això per moure a través de. El primer que volem fer és anar pel camí gener. Aquest és el primer dígit de la clau. Afortunadament, però, no ho fem haver de fer cap treball en aquesta ocasió. La ruta 1 ja ha estat aprovat. Em vaig aclarir prèviament quan va ser la inserció de la Universitat d'Harvard en 1636. Així que em puc moure amb seguretat baix 1 i acaba d'anar-hi. Si es pot moure per l'1. 

Ara, però, jo vull anar a 7. Em vaig aclarir la forma a les 6. Sé que puc amb seguretat continuar pel camí juny. Però necessito per continuar en el camí juliol. Llavors, què he de fer? Bé, igual que abans, només necessito per aclarir la porta, sortir del camí, i construir un nou node de la ruta 7. Igual que aquest. 

Així que ara m'he mudat 1 i 7. I ara compte, jo sóc una mena d'aquesta nova subbranca. Dreta. Tota la resta de 16 , Jo no em preocupo. No faré res 16. Estic fent 17 coses. 

Així que ara des del 17 en endavant, he de espècie d'obrir nous camins aquí. El següent dígit meva clau és 0. Jo clarament no puc arribar enlloc. Acabo de construir aquest node. Així que sé que no hi ha camins a seguir d'aquí. Així que he de fer un jo mateix. 

Així que malloc un nou node i tenen 0 punt allà. I a continuació, una vegada més, em malloc 1 nou node i tenen un punt allà. Un cop més, he esgotat el meu clau, 1701. Així que miro cap avall i jo pintura d'aerosol de Yale. Aquest és el nom d'aquest node. 

I ara si mai necessito per veure si Yale És en aquest trie, començo a l'arrel, Vaig per 1701, i miro cap avall. I si veig aerosol Yale pintada al terra, a continuació, Sigues Yale existeix en aquest trie. Anem a fer una més. Anem a inserir Dartmouth en això trie, que va ser fundada el 1769. 

Comenceu a l'arrel de nou. El meu primer dígit de la meva clau es 1. Em puc moure amb seguretat per aquest camí. Que ja existeix. El següent dígit de la meva clau és 7. Em puc moure amb seguretat per aquest camí. Existeix també. 

El meu següent és 6. Des d'aquí, des d'on actualment sóc en groc allà en aquell node central, 6 està actualment bloquejat apagat. Si vull anar per aquest camí, He de construir jo mateix. Així que vaig a malloc un nou node i tenen 6 punts allà. I llavors, un cop més, estic camins per obrir aquí. 

Així que malloc un nou node perquè des aquest nombre ruta node-- 9-- i llavors ara si viatjo 1769, i miro cap avall. No hi ha res actualment aerosol pintat allà. Puc escriure Dartmouth. I he inserit Dartmouth al trie. 

Així que aquesta és la inserció coses al trie. Ara volem buscar coses. Com busquem coses al trie? Bé, és més o menys la mateixa idea. Ara només utilitzem els dígits de la clau per veure si podem navegar des de l'arrel cap a on volem anar en el trie. 

Si arribem a un carreró sense sortida en qualsevol moment, a continuació, sabem que no pot existeix aquest element o del que ho faria camí ja s'han aclarit. Si ho fem tot el camí fins Al final, tot el que ha de fer és mirar cap avall i veure si això és l'element que estem buscant. Si ho és, l'èxit. Si no ho és, fallar. 

Així que anem a la recerca per Harvard en aquest trie. Comencem a l'arrel. I, de nou, anem a crear un punter recorregut fer els nostres moviments per a nosaltres. Des de l'arrel sabem que el primer lloc hem d'anar és 1, podem fer això? Sí, podem. Si hi ha segura. Podem anar-hi. 

Ara, el següent lloc on cal anar és 6. Existeix la ruta 6 des d'aquí? Sí, ho fa. Podem anar pel camí juny. I acabem aquí. 

Podem anar pel camí de 3 des d'aquí? Bé, resulta que, sí, que existeix també. I podem aconseguir en el camí juny des d'aquí? Sí, podem. 

Encara no hem contestat la qüestió encara. Encara hi ha una més pas, que és ara hem de mirar cap avall i veure si això és actually-- si estem a la recerca de Harvard, és que el que trobem després que vam esgotar la clau? En l'exemple que estem utilitzant aquí, els anys són sempre quatre dígits. Però és possible que estigui utilitzant el exemple en què vostè està guardant un diccionari de paraules. 

I així, en lloc de tenir 10 punters per la meva ubicació, és possible que tingui 26. Un per cada lletra de l'alfabet. I hi ha algunes paraules com ratpenat, que és un subconjunt de lot, per exemple. I pel que fins i tot si s'arriba a la final de la clau i es mira cap avall, pot ser que no vegi el que que vostè està buscant. 

Així que sempre cal recórrer tot el camí i després si vostè fos capaç d'èxit per recórrer tot el camí, mirar cap avall i faci una confirmació final. ¿Això és el que estic buscant? Bé, jo miro cap avall després de començar a la part superior i anant 1.636. Miro cap avall. Veig Harvard. Així que, sí, ho vaig aconseguir. ¿I si el que estic buscant no està en el trie, però. Què passa si estic buscant Princeton, que va ser fundada el 1746. I així, 1746 es converteix en la clau per navegar pel trie. Bé, em poso a l'arrel. I el primer lloc vull que va pel camí gener. Puc fer-ho? Sí, jo puc. 

Puc anar pel camí de 7 a partir d'aquí? Sí, pot. Que hi ha també. Però puc anar pel camí 4 de aquí? Això és com demanar-li a la pregunta, pot Procedeixo per aquest petit quadrat que he ressaltat en groc? No hi ha res allà. Dreta. 

No hi ha manera d'avançar pel camí abril. Si Princeton va ser en aquest trie, que 4 hauria estat buidat per a nosaltres ja. I així, en aquest punt hem arribat a un carreró sense sortida. No podem anar més enllà. I així es pot dir, en definitiva, no. Princeton no existeix en aquest trie. 

Llavors, què significa tot això? Dreta. Hi ha molt per fer aquí. Hi ha punters de tot el lloc. I, com es pot veure simplement a partir del diagrama, hi ha una gran quantitat de nodes que són una mena de volar al voltant. Però noti cada vegada que volíem comprovar si hi havia alguna cosa en el trie, només vam haver de fer 4 moviments. 

Cada vegada que volíem inserir alguna cosa en el trie, hem de fer 4 moviments, possiblement mallocing algunes coses en el camí. Però com vam veure quan ens inserim Dartmouth al trie, de vegades alguns de la ruta podria ja ser netejat per a nosaltres. I així com la nostra trie fa més gran i més gran, hem de fer menys feina cada vegada inserir noves coses perquè ja hem construït una gran quantitat de la substància intermèdia branques en el camí. Si tan sols alguna vegada hem de mirar 4 coses, 4 és només una constant. Realment estem apropant tipus de inserció constant de temps i la recerca constant de temps. El desavantatge, és clar, és que aquest trie, com vostè probablement pot dir, és enorme. Cada un d'aquests nodes ocupa molt espai. 

Però aquesta és la disjuntiva. Si volem realment ràpid inserció, deleció molt ràpid, i les operacions de recerca molt ràpid, hem de té una gran quantitat de dades que volen voltant. Hem de deixar de banda un munt d'espai i la memòria perquè l'estructura de dades d'existir. 

I això és l'equilibri. Però sembla que podria haver trobat. Podríem haver trobat que Sant Grial de les estructures de dades amb la inserció ràpida, eliminació i cerca. I potser això serà un estructura de dades apropiada a utilitzar per a qualsevol informació estem tractant d'emmagatzemar. Sóc Doug Lloyd, això és CS50.