[Powered by Google Translate] [Recherche binaire] [Patrick Schmid - Université de Harvard] [C'est CS50. - CS50.TV] 

Si je vous ai donné une liste de noms de personnages Disney dans l'ordre alphabétique et vous a demandé de trouver Mickey Mouse, comment feriez-vous pour cela? Une façon évidente serait de parcourir la liste depuis le début et vérifier chaque nom pour voir si c'est Mickey. Mais pendant que vous lisez Aladdin, Alice, Ariel, et ainsi de suite, vous vous rendrez vite compte que le démarrage sur le devant de la liste n'était pas une bonne idée. Ok, peut-être vous devriez commencer à travailler à rebours à partir de la fin de la liste. Maintenant que vous lisez Tarzan, Stitch, Blanche-Neige, et ainsi de suite. Pourtant, cela ne semble pas être la meilleure façon de s'y prendre. 

Eh bien, une autre façon que vous pourriez prendre pour ce faire est d'essayer d'affiner la liste des noms que vous avez à regarder. Puisque vous savez qu'ils sont dans l'ordre alphabétique, vous pouvez simplement regarder les noms dans le milieu de la liste et vérifier si Mickey Mouse est avant ou après ce nom. En regardant le nom de famille dans la deuxième colonne vous rendre compte que M pour Mickey vient après J pour Jasmine, si vous souhaitez tout simplement ignorer la première moitié de la liste. Ensuite, vous auriez probablement regarder le haut de la dernière colonne et de voir qu'il commence par Raiponce. Mickey vient avant Rapunzel, dirait qu'on ne peut ignorer la dernière colonne ainsi. Poursuite de la stratégie de recherche, vous verrez rapidement que Mickey est dans la première moitié de la liste restante de noms et enfin trouver Mickey caché entre Merlin et Minnie. 

Ce que vous venez de faire est essentiellement binaire de recherche. Comme ce nom l'indique, il effectue sa stratégie de recherche en quelques binaire. Qu'est-ce que cela signifie? Eh bien, étant donné une liste d'éléments triés, l'algorithme de recherche binaire prend une décision binaire - à gauche ou à droite, supérieure ou inférieure, avant ou après alphabétique - à chaque point. Maintenant que nous avons un nom qui va de pair avec cet algorithme de recherche, Voyons un autre exemple, mais cette fois avec une liste de numéros triés. Disons que nous sommes à la recherche pour le numéro 144 dans la liste des numéros triés. Tout comme avant, nous trouvons que le nombre est au milieu - qui dans ce cas est de 13 - 144 et voir si est supérieur ou inférieur à 13. Comme il est clairement supérieur à 13, on peut ignorer tout ce qui est 13 ou moins et se concentrer uniquement sur la moitié restante. Puisque nous avons maintenant un nombre pair d'éléments à gauche, nous avons simplement choisir un numéro qui est proche de la moyenne. Dans ce cas, nous choisissons 55. Nous aurions pu tout aussi bien choisi 89. D'accord. Encore une fois, 144 est supérieur à 55, alors nous allons vers la droite. Heureusement pour nous, le nombre du milieu prochaine est de 144, celui que nous recherchons. Ainsi, afin de trouver 144 en utilisant une recherche binaire, nous sommes en mesure de le trouver en seulement 3 étapes. Si nous avions utilisé la recherche linéaire ici, il nous aurait fallu 12 étapes. En effet, depuis cette méthode de recherche de moitié le nombre d'éléments il doit regarder à chaque étape, il va trouver l'élément qu'il est à la recherche dans environ le logarithme du nombre d'éléments dans la liste. Maintenant que nous avons vu 2 exemples, nous allons jeter un coup d'oeil à certains pseudo-code pour une fonction récursive qui implémente recherche binaire. En partant du haut, nous voyons que nous devons trouver une fonction qui prend 4 arguments: clé, tableau, min et max. La clé, c'est le nombre que nous sommes à la recherche d', donc 144 dans l'exemple précédent. Array est la liste des numéros que nous recherchons. Min et max sont les indices des positions minimum et maximum que nous étudions actuellement. Alors, quand nous commençons, min sera de zéro et max sera l'indice maximum de la matrice. Comme nous l'limiter la recherche, nous mettrons à jour min et max pour être juste la gamme que nous sommes toujours à la recherche po 

Passons à la partie intéressante premier. La première chose à faire est de trouver le point milieu, l'indice qui est à mi-chemin entre le mini et maxi du tableau que nous envisageons toujours. Ensuite, nous examinons la valeur du tableau à cet endroit mi-parcours et voir si le nombre que nous sommes à la recherche d'est inférieure à cette clé. Si le nombre est à cette position inférieure, alors cela signifie que la clé est plus grand que tous les nombres à gauche de cette position. Ainsi, nous pouvons appeler la fonction de recherche binaire à nouveau, mais cette fois la mise à jour des valeurs minimum et maximum des paramètres de lire que la moitié qui est supérieure ou égale à la valeur que nous venons d'examiner. D'autre part, si la clé est inférieur au nombre courant au milieu de la matrice, nous voulons aller vers la gauche et ignorer tous les nombres supérieurs. Encore une fois, nous appelons binaire de recherche, mais cette fois avec la gamme des valeurs min et max à jour pour inclure juste la moitié inférieure. Si la valeur à mi-chemin de courant dans le réseau n'est pas supérieur ni inférieur à la clé, il doit être égal à la clé. Ainsi, nous pouvons simplement retourner l'indice milieu actuel, et nous avons fini. Enfin, ce contrôle est ici dans le cas où le nombre n'est pas réellement dans le tableau de nombres, nous sommes à la recherche. Si l'indice maximum de la plage que nous sommes à la recherche d' est toujours inférieur au minimum, ce qui signifie que nous sommes allés trop loin. Comme le nombre n'était pas dans le tableau d'entrée, nous renvoient -1 pour indiquer que rien n'a été trouvé. 

Vous avez peut être remarqué que pour cet algorithme au travail, la liste des numéros doit être trié. En d'autres termes, on ne peut que trouver 144 en utilisant la recherche binaire si tous les nombres sont triés du plus bas au plus élevé. Si ce n'était pas le cas, nous ne serions pas en mesure d'exclure la moitié des numéros à chaque étape. Nous avons donc 2 options. Soit on peut prendre une liste non triée et trier avant en utilisant la recherche binaire, ou nous pouvons faire en sorte que la liste des numéros est triée comme nous ajouter des numéros à elle. Ainsi, au lieu de trier juste au moment où nous devons rechercher, pourquoi ne pas garder la liste triée en tout temps? 

Une façon de garder une liste de numéros triés tout en permettant un pour ajouter ou déplacer des numéros de cette liste est d'utiliser ce qu'on appelle un arbre binaire de recherche. Un arbre binaire de recherche est une structure de données qui possède 3 propriétés. En premier lieu, le sous-arbre gauche du noeud contient aucune seules valeurs qui sont inférieures à ou égale à la valeur du nœud. Deuxièmement, le sous-arbre droit d'un noeud ne contient que des valeurs qui sont supérieures à ou égale à la valeur du nœud. Et, enfin, les deux sous-arbres gauche et droit de tous les nœuds sont aussi des arbres binaires de recherche. Regardons un exemple avec les mêmes numéros que nous avons utilisés précédemment. Pour ceux d'entre vous qui n'ont jamais vu un arbre en informatique avant, permettez-moi de commencer par vous dire qu'un arbre pousse vers le bas de l'informatique. Oui, contrairement aux arbres vous êtes habitués, la racine d'un arbre de l'informatique est au sommet, et les feuilles sont en bas. Chaque petite boîte est appelée un nœud et les noeuds sont reliés les uns aux autres par des arêtes. Ainsi, la racine de cet arbre est une valeur de nœud avec la valeur 13, qui a 2 nœuds enfants avec les valeurs 5 et 34. Un sous-arbre est l'arbre qui est formé juste en regardant une sous-section de l'arbre entier. 

Par exemple, le sous-arbre gauche du noeud 3 est l'arbre créé par les noeuds 0, 1, et 2. Donc, si nous revenons aux propriétés d'un arbre binaire de recherche, nous voyons que chaque nœud de l'arbre est conforme à toutes les 3 propriétés, à savoir, la sous-arborescence de gauche ne contient que des valeurs qui sont inférieures ou égales à la valeur du noeud; le sous-arbre droit de tous les nœuds ne contient que des valeurs qui sont supérieures ou égales à la valeur du noeud, et sous-arbres gauche et droit de tous les nœuds sont aussi des arbres binaires de recherche. Bien que cet arbre est différent, c'est un arbre binaire de recherche valide pour le même ensemble de nombres. En fait, il existe de nombreuses façons que vous pouvez créer un arbre binaire de recherche valable à partir de ces chiffres. Eh bien, revenons à la première que nous avons créé. Alors, que pouvons-nous faire avec ces arbres? Eh bien, nous pouvons très simplement trouver les valeurs minimales et maximales. Les valeurs minimales peuvent être trouvés en va toujours vers la gauche jusqu'à ce qu'il n'y pas d'autres nœuds à visiter. A l'inverse, pour trouver le maximum tout simplement descend vers la droite à chaque fois. 

Trouver tout autre numéro qui n'est pas le minimum ou le maximum est tout aussi facile. Dire que nous sommes à la recherche pour le nombre 89. Nous avons simplement vérifier la valeur de chaque nœud et allez vers la gauche ou vers la droite, selon que la valeur du noeud est inférieur ou supérieur à celui que nous recherchons. Donc, à partir de la racine de 13, nous voyons que 89 est plus grand, et si nous allons vers la droite. Ensuite, nous voyons le nœud 34, et encore une fois nous allons à droite. 89 est toujours supérieur à 55, donc nous continuons à aller vers la droite. Nous avons ensuite mis au point un nœud avec la valeur de 144 et allez vers la gauche. Et voilà, 89 est juste là. 

Une autre chose que nous pouvons faire est d'imprimer tous les numéros en effectuant un parcours infixe. Un parcours infixe signifie tout imprimer dans le sous-arbre gauche suivie de l'impression elle-même le noeud puis suivie par une impression tout dans le sous-arbre droit. Par exemple, prenons notre arbre binaire de recherche favori et imprimer les numéros dans l'ordre. Nous commençons à la racine de 13, mais avant l'impression 13, nous devons imprimer tout dans le sous-arbre gauche. Donc, nous allons à 5. Nous devons encore aller plus loin dans l'arbre jusqu'à ce qu'on trouve le nœud le plus à gauche, qui est égale à zéro. Après l'impression de zéro, nous remontons à la 1 et imprimer cela. Puis nous allons à la sous-arbre droit, qui est 2, et imprimer cela. Maintenant que nous avons terminé avec ce sous-arbre, nous pouvons revenir à la 3 et l'imprimer. Poursuivant back up, nous imprimons le 5 puis le 8. Maintenant que nous avons terminé l'ensemble du sous-arbre gauche, nous pouvons imprimer le 13 et commencer à travailler sur le sous-arbre droit. Nous sautons jusqu'au 34, mais avant impression 34, nous devons imprimer son sous-arbre gauche. Donc, nous imprimons 21; puis nous arrivons à imprimer 34 et visiter son sous-arbre droit. Comme 55 n'a pas de sous-arbre gauche, nous l'imprimer et de continuer sur son sous-arbre droit. 144 comporte un sous-arbre gauche, et ainsi nous imprimons le 89, suivi du 144, et enfin le nœud le plus à droite de la 233. Il vous en avez, tous les nombres sont imprimées dans l'ordre du plus bas au plus élevé. 

Ajouter quelque chose à l'arbre est relativement indolore ainsi. Tout ce que nous avons à faire est de s'assurer que nous suivons 3 propriétés binaires de recherche arborescente puis insérez la valeur là où il ya de l'espace. Disons que nous voulons insérer la valeur de 7. Depuis le 7 est inférieur à 13, on va vers la gauche. Mais elle est supérieure à 5, donc nous traversons vers la droite. Comme il est inférieur à 8 et 8 est un noeud feuille, on ajoute 7 à la gauche de l'enfant 8. Voila! Nous avons ajouté un certain nombre à notre arbre binaire de recherche. 

Si nous pouvons ajouter des choses, nous ferions mieux en mesure de supprimer les choses ainsi. Malheureusement pour nous, la suppression est un peu plus compliqué - pas beaucoup, mais juste un peu. Il ya 3 différents scénarios que nous avons à examiner lors de la suppression d'éléments d'arbres binaires de recherche. Tout d'abord, le cas le plus simple est que l'élément est un nœud feuille. Dans ce cas, il suffit de le supprimer et continuer avec notre entreprise. Disons que nous voulons supprimer le 7 que nous venons d'ajouter. Eh bien, il suffit de le trouver, retirez-le et c'est tout. Le cas suivant est de savoir si le nœud a seulement 1 enfant. Ici, nous pouvons supprimer le noeud, mais nous devons d'abord assurez-vous pour relier le sous-arbre qui est maintenant laissé orphelin pour le parent du nœud que nous venons supprimé. Disons que nous voulons supprimer 3 de notre arbre. Nous prenons l'élément enfant de ce noeud et le fixer au parent du noeud. Dans ce cas, nous sommes en train de fixer la 1 à la 5. Cela fonctionne sans problème parce que nous savons, d'après la propriété d'arbre binaire de recherche, que tout, dans le sous-arbre gauche du 3 étant inférieur à 5. Maintenant que 3 sous-arbre est pris en charge, on peut le supprimer. Le troisième et dernier cas est le plus complexe. C'est le cas lorsque le nœud que nous voulons supprimer a 2 enfants. Pour ce faire, nous devons d'abord trouver le nœud qui possède la plus grande valeur suivante, permuter les deux, puis supprimez le nœud en question. Notez que le nœud qui possède la plus grande valeur suivante ne peut pas avoir 2 enfants se depuis son enfant de gauche serait un meilleur candidat pour le plus grand côté. Par conséquent, la suppression d'un nœud avec 2 enfants revient à la permutation de 2 nœuds, et en supprimant ensuite est traité par 1 des 2 règles précitées. Par exemple, disons que nous voulons supprimer le nœud racine, 13. La première chose à faire est de nous trouver la plus grande valeur suivant dans l'arborescence qui, dans ce cas, est de 21. Nous avons ensuite permuter les 2 noeuds, soit 13 et 21 une feuille le nœud du groupe central. Maintenant, nous pouvons simplement supprimer 13. 

Comme mentionné précédemment, il existe de nombreuses façons de faire un arbre binaire de recherche valide. Malheureusement pour nous, certains sont pires que d'autres. Par exemple, qu'est-ce qui se passe quand on construit un arbre binaire de recherche à partir d'une liste triée des chiffres? Tous les numéros sont simplement ajoutés à la droite à chaque étape. Quand nous voulons rechercher un numéro, nous n'avons pas le choix, mais seulement à regarder à droite à chaque étape. Ce n'est pas mieux que la recherche linéaire du tout. Bien que nous ne les couvrir ici, il existe d'autres, plus complexes, des structures de données qui font en sorte que cela n'arrive pas. Cependant, une chose simple qui peut être fait pour éviter cela est simplement modifier aléatoirement les valeurs d'entrée. Il est hautement improbable que par hasard une liste de numéros mélangées sont triées. Si tel était le cas, les casinos ne voulait pas rester en affaires longtemps. 

Il vous en avez. Vous savez maintenant sur la recherche binaire et les arbres binaires de recherche. Je suis Patrick Schmid, et c'est CS50. [CS50.TV] Une façon évidente serait d'examiner la liste de ... [bip] ... Le nombre d'articles ... yep [Rires] ... Poster nœud de 234 ... Augh. >> Yay! C'était -