[Jouer de la musique] DOUG LLOYD: Donc nous avons progresse lentement et plus proche que le Saint-Graal des données structures, l'une que nous pouvons insérer en, de supprimer et rechercher en temps constant. Droit. Voilà en quelque sorte le but. Nous voulons être en mesure de le faire des choses très, très rapidement. 

Avons-nous l'avons trouvé ici quand nous parlons essais? Eh bien, nous allons jeter un coup d'oeil. Donc, nous avons vu plusieurs différentes structures de données qui manient la cartographie des soi-disant paires clé-valeur, la cartographie de certaines données à à un autre élément de données donc nous savons où les trouver l'information dans la structure. 

Ainsi, par réseau, par exemple, la clé est l'indice de l'élément ou réseau emplacement 0 ou un tableau 1 et ainsi de suite. Et la valeur est les données qui existe à cet endroit. Donc ce qui est stocké dans le tableau 0? Quel est stocké dans le tableau 1 contre seulement 0 et 1, ce qui serait les touches. 

Avec une table de hachage il est sorte de la même idée. Avec une table de hachage, nous avons ce hachage fonction qui génère des codes de hachage. Donc, la clé est le code de hachage des données. Et la valeur, en particulier nous avons parlé de chaînage dans la vidéo sur les tables de hachage, est que la liste chaînée des données dont le hachage pour ce code de hachage. Droit. Qu'en est-il une autre approche cette méthode, si? Qu'en est-il une méthode où le clé est garantie unique, contrairement à une table de hachage, où nous pourrions retrouver avec deux morceaux de données ayant le même code de hachage. Et puis nous avons à traiter avec que ce soit par palpage ou plus chaînage de préférence pour régler ce problème. 

Alors maintenant, nous pouvons garantir que notre clé sera unique. Et si notre valeur était juste quelque chose aussi facile comme vrai et le faux qui nous dit si ou non cette information existe dans la structure? Booléenne pourrait être aussi simple que un peu. De façon réaliste, il est probablement une octet plus susceptibles que les un peu. Mais cela est beaucoup plus petit que le stockage peut être une chaîne de 50 caractères, par example. 

Donc essais, semblable aux différentes tables, qui combinent les tableaux et les listes chaînées, tente de combiner les tableaux, les structures et les pointeurs ainsi que pour stocker des données en une façon intéressante qui est assez différent de tout ce que nous avons vu jusqu'à présent. Maintenant, nous utilisons les données de feuille de route naviguer à cette structure de données. Et si nous pouvons suivre la feuille de route, si nous le pouvons suivre les données de début à la fin, nous allons savoir si ces données exister dans le trie. 

Et si nous ne pouvons pas suivre la carte de signifier à la fin du tout, les données ne peuvent pas exister. Encore une fois, les touches sont ici assuré d'être unique. Et contrairement à une table de hachage, nous ne serons jamais avoir à traiter avec des collisions ici. Et ni deux morceaux de données avoir exactement la même feuille de route à moins que les données sont identiques. 

Si nous insérons John, puis nous recherchons pour John. Voilà deux pièces identiques de données, à droite, nous cherchons à travers. Mais sinon, tout deux éléments de données sont la garantie d'avoir des feuilles de route uniques grâce à cette structure de données. Et nous allons jeter un oeil à un visuel de cela dans un instant. 

Nous allons faire cela en essayant de créer une nouvelle structure de données, la cartographie des paires de valeurs clés suivants. Dans ce cas, on ne va pas à utiliser quelque chose de simple comme un booléen. Nous allons effectivement stocker la chaîne. Et cette chaîne va être le nom d'une université. 

Et la clé va être l'année quand cette université a été fondée. Tous les ans pour les universités vont être quatre chiffres. Et donc nous allons utiliser ces quatre chiffres à naviguer dans cette structure de données. Et nous verrons, encore une fois, comment nous faisons cela en seulement une seconde. 

A la fin de la trajectoire, nous verrons le nom de l'université qui correspond à cette touche, ces quatre chiffres. L'idée de base derrière un trie est que nous avons une voie centrale. Alors, pensez-y comme un arbre. Et ce qui est similaire à l'orthographe et dans le concept à un arbre. Généralement, lorsque nous pensons à arbres dans le monde réel, ils ont une racine qui est dans le sol et ils poussent à la hausse et ils ont des succursales et ils ont des feuilles. Et fondamentalement l'idée de un trie est exactement le même, sauf que racine est ancrée quelque part dans le ciel. Et les feuilles sont au fond. 

Donc, il est un peu comme prendre un arbre et juste retournant à l'envers. Mais il ya encore des branches. Et ceux qui seraient nos voies, ceux-ci seront nos connexions partir de la racine vers les feuilles. Dans ce cas, ceux qui chemins, ces branches sont étiquetés avec des chiffres qui nous disent où aller à partir de là où nous sommes. 

Si nous voyons un 0, nous descendons cette branche, si nous voyons un 1, nous descendons cette branche, et ainsi et ainsi de suite. Eh bien, qu'est-ce que cela signifie? Eh bien, cela signifie que à chaque point de jonction et chaque noeud de la milieu et chaque branche, il y a 10 possible lieux que nous pouvons aller. Donc, il ya 10 pointeurs de chaque emplacement. 

Et ce est là essais peuvent obtenir un peu intimidant pour quelqu'un qui est n'a pas beaucoup de expérience en informatique avant. Mais essais sont vraiment assez impressionnant. Et si vous avez la chance de travailler avec eux et vous êtes prêt à creuser dans et d'expérimenter avec eux, ils sont vraiment très intéressant structures de données pour travailler avec. Si nous voulons insérer un élément dans le trie, tout ce que nous devons faire est de construire le chemin correct de la racine à la feuille. Voici ce que chaque étape la façon dont pourrait ressembler. Nous allons définir une nouvelle donnée structure d'un nouveau nœud appelé un trie. 

Et à l'intérieur de ces données la structure il ya deux morceaux. Nous allons stocker le nom d'une université. Et nous allons stocker un tableau de pointeurs à d'autres noeuds du même type. Donc, encore une fois, cela est ce genre du concept de partout nous sommes, nous, à 10 possible endroits nous pouvons aller. Si nous voyons un 0, nous descendons cette branche. Si nous voyons un 1, cette branche, et ainsi de suite et ainsi de suite et ainsi de suite. Si nous disons 9, nous descendons cette branche. Donc, à chaque point de jonction, nous pouvons aller de 10 places possibles. Ainsi, chaque noeud doit contenir 10 des pointeurs à d'autres noeuds, et 10 d'autres nœuds. 

Et les données que nous stockage est juste le nom de l'université. Donc, nous allons construire un trie. Insérons un couple des éléments dans notre trie. Donc, tout en haut, ceci est notre nœud racine. Cela va probablement être quelque chose vous allez déclarer globalement. Et vous allez maintenir globalement un pointeur vers ce nœud toujours. 

Vous allez dire, root est égal, et vous êtes allez vous malloc noeud de Trie. Et vous allez jamais de toucher à nouveau racine. Chaque fois que vous voulez commencer à naviguer à travers, vous définissez un autre pointeur égale à la racine, comme trav, qui est l'exemple que je utiliser dans plusieurs de mes vidéos ici sur des piles et files d'attente et des listes de liens et ainsi de suite. 

Vous définissez un autre pointeur trav appelé pour la traversée. Et vous utilisez trav pour naviguer à travers la structure de données. Donc, nous allons voir comment cela pourrait ressembler. Donc, en ce moment, ce qui un noeud ne ressemble? Eh bien, tout comme nos données déclaration de la structure indiquée, nous avons une chaîne, qui dans ce cas est vide. Il n'y a rien ici. 

Et un tableau de 10 pointeurs. Et en ce moment, nous ne avoir une nœud dans cette trie. Il n'y a rien d'autre en elle. Donc, tous les 10 de ceux pointeurs points à null. Voilà ce que le rouge indique. 

Insérons la chaîne de Harvard. Insérons l'Université de Harvard dans cette trie, qui a été fondée en 1636. Nous voulons utiliser la clé, 1636, pour nous dire où nous en sommes allez stocker Harvard dans le trie. Maintenant, comment pourrions-nous le faire? 

Il pourrait ressembler à ceci. Nous commençons à la racine. Et nous avons ces 10 endroits où nous pouvons aller. La racine est comme tout autre nœud de l'trie. Il ya 10 places, nous pouvons aller d'ici. 

Où voulons-nous probablement où aller si la clé est 1636? Il n'y a vraiment deux options. Droit. Nous pouvons construire la clé de de droite à gauche et de commencer avec 6. Ou nous pourrions construire la clé de de gauche à droite et de commencer avec 1. 

Il est probablement plus intuitive comme un être humain à nous comprendre va Il suffit d'aller de gauche à droite. Et si je veux insérer Harvard dans cette trie, Je veux probablement commencer en partant de la racine, en regardant mes 10 options en face de moi, en disant Je veux aller dans la voie 1. D'ACCORD. 

Maintenant, une voie est actuellement nulle. Donc, si je veux continuer dans cette voie pour insérer cet élément dans le trie, Je dois malloc un nouveau nœud, avoir 1 signaler là, et puis je suis bon pour aller. 

Donc, je suis fondamentalement à une point où je suis debout à la racine de l'arbre ou le Trie et il ya 10 branches. Mais chaque branche a une porte en face d'elle. Droit. Parce qu'il n'y a rien d'autre, il ya. Pas de passage en toute sécurité. Cela signifie qu'il n'y a rien bas l'une de ces branches. Si je veux commencer à construire quelque chose, je veux enlever la porte. Je veux enlever la porte en face du numéro 1. Et je veux marcher dans cela. Et je veux construire un autre lieu pour moi d'aller. 

Et voilà ce que je l'ai fait ici. Donc 1 ne pointe plus sur null. Je l'ai dit il est sûr de descendre ici maintenant. Je construit un autre nœud. Et quand je reçois à ce nœud, je avoir une autre décision à prendre. Où vais-je aller d'ici? 

Eh bien, je suis déjà allé en bas de la 1. Alors maintenant, je veux probablement descendre la 6. Droit. Encore une fois, je dois 10 emplacements je peux choisir. Passons donc maintenant en baisse numéro 6. Donc je effacer la porte devant le numéro 6. Et je marche là-bas. Et je construis un autre nœud. Et je suis arrivé à un autre point de jonction. 

Encore une fois, je dois 10 choix pour où je peux aller. Je l'ai déplacé de 1 à 6. Alors maintenant, je veux probablement pour aller à 3. 3, il n'y a nulle part où je peux aller. Donc, je dois ouvrir la voie et me construire un nouvel espace. Et puis à partir de 3, où je veux aller? Je veux aller en baisse de 6. 

Et, encore une fois, je devais effacer la façon de le faire. Alors maintenant, je l'ai utilisé ma clé pour insérer créer nœuds et commencent à construire cette trie. Je l'ai commencé à la racine. Je suis allé jusqu'à 1,636. Et maintenant, je suis au fond il sur ce nœud. Et vous pourriez être en mesure de voir sur votre écran. 

Il est surligné en jaune. Voilà où je suis actuellement. Ma clé est fait. Je suis épuisé toutes les positions dans ma clé. Donc, je ne peux pas aller plus loin. Donc, à ce stade, tout ce que je vraiment besoin de faire est de dire, OK. Il est un peu comme la recherche vers le sol, si vous êtes envisager vous que ce genre de chemin avec différentes connexions. Trier de regarder vers le bas et une sorte de peinture au pistolet Harvard sur le terrain. Voilà le nom de cette. Sachez que est ce qui est à cet endroit. Si nous commençons à la racine et nous descendons 1 puis 6 puis 3, puis 6, où sommes-nous? Eh bien, si nous regardons vers le bas et nous voyons Harvard, puis nous savons que Harvard était fondée en 1636 basée sur le chemin nous mettons en œuvre cette structure de données. Donc, ce fut espérons simple. Nous allons faire deux autres insertions. Et nous espérons que ça va aider à cela soit fait deux fois de plus. 

Maintenant, nous allons insérer une autre université. Insérons Yale dans cette trie. Yale a été fondée en 1701. Nous allons donc commencer à la racine, comme nous le faisons toujours. Et nous avons mis un pointeur de parcours. Nous allons l'utiliser pour se déplacer à travers. La première chose que nous voulons faire est d'aller sur la voie 1. Voilà le premier chiffre de notre clé. Heureusement, nous ne faisons pas avoir à faire un travail cette fois. Le 1 chemin a déjà été effacé. Je parvient auparavant quand je a été l'insertion d'Harvard à 1636. Donc, je peux déplacer en toute sécurité en baisse de 1 et juste aller là-bas. Si peut se déplacer sur le 1. 

Maintenant, cependant, je veux aller à 7. Je me suis raclé la voie à 6. Je sais que je peux en toute sécurité procéder sur la voie 6. Mais je dois continuer sur le chemin 7. Alors, que dois-je faire? Eh bien, comme avant, je dois juste pour effacer la porte, sortir de la route, et de construire un nouveau nœud de la voie 7. Comme ça. 

Alors maintenant, je suis passé 1 puis 7. Et maintenant remarquez, je suis en quelque sorte de ce nouveau sous-branche. Droit. Tout le reste de 16 , je ne me soucie pas. Je ne fais pas 16 quoi que ce soit. Je fais 17 trucs. 

Alors maintenant, à partir de 17, je dois sorte de tracer de nouveaux chemins ici. Le chiffre suivant ma clé est 0. Je peux clairement pas aller partout. Je viens de construire ce noeud. Donc, je sais qu'il n'y a pas chemins à terme d'ici. Donc, je dois faire un moi-même. 

Donc, je malloc un nouveau noeud et ont 0 point, il n'y. Et puis une fois de plus, je malloc un nouveau nœud et avoir un point là. Encore une fois, je suis épuisé ma clé 1701. Donc, je regarde et je pulvériser de la peinture Yale. Voilà le nom de ce noeud. 

Et maintenant, si jamais je dois voir si Yale est dans ce trie, je commence à la racine, Je descends de 1701, et regarde vers le bas. Et si je vois Yale pulvérisation peint sur le sol, puis Je sais Yale existe dans ce trie. Faisons un de plus. Insérons Dartmouth dans cette Trie, qui a été fondée en 1769. 

Commencer à la racine de nouveau. Mon premier chiffre de ma clé est 1. Je peux me déplacer en toute sécurité dans cette voie. Cela existe déjà. Le prochain chiffre de ma clé est de 7. Je peux me déplacer en toute sécurité dans cette voie. Il existe aussi. 

Mon prochain est 6. De là, d'où je suis actuellement il en jaune par le fait que le noeud intermédiaire, 6 est actuellement verrouillé off. Si je veux aller dans cette voie, Je dois construire moi-même. Je vais donc malloc un nouveau noeud et ont 6 points là. Et puis, encore une fois, je suis de nouveaux sentiers ici. 

Donc, je malloc un nouveau noeud de sorte que de ce numéro de chemin node-- 9-- puis maintenant si je voyage 1769, et je regarde vers le bas. Il n'y a rien pour le moment vaporisez il peint. Je peux écrire Dartmouth. Et je l'ai inséré Dartmouth dans le trie. 

Voilà donc l'insertion les choses dans le Trie. Maintenant, nous voulons chercher des choses. Comment pouvons-nous cherchons des choses dans le trie? Eh bien, il est à peu près la même idée. Maintenant, nous utilisons simplement les chiffres de la clé pour voir si nous pouvons naviguer à partir de la racine à l'endroit où nous voulons aller dans le trie. 

Si nous avons atteint une impasse en tout point, puis nous savons que cet élément ne peut pas existe ou bien ce chemin serait ont déjà été défrichées. Si nous le faisons tout le chemin à la fin, tout ce que nous devons faire est de regarder vers le bas et voir si cela est l'élément que nous recherchons. Dans ce cas, le succès. Si il est pas sûr. 

Donc, nous allons chercher des Harvard dans cette trie. Nous commençons à la racine. Et, encore une fois, nous allons créer un pointeur de parcours faire nos mouvements pour nous. De la racine nous savons que le premier lieu, nous devons aller est 1, pouvons-nous faire cela? Oui nous pouvons. Si existe en toute sécurité. Nous pouvons y aller. 

Maintenant, le prochain endroit où nous devons aller est 6. Est-ce que le chemin existe 6 à partir d'ici? Oui, il le fait. Nous pouvons aller sur la voie 6. Et nous nous retrouvons ici. 

Pouvons-nous aller sur la voie 3 à partir d'ici? Eh bien, il se trouve que, Oui, cela existe aussi. Et pouvons-nous obtenir sur le chemin d'ici 6? Oui nous pouvons. 

Nous avons répondu à pas tout à fait la question encore. Il ya encore une étape, qui est maintenant nous devons regarder vers le bas et voir si cela est actually-- si nous sommes à la recherche de Harvard, est que ce que nous trouvons après que nous épuisons la clé? Dans l'exemple que nous utilisons ici, les années sont toujours quatre chiffres. Mais vous utilisez peut-être l'exemple où vous stockez un dictionnaire de mots. 

Et au lieu d'avoir 10 des pointeurs pour ma position, vous pourriez avoir 26. Un pour chaque lettre de l'alphabet. Et il ya des mots comme chauve-souris, qui est un sous-ensemble de lot, par exemple. Et même si vous arrivez à la fin de la clé et vous regardez en bas, vous pourriez ne pas voir ce qui vous cherchez. 

Donc, vous avez toujours à traverser le chemin complet, puis si vous étiez en mesure succès pour traverser le chemin d'accès complet, regarder vers le bas et effectuez l'une confirmation définitive. Est-ce que ce que je suis à la recherche? Eh bien, je regarde vers le bas après le démarrage en haut et en allant 1,636. Je regarde en bas. Je vois Harvard. Donc, oui, je réussis. Que faire si ce que je suis à la recherche est pas dans la trie, cependant. Que faire si je suis à la recherche de Princeton, qui a été fondée en 1746. Et ainsi de 1,746 devient ma clé pour naviguer dans le trie. Eh bien, je commence à la racine. Et le premier endroit où je veux à descend le chemin 1. Puis-je le faire? Oui je peux. 

Puis-je descendre le chemin à partir de là 7? Ouais je peux. Cela existe aussi. Mais puis-je aller sur le chemin d'ici 4? Cela est comme posant la question, peut Je procède bas ce petit carré que je l'ai souligné en jaune? Il n'y a rien là-bas. Droit. 

Il n'y a pas aller de l'avant sur la voie 4. Si Princeton était dans ce Trie, que 4 aurait été dégagé pour nous déjà. Et si à ce stade nous avons atteint une impasse. Nous ne pouvons pas aller plus loin. Et donc on peut dire, en définitive, pas. Princeton ne existe pas dans ce trie. 

Alors qu'est-ce que tout cela veut dire? Droit. Il ya beaucoup de choses ici. Il ya des pointeurs dans tous les sens. Et, comme vous pouvez le voir simplement à partir du diagramme, il ya beaucoup de nœuds sont sorte de voler autour. Mais notez chaque fois que nous voulions vérifier si quelque chose était dans le trie, nous avons seulement eu à faire 4 se déplace. 

Chaque fois que nous voulions insérer quelque chose dans le trie, nous devons faire 4 se déplace, peut- allouer de certaines choses sur le chemin. Mais comme nous l'avons vu lorsque nous avons inséré Dartmouth dans le trie, parfois une partie du trajet peut-être déjà défrichées pour nous. Et comme notre trie devient de plus en plus, nous avons faire moins de travail à chaque fois pour insérer de nouvelles choses parce que nous avons déjà construit un grand nombre de l'intermédiaire branches le long du chemin. Si nous ne jamais avoir à regarder 4 choses, 4 est juste une constante. Nous sommes vraiment une sorte de approchons insertion de la constante de temps et de recherche constante de temps. Le compromis, bien sûr, étant que cette trie, comme vous pouvez le dire, est énorme. Chacun de ces nœuds prend beaucoup d'espace. 

Mais voilà le compromis. Si nous voulons vraiment rapide insertion, la suppression très rapide, et recherche très rapide, nous devons ont beaucoup de données qui volent autour. Nous devons mettre de côté beaucoup d'espace et que la mémoire de structure de données exister. 

Et si tel est le compromis. Mais il semble que nous aurait trouvé. Nous aurions peut-être constaté que Saint-Graal de structures de données avec insertion rapide, la suppression et la recherche. Et peut-être que ce sera un structure de données appropriée à utiliser pour toutes les informations nous essayons de magasin. Je suis Doug Lloyd, cela est CS50.